Problem B
Roomba 2

Image of a vacuuming robot by geranium alpha

Your friend Tómas has a very eccentric grandfather, mister Miyagi, from which he inherited a large shed in Raufarhöfn. The only condition his grandfather stipulated is that the floor must be kept clean. A rumor has long been going around regarding what’s stored in the shed, but some thing its the first 3141 digits of $\pi $. Others think it stores the Ramsey-number $R(6,6)$. What truly lives in the shed will ultimately only be known by Tómas.

Tómas lives in Reykjavík and doesn’t have the time to drive to Raufarhöfn regularly to vacuum the shed. He thus contacts the main vacuuming experts of the country, which can be found at the store Ryksugur í Úrvali Með Barka og Allt (initials are RÚMBA) and asks them to send over their most powerful vacuuming robot.

RÚMBA starts designing a vacuuming robot that will meet Tómas’s needs. After a great deal of work they end up with a robot that vacuums twice as well and has twice the range of any other known vacuuming robot. They haven’t decided on a name yet, but decide to call it R2-D2 while they’re looking for a better name.

At RÚMBA they want to make the vacuuming robot as efficient as possible. That is to say, when the robot vacuums as room, the people at RÚMBA don’t want the robot to take an unneccesarily long path.

No programmers work at RÚMBA so they look to Tómas, who is from one of the most famous computer science families of Iceland, to implement the path finding algorithm of the robot. Tómas is too busy solving the knapsack problem in polynomial time, so he asks you to implement it for him.

RÚMBA tells you the robot only vacuums rectangular rooms and that they get to know the length and width beforehand. The robot starts by dividing the room into cells, i.e. $r$ rows and $d$ columns. The robot chooses the size of the cells such that if it is at the center of a cell it can vacuum the entire cell. The robot assigns each cell some coordinates $(a, b)$ where $a$ is the row of the cell and $b$ the column. The rows are numbered in increasing order from bottom to top and the columns from left to right. The count starts at $0$. See the example in Image 1.

Your assignment is to find the shortest possible path for the robot to vacuum the entire room such that it starts and ends in the same place. The robot starts in the bottom left corner of the room, i.e. in cell $(0,0)$ and can only move between adjacent cells (not diagonally).

Figure 1: Example of a room divided into $6 \times 6$ cells.

Input

The input is a single line containing two integers, $r$ and $d$, which denote the number of rows and columns the robot has divided the room into.

Output

Print the shortest path the robot can take to vacuum the entire room. If many such paths exist, any one of them can be printed. The path should be printed by printing out the coordinates of the cells that are visited in the order that they are visited, one on each line. A coordinate $(a,b)$ should be printed as $a$ and $b$, separated by a single spice. Note tha the robot always starts by visiting $(0,0)$.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

2 4

0 0
1 0
1 1
1 2
1 3
0 3
0 2
0 1
0 0

3 6

0 0
1 0
2 0
2 1
2 2
2 3
2 4
2 5
1 5
0 5
0 4
1 4
1 3
0 3
0 2
1 2
1 1
0 1
0 0

3 3

0 0
1 0
2 0
2 1
2 2
1 2
1 1
0 1
0 2
0 1
0 0