Pe cerul unei nopti senine, cercetatorii de la SETI (Search for Extraterrestrial Intelligence Institute) au detectat aparitia simultana a n puncte luminoase. Ei au observat cu surprindere ca toate punctele se aflau in acelasi plan pe care nu l-au mai parasit pana la disparitia lor subita. Fie acesta planul XOY. Pe ecranul radarului, punctele se gaseau initial la coordonatele (x₁, y₁), (x₂, y₂),... (x_n, y_n). Un alt fenomen bizar care le-a atras atentia a fost ca toate cele n puncte luminoase (sa le spunem OZN-uri) executa in fiecare moment miscari sincrone, efectuand aceleasi manevre in plan. S-au numarat m astfel de manevre inainte ca OZN-urile sa dispara. Fiecare manevra consta din urmatoarele deplasari ale tuturor punctelor, efectuate exact in aceasta ordine:

1. Deplasarea punctelor pe directia axei OX cu valoarea h si apoi pe directia OY cu valoarea k.
2. Deplasarea punctelor pe un cerc cu centrul in originea O a sistemului de coordonate. Miscarea este o rotire cu 90 de grade in sens anti-orar a tuturor punctelor in raport cu originea O.
3. Deplasarea punctelor astfel incat coordonata x a fiecarui punct se multiplica de p ori, iar coordonata y se multiplica de q ori.
4. Deplasarea punctelor astfel incat coordonata x a fiecarui punct creste cu valoarea a*y , iar coordonata y a fiecarui punct creste cu valoarea b*x. Astfel, daca x si y sunt coordonatele actuale ale unui punct, atunci noile coordonate x' si y' se obtin astfel: x' = x + a*y si y' = y + b*x.

Cerinta

Scrieti un program care determina coordonatele finale ale celor n OZN-uri, dupa efectuarea celor m manevre.

Date de intrare

Fisierul de intrare ozn.in contine pe prima linie numarul natural n. Fiecare dintre urmatoarele n linii contine cate o pereche de numere intregi x y, reprezentand coordonatele initiale ale celor n OZN-uri. Pe linia n+2 se gasesc sapte numere intregi separate prin spatii: m h k p q a b.

Date de iesire

Fisierul de iesire ozn.out va contine n linii. Pe linia i vor fi scrise doua numere intregi reprezentand coordonatele finale x si y ale OZN-ului i, calculate modulo 90001 (considerand ordinea din fisierul de intrare).

Restrictii

• 1 <= n <= 100000
• 1 <= m <= 4000000000
• -1000 <= h, k, a, b, p, q <= 1000
• Coordonatele initiale -1000 <= x1, y1, x2, y2,... xn, yn <= 1000

Exemple

ozn.in	ozn.out	Explicatie
1 2 1 2 1 -2 3 -1 -2 1	26 89997	Coordonatele initiale ale singurului OZN sunt:(2, 1). Dupa deplasarea 1. , x = 3, y = -1. Dupa deplasarea 2., x = 1, y = 3. Dupa deplasarea 3., x = 3, y = -3. Dupa deplasarea 4., x = 9, y = 0. Repetarea aceleiasi manevre, deci a aceleiasi secvente de deplasari pornind de la pozitia x = 9, y = 0, conduce la coordonatele finale: x = 26, y = -4. Din punct de vedere matematic, -4 modulo 90001 este 89997, deci se va afisa 26 si 89997

ozn.in	ozn.out	Explicatie
2 1 0 -1 2 2 -2 0 -1 1 0 3	90000 89996 3 9	Dupa prima manevra, x1 = 0, y1 = -1 si x2 = 2, y2 = 3. Dupa a doua manevra, x1 = -1, y1 = -5 si x2 = 3, y2 = 9. Deoarece din punct de vedere matematic -1 modulo 90001 este 90000 iar -5 modulo 90001 este 89996, atunci se afiseaza pentru x1 valoarea 90000 iar pentru y1 valoarea 89996.

prof. Constantin Galatan

C. N. "Liviu Rebreanu" Bistrita

tucu_galatan@yahoo.com