Magic Chessboard

Time limit1sMemory limit256 MB

Summary

Flip each even row and then each even column exactly as specified to turn the n by m chessboard into a single color.

Level: Easy1 of 10
Topics: Implementation
Solved: No attempts yet

Problem

Jinsu got an $n \times m$ magic chessboard from his younger sister Jisu. The board has many curious functions, and one of them inverts colors. With that function you can pick a rectangle of cells and turn every white cell inside it black and every black cell inside it white.

At the start the board is painted like an ordinary chessboard. In other words, two cells that share an edge have different colors. Jinsu wants to make every cell the same color using the smallest possible number of inversions.

Rows are numbered 1 to $n$ from the top, and columns are numbered 1 to $m$ from the left.

Input

The first line contains the number of rows $n$ and the number of columns $m$ . ( $1 \le n, m \le 50$ )

Output

Several different ways can reach the minimum number of inversions, so print only the one fixed below.

On the first line print the number of inversions $k$ . On each of the next $k$ lines print one rectangle to invert as r1 c1 r2 c2, the coordinates of one corner cell followed by the coordinates of the opposite corner cell.

Pick the rectangles like this. First, for every even-numbered row in increasing order, print the rectangle r 1 r m that covers the whole row. Then, for every even-numbered column in increasing order, print the rectangle 1 c n c that covers the whole column. If there is no even row or no even column, that part prints nothing. The number of rectangles picked this way always equals the minimum number of inversions.

Examples2

Example 1
Input
```
2 2
```
Expected output
```
2
2 1 2 2
1 2 2 2
```
Example 2
Input
```
3 3
```
Expected output
```
2
2 1 2 3
1 2 3 2
```