F. Delivery Robot
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

The progressive burger joint "ITBurger" plans to launch the delivery of its burgers using autonomous delivery robots that can independently plan the optimal delivery route.

To train the robot, engineer Albina built a testing ground, which is a coordinate plane. On the nodes of the coordinate plane, there are $$$n \times n$$$ light markers in the form of a square, with neighboring markers in columns and rows located at a unit distance from each other. The bottom-left marker is located at the node with coordinates $$$(0,0)$$$, and the top-right marker is at the node with coordinates $$$(n - 1, n - 1)$$$.

The robot's goal is to create a route that visits all the light markers. The robot can start moving from any point on the coordinate plane with integer coordinates from $$$-1000$$$ to $$$1000$$$. It can only move in a straight line, so its trajectory will be a polyline. Albina believes that the robot can be programmed to traverse the light markers along a polyline consisting of exactly $$$2n - 2$$$ segments, where the start and end of the route, as well as all turns, will be at points with integer coordinates from $$$-1000$$$ to $$$1000$$$. Help the robot find such a route.

Input

The first line of input contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of light markers in one row of the square.

Output

Output $$$2n - 1$$$ pairs of integers — the robot's route. The first pair of numbers is the coordinates of the starting point of the route, the next $$$2n - 3$$$ pairs of numbers are the points where the robot makes turns, and the last pair of numbers is the coordinates of the end of the route.

Example
Input
3
Output
2 2
0 0
3 0
0 3
0 1
Note

The robot's route for $$$n = 3$$$. The robot starts at point $$$(2, 2)$$$ and ends at point $$$(0, 1)$$$. The trajectory is shown in the figure.