Triunghiuri

Statement

Ana and Bogdan each draw $N$ lattice points (with integer coordinates) in the $xOy$ plane. Ana's points are denoted $P_0, P_1, \dots, P_{N-1}$, and Bogdan's points are denoted $Q_0, Q_1, \dots, Q_{N-1}$.

Bogdan notices an interesting property: for every $i$ from $0$ to $N-1$, his point $Q_i$ is the centroid of the triangle formed by Ana's point $P_i$ and two other points of his own, $Q_{a_i}$ and $Q_{b_i}$ (where $a_i, b_i \in \{0, 1, \dots, N-1\}$).

In a moment of carelessness, Ana erases the points drawn by Bogdan. Now he must reconstruct them, knowing only the coordinates of the points $P_i$ and the relations described above (the pairs of indices $a_i$ and $b_i$).

Requirement

Given the points $P_0, P_1, \dots, P_{N-1}$ and the pairs of indices $(a_i, b_i)$ for each $i \in \{0, \dots, N-1\}$, determine the coordinates of the points $Q_0, Q_1, \dots, Q_{N-1}$.

Implementation Details

You must implement a single function:

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

The solve function is called by the judge exactly once and receives as parameters:

• $N$: the number of points drawn by Ana;
• $p$: the coordinates of the $N$ points drawn by Ana (indexed from $0$);
• $a$ and $b$: representing the pairs of indices for each property

and must return a sequence of pairs, given by the coordinates of the points $Q_0, Q_1, \dots, Q_{n-1}$.

Constraints

• $3 \leq N \leq 300 \ 000$
• $0 \leq a_i, b_i < N$, for $0 \leq i < N$
• $a_i \neq i$, $b_i \neq i$, $a_i \neq b_i$ for $0 \leq i < N$
• All unordered pairs $\{a_i, b_i\}$ are pairwise distinct
• $0 \leq$ coordinates of points $P_i$ $< \mathbf{7 \cdot 10^{18}}$, for $0 \leq i < N$
• $0 \leq$ coordinates of points $Q_i$ $< \mathbf{7 \cdot 10^{18}}$, for $0 \leq i < N$
• It is guaranteed that the triangles from the properties are not degenerate
• It can be proven that there exists a unique solution for determining the points $Q_i$
• The sides $Q_{a_i}Q_{b_i}$ (the bases of the $N$ triangles) together form a single continuous geometric figure.

A geometric figure is continuous if, for any two points $Q_u$ and $Q_v$ we choose, there exists a sequence of points $Q_{p_1}, Q_{p_2}, \ldots, Q_{p_k}$ satisfying the following properties:

• $p_1=u$, $p_k=v$;
• For every $1 \le j < k$, there exists an unordered pair $\{Q_{a_i}, Q_{b_i}\}$ in the input that coincides with $\{Q_{p_j}, Q_{p_{j+1}}\}$.

Example 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

Explanation

For the first example, the drawing is shown in the image below.
Ana's points are denoted $P_0, P_1, P_2, P_3$, and Bogdan's points are denoted $Q_0, Q_1, Q_2, Q_3$.

Example 2

input

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

output

250000001 350000002
150000003 250000005
200000007 200000011