Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_04_08 - Drzwi i Adrian

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;
           }
 

Dodane przez:Marek Mystkowski
Data dodania:2013-01-26
Limit czasu wykonania programu:0.100s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

ukryj komentarze
2013-02-09 18:32:47 Marek Mystkowski
tak wychodzi ujemne ( widocznie na tablicy były pozycje ujemne) a jak jest a>b trzeba wymienić miejscami
2013-02-09 17:59:24 Micha³ Szumski
W tresci zadania jest napisane
"Dane są tak dobrane, że obliczone liczby a, b spełnią warunek -1000000<a, b<1000000"
Jak interpretowac a<0? Bo zgodnie z podanym wyzej algorytmem wartosci a i b wychodza ujemne, oraz czasem a<b
2013-02-09 17:03:21 Przemek Komosa
"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"

pytanie do ostatnich trzech słów: jakie są warunki zwycięstwa?
2013-02-09 15:07:51 Marek Mystkowski
:)
2013-02-09 15:05:12 Przemek Komosa
dopóki...
2013-02-09 14:59:06 Marek Mystkowski
przepraszam, teraz należy zastosować dany algorytm
2013-02-09 13:53:31 Pawe³ Jasiñski
malo tego dla p = 1 q = 4, to albo a bedzie wieksze od b, albo a bedzie ujemne.
2013-02-09 12:25:22 Damian Straszak
mając p,q, liczby a,b nie są wyznaczone jednoznacznie, mam wrażenie, że to nie jest tu bez znaczenia
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.