h2. Date de ieşire
În fişierul de ieşire $taristraine.out$ se vor afla raspunsurile la operatiile de tipul $2$, fiecare pe cate o linie, in ordinea in care acestea apar in fisierul de intarare. Afisati raspunsurile sub forma $p q$, unde raspunsul (expected value) este egal cu $p / q$ si cel mai mic multiplu comun al lui $p$ si $q$ este $1$.

Afisati expectedul sub forma p q, unde (p,q) = 1 si E = p / q

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 10^5^$
* $1 ≤ costul unei muchii ≤ 10^6^$

h2. Exemplu