E - Juego LCM GCD

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Es bien conocido que BitZero y BitOne son grandes matemáticos, pero lo que es un secreto es la forma en la que ellos hacen sus descubrimientos. Para lograr obtener nuevos resultados utilizan acertijos. Un día BitOne le presentó uno a BitZero que aún no había resuelto. BitOne quería obtener una lista de números que cumplieran ciertas propiedades, pero no sabía siquiera si era posible obtenerla. BitZero, confiado, le aseguró que él le daría solución, pero no sabía cuán complejas eran las propiedades que la lista de números debía cumplir. BitOne le indicó las propiedades a BitZero:
* La cantidad de números en la lista debía ser $N$
* En total había M restricciones
* Cada restricción contaba de cuatro enteros positivos $i, j, G, L$ y consitía en que para los elementos $i$-ésimo y $j$-ésimo el máximo común divisor debía ser $G$ y el mínimo común múltiplo, $L$.
Luego de analizar profundamente el acertijo, BitZero decidió pedirte ayuda.

Input

1ra línea : dos enteros $N$ $(1 \le N \le 500)$ y $M$ $(1 \le M \le 500)$ que representan la cantidad de números y la cantidad de restricciones respectivamente.
M siguientes líneas : cuatro enteros $i, j$ $(1 ≤\le i, j \le N, i \ne j)$, $G$ y $L$ $(1 \le G, L \le 10000)$ indicando los componentes de cada restricción.

Output

1ra línea : "Existe" (sin las comillas) si es posible encontrar una lista de enteros positivos que cumpla todas las propiedades, o "No existe" (sin las comillas) si no lo es.

Sample test(s)

Input
3 1 1 2 4 56
Output
Existe
Input
2 2 1 2 2 6 2 1 2 4
Output
No existe
Input
4 4 1 2 6 12 2 3 6 12 3 4 6 12 4 1 6 12
Output
Existe
Input
5 5 1 2 6 12 2 3 6 12 3 4 6 12 4 5 6 12 5 1 6 12
Output
No existe