Jungle Game

문제

Denise is designing a rainforest themed board game. The goal of the game is for each player to form a team of two characters and complete various challenges.

There are $NN$ different characters numbered from $11$ to $NN$. Each character $ii$ has two attributes $p_{i}p\_i$ and $s_{i}s\_i$ (problem solving skill and strength). The numbers $p_{i}p\_i$ and $s_{i}s\_i$ are positive integers satisfying $1\le p_i,s_i\le N1\; \backslash leq\; p\_i,\; s\_i\; \backslash leq\; N$. Before the game starts, each player will pick two characters $ii$ and $jj$ to form a team. It is possible to pick two copies of the same character. The total problem solving skill and strength of the team will be $p_i+p_{j}p\_i\; +\; p\_j$ and $s_i+s_{j}s\_i\; +\; s\_j$ respectively.

In the game there are also $NN$ challenge cards numbered from $11$ to $NN$. Each of these also has two attributes $P_{k}P\_k$ and $S_{k}S\_k$. Denise has already designed the challenge cards and decided on the values of all numbers $P_1,P_2,\dots ,P_{N}P\_1,\; P\_2,\; \backslash dots,\; P\_N$ and $S_1,S_2,\dots ,S_{N}S\_1,\; S\_2,\; \backslash dots,\; S\_N$. However, the rules of the game assume that it is not possible for a player to form a team whose problem solving skill and strength are both the same as one of the challenge cards. In other words, the situation

$$p_i+p_j=P_k\text{ and }{s}_i+s_j=S_{k}p\_i+p\_j\; =\; P\_k\; \backslash text\{\; and\; \}\; s\_i+s\_j\; =\; S\_k$$

should never occur for any triple $i,j,ki,j,k$ (note that $ii$ can be equal to $jj$).

The only thing left to do is to decide the $NN$ distinct pairs $(p_1,s_1),(p_2,s_2)\dots ,(p_N,s_N)(p\_1,\; s\_1),\; (p\_2,\; s\_2)\; \backslash dots,\; (p\_N,\; s\_N)$ such that $1\le p_i,s_i\le N1\; \backslash leq\; p\_i,\; s\_i\; \backslash leq\; N$ and the situation above never happens.

입력

The first line contains the integer $NN$ ($1\le N\le 20001\; \backslash leq\; N\; \backslash leq\; 2000$).

The following $NN$ lines contain the values of the challenge cards $P_i,S_{i}P\_i,\; S\_i$ ($1\le P_i,S_i\le 2\cdot N1\; \backslash leq\; P\_i,\; S\_i\; \backslash leq\; 2\; \backslash cdot\; N$).

출력

If there is no solution, print "NO". Otherwise, print "YES" followed by $NN$ lines, each containing a pair of integers $p_i,s_{i}p\_i,\; s\_i$ ($1\le p_i,s_i\le N1\; \backslash leq\; p\_i,\; s\_i\; \backslash leq\; N$). These pairs of integers must be distinct. In other words, you may not have two indices $i\mathrm{\ne }ji\; \backslash neq\; j$ with $p_i=p_{j}p\_i\; =\; p\_j$ and $s_i=s_{j}s\_i\; =\; s\_j$.