Given a checkered field N x M, all cells of the field are initially white. The machine can:
paint cell (i, j) black.
for cell (i,j) to find out its nearest white neighbors vertically and horizontally.
Given a sequence of commands for the machine. It is required to execute these commands in the specified sequence, and for each command to query the nearest white neighbors, indicate the result of its execution.
Input
First enter the field sizes N and M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), then the number of commands K (1 ≤ K ≤ 10
5), and then themselves commands. Commands are written one per line in the following format:
Color i j — coloring cell (i, j) black;
Neighbors i j — finding white neighbors for a WHITE cell (i,j).
1≤ i≤ N, 1 ≤ j ≤ M.
Imprint
For each Neighbors query, you first need to display the number of nearest white neighbors (or 0 if there are no white cells left on either side), and then their coordinates (neighbors can be listed in any order). If there are no Neighbors requests, nothing should be output.
Examples
| # |
Input |
Output |
| 1 |
5 |
0 1 2 3 4
1 0 1 2 3
2 1 0 1 2
3 2 1 0 1
4 3 2 1 0
|