Broken Line 07

Azerbaijan is famous for its carpets. As a master carpet designer, you want to make a new design by drawing a broken line. A broken line is a sequence of $t$ line segments in a two-dimensional plane, defined by a sequence of $t+1$ points $p_0, \ldots, p_t$ as follows. For each $0 \leq j \leq t-1$ there is a segment connecting points $p_j$ and $p_{j+1}$.

To make the new design, you have already marked $n$ dots in a two-dimensional plane. The coordinates of dot $i$ ($1 \leq i \leq n$) are $(x[i], y[i])$. No two dots have the same x or the same y coordinate.

You now want to find a sequence of points $(sx[0], sy[0]), (sx[1], sy[1]), \ldots, (sx[k], sy[k])$ that defines a broken line which

• starts at $(0, 0)$ (that is, $sx[0] = 0$ and $sy[0] = 0$),
• contains all of the dots (not necessarily as the endpoints of the segments), and
• consists solely of horizontal or vertical segments (two consecutive points defining the broken line have an equal x or y coordinate).

The broken line is allowed to intersect or overlap itself in any way. Formally, each point of the plane may belong to any number of segments of the broken line.

This is an output-only task with partial scoring. You are given $10$ input files specifying the locations of dots. For each input file, you should submit an output file describing a broken line with the required properties. For each output file that describes a valid broken line, your score depends on the number of segments in the broken line (see Scoring below).

Each input file is in the following format:

• line $1$: $\;\;n$
• line $1+i$ (for $1 \leq i \leq n$): $\;\; x[i] \;\; y[i]$

Each output file must be in the following format:

• line $1$: $\;\;k$
• line $1+j$ (for $1 \leq j \leq k$): $\;\; sx[j] \;\; sy[j]$

Note that the second line should contain $sx[1]$ and $sy[1]$ (i.e., the output should not contain $sx[0]$ and $sy[0]$). Each $sx[j]$ and $sy[j]$ should be an integer.

• $1 \leq n \leq 100\,000$
• $1 \leq x[i], y[i] \leq {10}^9$
• All values of $x[i]$ and $y[i]$ are integers.
• No two dots have the same $x$ or the same $y$ coordinate, i.e. $x[i_1] \neq x[i_2]$ and $y[i_1] \neq y[i_2]$ for $i_1 \neq i_2$.
• $-2 \cdot {10}^9 \leq sx[j], sy[j] \leq 2 \cdot {10}^9$