Triunghiuri

Ana și Bogdan desenează fiecare câte $N$ puncte laticiale (cu coordonate întregi) în planul $xOy$. Punctele Anei sunt notate cu $P_0, P_1, \dots, P_{N-1}$, iar cele ale lui Bogdan cu $Q_0, Q_1, \dots, Q_{N-1}$.

Bogdan observă o proprietate interesantă: pentru orice $i$ de la $0$ la $N-1$, punctul său $Q_i$ este centrul de greutate al triunghiului format de punctul $P_i$ al Anei și de alte două puncte ale sale, $Q_{a_i}$ și $Q_{b_i}$ (unde $a_i, b_i \in \{0, 1, \dots, N-1\}$).

Într-un moment de neatenție, Ana șterge punctele desenate de Bogdan. Acum, el trebuie să le reconstruiască, știind doar coordonatele punctelor $P_i$ și relațiile descrise mai sus (perechile de indici $a_i$ și $b_i$).

Cerință

Dându-se punctele $P_0, P_1, \dots, P_{N-1}$ și perechile de indici $(a_i, b_i)$ pentru fiecare $i \in \{0, \dots, N-1\}$, \ determinați coordonatele punctelor $Q_0, Q_1, \dots, Q_{N-1}$.

Detalii de implementare

Veți avea de implementat o singură funcție:

std::vector<std::pair<long long, long long>> solve(
    int N,
    std::vector<std::pair<long long, long long>> p,
    std::vector<int> a, std::vector<int> b);

Funcția solve se apelează de comisie o singură dată și primește ca parametri:

• $N$: numărul de puncte desenate de Ana;
• $p$: coordonatele celor $N$ puncte desenate de Ana (indexate de la $0$);
• $a$ și $b$: reprezentând perechile de indici pentru fiecare proprietate

și trebuie să returneze un șir de perechi, dat de coordonatele punctelor $Q_0, Q_1, \dots, Q_{n-1}$.

Restricții

• $3 \leq N \leq 300 \ 000$
• $0 \leq a_i, b_i < N$, pentru $0 \leq i < N$
• $a_i \neq i$, $b_i \neq i$, $a_i \neq b_i$ pentru $0 \leq i < N$
• Toate perechile neordonate $\{a_i, b_i\}$ sunt distincte două câte două
• $0 \leq$ coordonatele punctelor $P_i$ $< \mathbf{7 \cdot 10^{18}}$, pentru $0 \leq i < N$
• $0 \leq$ coordonatele punctelor $Q_i$ $< \mathbf{7 \cdot 10^{18}}$, pentru $0 \leq i < N$
• Se garantează că triunghiurile din proprietăți nu sunt degenerate
• Se poate demonstra că există o soluție unică pentru determinarea punctelor $Q_i$
• Laturile $Q_{a_i}Q_{b_i}$ (bazele celor $N$ triunghiuri) formează împreună o singură figură geometrică continuă.

O figură geometrică este continuă dacă, oricum am alege două puncte $Q_u$ și $Q_v$, există o secvență de puncte $Q_{p_1}, Q_{p_2}, \ldots, Q_{p_k}$ care respectă următoarele proprietăți:

• $p_1=u$, $p_k=v$;
• Pentru orice $1 \le j < k$, există o pereche neordonată $\{Q_{a_i}, Q_{b_i}\}$ în input care coincide cu $\{Q_{p_j}, Q_{p_{j+1}}\}$.

Exemplul 1

input

4
3 2
7 3
6 7
2 6
2 3
3 0
0 1

output

4 4
5 4
5 5
4 5

Explicație

Pentru primul exemplu, desenul este redat în imaginea de mai jos.

Punctele Anei sunt notate cu $P_0, P_1, P_2, P_3$, iar cele ale lui Bogdan cu $Q_0, Q_1, Q_2, Q_3$.

Exemplul 2

input

3
399999993 599999990
1 200000002
200000017 26
1 2
2 0
0 1

output

250000001 350000002
150000003 250000005
200000007 200000011