Problem Statement

There is a rectangular piece of land with size H \times W. This land is divided into square blocks of size 1 \times 1, and some of the boundaries between the blocks are separated by waterways. The border of the land is surrounded by fences except for a single entrance, which is the only way to enter or exit the land. The entrance is set on one side of a single block.

You plan to grow crops on this land. When planting or harvesting crops, you will need to move agricultural machinery from the entrance to the block you plan to work on. However, there are no fixed pathways set as the passage for the machinery.

As it would be a challenging task to establish the pathways now, you have decided to move the machinery through the blocks which are not currently being used for growing crops. In other words, when planting or harvesting crops in a particular block, it must be possible to reach to the block from the entrance while satisfying the following conditions:

• You can only move to the four adjacent blocks from each block (moving diagonally is not allowed).
• Yon cannot move from one block to another if they are separated by a waterway.
• You may not pass through blocks which are currently being used for growing crops.

There are K kinds of crops available for planting, numbered 1, 2, \dots, K. You are to choose some of them to be planted and harvested in the following T months. To plant crop k, you will need to plant it no later than the S_k-th month, and harvest it at the D_k-th month. You can plant crop k before the S_k-th month, but even if you plant it earlier than required, you cannot harvest it before D_k-th month.

It is allowed to plant any kind of crop in any block, but one kind of crop cannot be planted in multiple blocks, and multiple kinds of crops cannot be planted in a single block.

Please make a planting plan which maximizes the utility of the land.

Details of the land

The land has coordinates with the northwest corner at (0, 0), the southwest corner at (H, 0), the northeast corner at (0, W), and the southeast corner at (H, W). The block at the i+1-th row from the north and the j+1-th column from the west is a square with diagonal points (i, j) and (i + 1, j + 1). This square is referred to as block (i, j) (0 \le i \le H - 1, 0 \le j \le W - 1).

The entrance is set at the west side of block (i_0, 0) (that is, on the segment between coordinates (i_0, 0) and (i_0 + 1, 0)).

For the blocks which shares sides, whether there is a waterway between them is determined by the given input. Please refer to the "Input" section for the details of the input format for the waterway.

Details of the planting plan

A planting plan describes which crop are grown on which blocks, and when they are planted. It is represented by a sequence (k_1, i_1, j_1, s_1), \dots, (k_M, i_M, j_M, s_M). The m-th element of this sequence signifies that crop k_m is planted in block (i_m, j_m) on the s_m-th month.

Based on a given planting plan, the following actions are taken on the t-th month (t = 1, 2, \dots, T).

1. At the beginning of the t-th month, for all m where s_m = t, crop k_m is planted in block (i_m, j_m). During this process, (i_m, j_m) must be reachable from the entrance without crossing waterways or passing through blocks where crops are currently growing in.
2. At the end of the t-th month, for all m where D_{k_m} = t, crop k_m is harvested from block (i_m, j_m). During this process, (i_m, j_m) must be reachable from the entrance without crossing waterways or passing through blocks where crops are currently growing in.

When planting multiple crops in a same month, the reachability condition above may depend on the order in which crops are planted. For example, if crops k_1 and k_2 are to be planted in a same month, and (i_2, j_2) cannot be reached without passing through (i_1, j_1), then planting crop k_1 before k_2 blocks the way for planting k_2.

In this case, a planting plan is considered valid if there exists an order such that planting them by the order does not lead to the situation above. Such an order will be calculated by the judging program, so it does not have to be determined in the output. Similarly, when harvesting multiple crops in a same month, the order of the crops will be calculated by the judging program and does not have to be determined in the output.

The planting plan must satisfy the following conditions.

• The same crop can only be planted in the same block.
• A block can only contains at most one kind of crop at the same time.
• When planting crop k, it must be planted before S_k-th month.
• When planting or harvesting crop, the target crop must be reachable from the entrance.

Note that, it is not required to plant all the K crops.

Scoring

The score of crop k, X_k, is determined as the following rules.

1. If crop k is not planted, then X_k = 0.
2. If crop k is planted, then X_k = D_k - S_k + 1.

For each test case that received an AC verdict, the score of the test case will be 10^6 \times {\sum_{k = 1}^K X_k \over HWT} (this number will be an integer in all test cases used in provisional test and system test). For each test case that received a not AC verdict, the score of the test case will be 0.

In provisional test, if a submission receives AC in all test cases, the score of the submission will be the sum of the score of all test cases. Otherwise, the score of the submission will be 0.

In system test, the score of the submission will be the sum of the score of all test cases.

The final standings will be determined by the system test which is conducted after the contest. The system test will be performed only for the last submission which received a result other than CE. Be careful not to make a mistake in the final submission.

Number of test cases

• Provisional test: 50
• System test: 2000; We will publish seeds.txt (sha256=0c2ffe8037c0c232ed9775b89a892fc1f68709a1582c83fd6bb609244cefcf32) after the contest is over.

The test cases in the system test contains the same amount of test cases with d = 1, 2, 3, 4, where d is a parameter used in generating the waterways (for details, please refer to the input generation).

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Sample Input 1

10 6 6 3
011010
000001
011000
000110
011000
00000
10001
10010
00110
10101
10000
20
2 10
1 10
4 10
1 10
2 9
4 5
2 8
4 10
4 9
1 9
1 3
1 6
1 7
3 6
8 10
1 7
3 8
2 8
1 10
2 10

Sample Output 1

12
1 0 0 2
2 0 1 1
3 1 0 4
4 0 2 1
5 3 1 2
6 2 0 4
7 4 0 2
10 3 2 1
15 2 0 8
18 5 0 2
19 0 3 1
20 4 1 2

This sample is only to show a concrete example of input/output, and is smaller than the actual test cases used for scoring.