AlgoLiga 2018

Tym razem Twej pomocy potrzebuje wysportowany Adrian. W drzwiach do jego pokoju jest zamek na szyfr, jednak można go zmieniać i może być on bardzo długi. Szalona Magda zrobiła mu piskus i zmieniła kod w zamku; żeby go nie zapomnieć, zapisała kod na kartce. Co prawda Adrian ma specjalną moc otwierania zamkniętych drzwi (zawdzięcza to również swojej bardzo dobrej kondycji fizycznej), ale... ich spójność jest wtedy "zaburzona" i wymagają wymiany, więc poprosił tajnego agenta Krystiana o zdobycie kodu. Jak się można było spodziewać, Magda zgubiła kartkę z hasłem, jednak Krystian, który nie spuszczał ładnej Magdy z oczu, zauważył tę zgubę i zabrał ją. Miał zamiar przekazać ją Adrianowi na szalonym kółku matematycznym, jednak na tym kółku nie było ani Adriana, ani Magdy (nikt chyba nie zna powodu ich nieobecności).

Jednak Krystian podzielił się informacją o znalezionej kartce z uczestnikami kółka. Marysia wpadła na pomysł zrobienia gry bazującej na tym kodzie: zapisano wszystkie liczby kodu na tablicy a następnie każdy uczestnik kółka podawał przedział (a, b) oraz wartość m, oznaczało to, że od pozycji a do pozycji b (włącznie) odejmuje się wartość m, i tak gra się toczyła, aż w końcu ostatnia osoba nie miała żadnej możliwości - ta osoba przegrywa (los chciał, że padło na bezradnego Mateusza, zwanego Zimą). I tak oto powstał zestaw n trójek, jednak okazało się, że te liczby mogą służyć do dalszej zabawy.

Na kolejny pomysł ich wykorzystania wpadła Ania, mianowicie polegał on na tym, że liczby a, b zamieniamy na p, q takie, że: a*p+b*q=NWD(p, q) - gra się toczyła, niektórzy popełniali błędy, ale inni ich poprawiali, i tak po skoczonej grze został wyłoniony mistrz, a dokładniej mistrzyni, mianowicie Marysia. Krystian wpadł na pomysł, że zamiast dać Adrianowi gotowy kod, da zestaw tych końcowych trójek i napisze, co z nimi robili. Gdy Adrian odczytał tę wiadomość, załamał się (było ich tak dużo, że przez najbliższe 2^10 dni musiałby to ręcznie liczyć, bo nie mógł użyć laptopa, który został w pokoju). Miał już zamiar skorzystać ze specjalnego daru otwierania drzwi bez znajomości kodu, ale na szczęście spotkał Ciebie! Pomożesz Adrianowi?

Input

W pierwszym wierszu liczba n, oznaczająca liczbę trójek (n<=1000000).
W nastepnych n liniach liczby p, q, m ( 1< p, q <500010; m<20).
Dane są tak dobrane, że obliczone liczby a, b spełnią warunek -1000000<a, b<1000000

Output

Należy wypisać szukany kod otwierający drzwi.
*co prawda z danych wejściowych nie można od razu określić, ile jest liczb kodu, jednak wiadomo, że nie zaczyna się on 0 i nie kończy 0, w środku 0 może występować.

Example

Input:
5
1 4 2
2 3 5
7 8 2
9 11 2
6 3 2

Output:
2 2 2 9 13 13 2 2 2 2

zmiana liczb  p q  w a b zachodzi zgodnie z algorytmem :
a=1    b=0    c=0    d=1
algorytm:
   dopóki q != 0 {
           r=p%q;
           quot=p/q;
           p=q;
           q=r;
           new_c=a-quot*c;
           new_d=b-quot*d;
           a=c;
           b=d;
           c=new_c;
           d=new_d;
           }