How do you let your goat walk around your vegetable garden? That becomes a real problem sometimes. You should make sure the goat doesn't die of starvation, and you certainly don't want all your crops to be eaten. The garden is a field consisting of 1 × 1 square elements. You can build a fence in some of the garden's elementary squares. To feed itself, the goat needs to eat all the crops in the area consisting of K (1 ≤ K ≤ 10⁶) squares. The goat initially stands in the point of origin (i.e. in the square with coordinates (0, 0)). You have to put the fence in the minimum number of squares so that the goat will be able to visit exactly K squares. The area is said to be fenced if it is impossible to leave it moving only in horizontal or vertical directions.

The input stream contains one number K — the total area granted to the goat.

The first line shall contain the amount N of boundary (fenced) squares. Each of the following N lines shall contain two numbers — X and Y coordinates of the fenced square, respectively. Squares should be output in the order of traversal.