There was a big bank robbery in Tablecity. In order to catch the thief, the President called none other than Albert – Tablecity's Chief of Police. Albert does not know where the thief is located, but he does know how he moves.
Tablecity can be represented as grid, where every cell represents one district. Each district has its own unique name "
", where
and
are the coordinates of the district in the grid. The thief's movement is as follows:
Every hour the thief will leave the district he is currently hiding in, and move to one of the districts:
,
,
,
,
,
as long as it exists in Tablecity.
Below is an example of the thief's possible movements if he is located in district :
Albert has enough people so that every hour he can pick any two districts in Tablecity and fully investigate them, making sure that if the thief is located in one of them he will get caught. Albert promised the President that the thief will be caught in no more than hours and needs your help in order to achieve that.
Constraints
Input Specification
There is no input for this problem.
Output Specification
The first line of output contains integer – duration of police search in hours. Each of the following
lines contains exactly
integers
separated by spaces that represent 2 districts
and
which got investigated during
hour. Output is given in chronological order (
line contains districts investigated during
hour) and should guarantee that the thief is caught in no more than
hours, regardless of thief's initial position and movement.
Sample Output
2
5 1 50 2
8 1 80 2
Explanation for Sample Output
The sample output is not guaranteed to catch the thief and is not correct. There exists a combination of an initial position and a movement strategy such that the police will not catch the thief.
Consider the following initial position and thief's movement:
In the first hour, the thief is located in district . Police officers will search districts
and
and will not find him.
At the start of the second hour, the thief moves to district . Police officers will search districts
and
and will not find him.
Since there is no further investigation by the police, the thief escaped!
Comments
Can the thief go to the position that you just searched? Let's say I searched
and
, can the thief (if he was at
) go to
?