De Crăciun, pe Insula Paștelui se împodobesc altfel brazii, deoarece pe această insulă există o singură dimensiune. Oamenii de pe insulele învecinate (străinii) pun bradul cu vârful în originea sistemului uzual de coordonate 3D. Dar obiceiurile fiind aceleași, trebuie să găsească o soluție pentru a comunica cu oamenii de pe insulă (băștinașii) cu privire la crengile bradului pe care pot fi puse globuri pentru un aspect plăcut. Astfel, străinii au ales să codifice spațiul tridimensional al insulelor lor în spațiul unidimensional al Insulei Paștelui. Ei au ales următoarea reprezentare: au pus în punctul de coordonate (1, 1, 1) numărul 1, în punctul de coordonate (2, 1, 1) numărul 2, în punctul de coordonate (1, 2, 1) numărul 3, în punctul de coordonate (1, 1, 2) numărul 4, și așa mai departe (a se vedea și exemplul). În acest mod există o corespondență între coordonatele 3D ale străinilor și numerele naturale, pe care băștinașii le folosesc pentru a-și împodobi brazii.
Cerinţă
S-a luat decizia ca băștinașii și străinii să comunice printr-un program care poate răspunde la:
- Întrebare străină E: care este numărul n din punctul de coordonate (x, y, z)?
- Întrebare băștinașă P: care sunt coordonatele (x, y, z) la care se află numărul n?
Date de intrare
Programul tău va citi de pe prima linie a fișierului bradut2.in un număr natural pozitiv N care reprezintă numărul de întrebări. Pe fiecare din următoarele N linii se găsesc: ori caracterul E separat prin spațiu de trei numere naturale xyz separate prin spațiu, ori caracterul P separat prin spațiu de un număr natural n.
Date de ieşire
Programul tău va scrie N linii în fișierul bradut2.out, astfel încât pe fiecare linie se găsește răspunsul corespunzător de pe linia din fișierul de intrare: ori un număr natural n, ori trei numere naturale separate prin spațiu xyz. Fiecare linie este urmată de caracterul sfârșit de linie.
Restricţii
1 ≤ x, y, z, x + y + z, N ≤ 100.000 1 ≤ n ≤ 1.000.000.000
Unele biblioteci de citire/scriere pot avea funcții lente.
Exemple
bradut2.in
bradut2.out
Explicaţii
12
E 1 1 1
E 2 1 1
E 1 2 1
E 1 1 2
P 7
E 3 1 1
E 2 2 1
E 1 3 1
E 2 1 2
E 1 2 2
E 1 1 3
P 3
1
2
3
4
1 3 1
5
6
7
8
9
10
1 2 1
Reprezentarea în spațiu a punctelor din exemplu
Punctele nu sunt situate în locații cu vreo coordonată 0.
Exemple de puncte coliniare: (1, 4, 10), (7, 6, 5), (7, 9, 10).
