There is a piece of cheese in the form of an NxM rectangle.
The little mouse wants to eat the whole piece of cheese. Starting in an arbitrary cell, he, eating the next piece (1x1), goes to the next (only if he has not eaten it yet). Help the little mouse make a route around the rectangle so that he can eat all the cheese.
Input
The string contains the numbers N, M. (1<=N,M<=30)
Imprint.
Output the route of the mouse as a sequence of coordinates of the pieces it eats.
Cheese pieces have coordinates from 1 to N on the x-axis, from 1 to M on the y-axis.
Examples
| # |
Input |
Output |
| 1 |
2 2 |
1 1
2 1
2 2
1 2
|