Amalthea's new walk#8718
When she was a princess in a small chess castle, Amalthea used to walk each day in the golden ceremonial hall. The floor of the hall was divided into cells of size 1 \times 1. Amalthea's route was the same each day: she started on a certain cell, made certain moves from a cell to its side-wise neighbouring cell, and returned to the initial cell. Since there were no prohibitions in her childhood, she could visit the same cell several times.
After many years of such walks, the gold on the visited cells faded. She memorized the faded pattern for life.
Now, after becoming a countess in a large chess palace, she has decided to restore that pattern using silver tiles in the new golden ceremonial hall, to remind her of her childhood.
The royal sculptor laid out this pattern in silver tiles, but, in order to please the mistress, he made the pattern twice as big. Now each faded cell from the childhood pattern corresponds to 2 \times 2 square of silver tiles. For each cell (, ) from the pattern, he placed silver tiles into cells (, ), (, 2y + 1), (2x + 1, ) and (2x + 1, 2y + 1).
Now Amalthea wants to learn how to traverse the new set of silver cells. As before, she will move only to a side-wise neighbouring cell. As before, she has to return to the initial cell in the end. But now, since the palace etiquette is quite strict, she can not visit the same cell twice or more. The exception is moving to the initial cell at the last move.
Help Amalthea find a valid route for this new pattern.
The first line contains one integer (1 \leq n \leq 30000) — the number of cells in the pattern from childhood.
Each of the next lines contains two integers x_i, y_i (0 \leq x_i, y_i \leq 1000) — coordinates of the faded cell.
It is guaranteed that no cell is given twice, and that the area is side-wise connected.
Output lines, in each of them output the coordinates of the respective cell of Amalthea's route in the palace. Every two consecutive cells, as well as the first and the last cell, must share a side. The route must contain all silver-tiled cells.
Example 1