B. Lefkaritika
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Marikkou is spending her afternoon with her grandmother, who is teaching her how to sew lefkaritika—a traditional type of Cypriot lace. These laces are made by tying tiny knots and joining them with threads to form delicate designs.

There are many patterns in lefkaritika, but Marikkou is most fascinated by the ones built entirely from knots and threads. She begins with a simple rectangular frame of knots, arranged in an $$$n \times m$$$ grid (all evenly spaced). From there, she can add new knots inside the frame and connect them to existing ones with threads, slowly weaving the lace.

Example of lefkaritiko for $$$n=5$$$ and $$$m=4$$$.

As she experiments, Marikkou discovers that not every design works: the lace must be sturdy. After some careful thought and experimentation, she makes up the rules for which patterns are allowed:

  • All the knots on the outer $$$n \times m$$$ frame must be used.
  • The threads may only form triangles.
  • All the triangles must have angles less than or equal to 90 degrees.
  • A knot that serves as a corner of one triangle cannot lie along the side of another triangle.
  • New knots may only be placed at points with integer coordinates.

Here are some examples of correct and incorrect lefkaritika:

  • a: incorrect, the knot on the frame is not used.
  • b: incorrect, the part is not a triangle.
  • c: incorrect, the angle is greater than 90 degrees.
  • d: incorrect, the knot is on a side of another triangle.
  • e: correct, 12 triangles.
  • f: correct, 10 triangles.

Marikkou believes that the fewer triangles she uses, the more elegant the lefkaritiko becomes. She wonders what pattern will give her the smallest number of triangles while still holding together firmly. Can you help her sew the perfect lefkaritiko?

This is an output-only task. Download the 20 input files (01.txt, 02.txt, up to 20.txt) containing the inputs from the contest system, solve the task, and submit the output as separate files. You need to submit a zip file called containing files 01.out, 02.out, etc.

Input

The single line of the input contains two integers $$$n$$$ and $$$m$$$, the width and the height of the frame.

Output

In the first line output integer $$$t$$$, the number of threads used. In the next $$$t$$$ lines output 4 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, the coordinates of two knots connected with a thread.

Scoring

Your score for the task will be the sum of your score on each of the 20 testcases 01.txt through 20.txt. Each testcase is worth up to 5 points.

If your answer for the test is incorrect, you will get 0 points. If it is correct, then your score $$$S$$$ for this test will be calculated using the following formula:

$$$S = 5 \cdot (0.05 + 0.95\cdot \min(\frac{T_{opt}}{T}, 1))$$$

Here $$$T$$$ is the number of triangles in your solution, and $$$T_{opt}$$$ is the number of triangles in the best solution found by judges.

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

Here is a picture for the example: