Description

In the year of 2018, the International Olympiad in Informatics will be held in Japan. In order to celebrate it, the committee of IOI is planning to make an artwork of “slightly odd design”, and decorate the competition venue with it. The committee requested the JOI (Just Odd Inventions) Co. Ltd. to make a design of it. The designers of JOI proposed the following:

• The artwork will be made on the rectangular board with $H \times W$ cells. We will pave the board with $N$ tiles. The tiles will not overlap with each other.
• The size of the tile $i$ ($1 \leq i \leq N$) is either $1 \times 1$ or $1 \times 2$. The color of the tile $i$ is $C_i$.
• We may rotate a tile of $1 \times 2$, and may use it as a tile of $2 \times 1$.

Moreover, they proposed the kinds of tiles for the artwork. However, they did not propose how to pave tiles on the board, which is the most important part of the design. Because the designs proposed by JOI are always beautiful, the committee decided to obey the proposal of JOI for the kinds of the tiles. The committee has to think of the way to pave the tiles on the board. The committee decided to pave the tiles in order to maximize the beauty of the design.

The beauty of the design is calculated as follows:

• For an edge of the cells on the board shared by two tiles with color $j$ and color $k$, the score of it is $A_{j,k}$.
• The beauty of the design is the total sum of the scores of the edges of the cells on the board.

If two tiles of $1 \times 2$ shares the edges of two cells, we count the scores of these two edges independently.

You are to calculate the way to pave the tiles on the board whose beauty is as large as possible.

Task

Given the size of the board, the size and the color of each tile, and the way to calculate the beauty of the design, determine the way to pave the tiles whose beauty is as large as possible.

Input Format

There are five subtasks. Each subtask corresponds to a public input data. The format of each input data file is as follows.

• The first line of input contains four space separated integers $H, W, K, N$. This means the rectangular board consists of $H \times W$ cells, there are $K$ kinds of colors of the tiles, and $N$ tiles are used in the design.
• The $i$-th line ($1 \leq i \leq N$) of the following $N$ lines contains two space separated integers $S_i, C_i$. This means the size of the tile $i$ is $1 \times S_i$, and the color of the tile $i$ is $C_i$.
• The $j$-th line ($1 \leq j \leq K$) of the following $K$ lines contains $K$ space separated integers $A_{j,1}, A_{j,2}, \dots, A_{j,K}$. This means, when two tiles with color $j$ and color $k$ share an edge, the score is $A_{j,k}$.

Output Format

Submit an output data file for each input data file. The output data file consists of $N$ lines. The $i$-th line ($1 \leq i \leq N$) describes the way to put the tile $i$ on the board in the following format.

• When $S_i = 1$, the $i$-th line should contain two space separated integers $A_i, B_i$. This means the tile $i$ is put on the cell located in the $A_i$-th row from above and the $B_i$-th column from left.
• When $S_i = 2$, the $i$-th line should contain four space separated integers $A_i, B_i, C_i, D_i$. This means the tile $i$ is put on the board so that it covers the cell located in the $A_i$-th row from above and the $B_i$-th column from left, and the cell located in the $C_i$-th row from above and the $D_i$-th column from left.

3 2 3 4
1 1
2 2
1 3
2 1
2 7 5
7 4 3
5 3 1

2 2
1 1 1 2
3 2
3 1 2 1

Hint

Sample 1 Explanation

In this sample input, the size of the board of the design is $3 \times 2$, and 4 tiles are used. The color and the size of each tile is as follows:

There is a tile of size $1 \times 1$ with color 1, a tile of size $1 \times 2$ with color 2, a tile of size $1 \times 1$ with color 3, and a tile of size $1 \times 2$ with color 1.

We put the tiles as follows. The numbers in the figure indicate the numbers of the tiles.

:::align{center} :::

The beauty of the design is calculated as follows. The beauty of the design is 26.

• Since the tile 2 with color 2 and the tile 4 with color 1 share an edge, we get the score 7.
• Since the tile 2 with color 2 and the tile 1 with color 1 share an edge, we get the score 7.
• Since the tile 4 with color 1 and the tile 1 with color 1 share an edge, we get the score 2.
• Since the tile 4 with color 1 and the tile 3 with color 3 share an edge, we get the score 5.
• Since the tile 1 with color 1 and the tile 3 with color 3 share an edge, we get the score 5.

Constraints

All input data satisfy the following conditions.

• $1 \leq H \leq 100$.
• $1 \leq W \leq 100$.
• $1 \leq K \leq 100$.
• $1 \leq N \leq 10\,000$.
• $1 \leq S_i \leq 2$ ($1 \leq i \leq N$).
• $1 \leq C_i \leq K$ ($1 \leq i \leq N$).
• $H \times W = S_1 + S_2 + \dots + S_N$.
• $0 \leq A_{j,k} \leq 1000$ ($1 \leq j \leq K, 1 \leq k \leq K$).
• $A_{j,k} = A_{k,j}$ ($1 \leq j \leq K, 1 \leq k \leq K$).

Subtasks

For each subtask, the values of $H$, $W$, $K$, $N$ are as in the following table. For the values of $X$, $Y$, see Grading.

Grading

This is an output-only task. There are five subtasks, and each subtask consists of one input data file. Submit an output data file for each subtask. Your score of each subtask is calculated as follows.

• If the way to put the tiles on the board does not satisfy the condition of the output file, the score is zero.
• If the way to put the tiles on the board satisfies the conditions of the output file, the score is calculated using the values of $X$, $Y$ as follows. Let $B$ be the beauty of the design of the way to put the tiles.
  • If $B < X$, the score is zero.
  • If $X \leq B < Y$, the score is $\left\lfloor 1 + 19 \times \left( \frac{B - X}{Y - X} \right)^2 \right\rfloor$. Here, $\lfloor x \rfloor$ is the largest integer less than or equal to $x$.
  • If $Y \leq B$, the score is 20.