Pe cerul unei nopţi senine, cercetătorii de la SETI (Search for Extraterrestrial Intelligence Institute) au detectat apariţia simultană a n puncte luminoase. Ei au observat cu surprindere că toate punctele se aflau în acelaşi plan pe care nu l-au mai părăsit până la dispariţia lor subită. Fie acesta planul XOY. Pe ecranul radarului, punctele se găseau iniţial la coordonatele (x₁, y₁), (x₂, y₂),... (x_n, y_n). Un alt fenomen bizar care le-a atras atenţia a fost că toate cele n puncte luminoase (să le spunem OZN-uri) execută în fiecare moment mişcări sincrone, efectuând aceleaşi manevre în plan. S-au numărat m astfel de manevre înainte ca OZN-urile să dispară. Fiecare manevră constă din următoarele deplasări ale tuturor punctelor, efectuate exact în această ordine:

1. Deplasarea punctelor pe direcţia axei OX cu valoarea h şi apoi pe direcţia OY cu valoarea k.
2. Deplasarea punctelor pe un cerc cu centrul în originea O a sistemului de coordonate. Mişcarea este o rotire cu 90 de grade în sens anti-orar a tuturor punctelor în raport cu originea O.
3. Deplasarea punctelor astfel încât coordonata x a fiecarui punct se multiplica de p ori, iar coordonata y se multiplica de q ori.
4. Deplasarea punctelor astfel încât coordonata x a fiecarui punct creşte cu valoarea a*y , iar coordonata y a fiecarui punct creşte cu valoarea b*x. Astfel, daca x şi y sunt coordonatele actuale ale unui punct, atunci noile coordonate x’ şi y’ se obtin astfel: x’ = x + a*y şi y’ = y + b*x.

Cerinţă

Scrieţi un program care determină coordonatele finale ale celor n OZN-uri, dupa efectuarea celor m manevre.

Date de intrare

Fişierul de intrare ozn.in conţine pe prima linie numărul natural n. Fiecare dintre următoarele n linii conţine câte o pereche de numere întregi x y, reprezentând coordonatele iniţiale ale celor n OZN-uri. Pe linia n+2 se găsesc şapte numere întregi separate prin spaţii: m h k p q a b.

Date de ieşire

Fişierul de ieşire ozn.out va conţine n linii. Pe linia i vor fi scrise două numere întregi reprezentând coordonatele finale x şi y ale OZN-ului i, calculate modulo 90001 (considerând ordinea din fişierul de intrare).

Restricţii

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

Exemple

ozn.in	ozn.out	Explicaţie
1 2 1 2 1 -2 3 -1 -2 1	26 -4	Coordonatele initiale ale singurului OZN sunt:(2, 1). După 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.

ozn.in	ozn.out	Explicaţie
2 1 0 -1 2 2 -2 0 -1 1 0 3	-1 -5 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

prof. Constantin Gălăţan

C. N. "Liviu Rebreanu" Bistriţa

tucu_galatan@yahoo.com