Colored Tiles 4

In 2018, the International Olympiad in Informatics will be held in Japan. To celebrate it, the IOI committee plans to make an artwork of "slightly odd design" and decorate the competition venue with it. The committee asked JOI (Just Odd Inventions) Co. Ltd. to design it. JOI proposed the following.

• The artwork is made on a rectangular board of $H \times W$ cells. The board is paved with $N$ tiles, and the tiles do not overlap.
• Tile $i$ ($1 \le i \le N$) is $1 \times 1$ or $1 \times 2$, and its color is $C_i$.
• A $1 \times 2$ tile may be rotated and used as a $2 \times 1$ tile.

JOI fixed the kinds of tiles but did not say how to lay them out. The committee must keep JOI's tile kinds and find a layout that maximizes the beauty of the design.

When two tiles share an edge of cells and their colors are $j$ and $k$, that edge scores $A_{j,k}$. The beauty is the sum of the scores of all such edges. If two $1 \times 2$ tiles share the edges of two cells, both edges count separately. Find a layout whose beauty is as large as possible.

The first line contains four space-separated integers $H$, $W$, $K$, and $N$. The board has $H \times W$ cells, there are $K$ colors, and $N$ tiles are used.

The $i$-th line ($1 \le i \le N$) contains two integers $S_i$ and $C_i$. Tile $i$ has size $1 \times S_i$ and color $C_i$.

The $j$-th line ($1 \le j \le K$) contains $K$ integers $A_{j,1}, A_{j,2}, \ldots, A_{j,K}$. When a tile of color $j$ and a tile of color $k$ share an edge, the score is $A_{j,k}$.

Print $N$ lines. The $i$-th line describes how to place tile $i$.

• If $S_i = 1$, print two integers $A_i$ and $B_i$. The tile covers the cell in row $A_i$ (counted from the top) and column $B_i$ (counted from the left).
• If $S_i = 2$, print four integers $A_i$, $B_i$, $C_i$, and $D_i$. The tile covers the cell in row $A_i$ and column $B_i$, and the cell in row $C_i$ and column $D_i$ (rows counted from the top, columns from the left).

All input data satisfy the following conditions.

• $1 \le H \le 100$
• $1 \le W \le 100$
• $1 \le K \le 100$
• $1 \le N \le 10000$
• $1 \le S_i \le 2$ ($1 \le i \le N$)
• $1 \le C_i \le K$ ($1 \le i \le N$)
• $H \times W = S_1 + S_2 + \cdots + S_N$
• $0 \le A_{j,k} \le 1000$ ($1 \le j \le K$, $1 \le k \le K$)
• $A_{j,k} = A_{k,j}$ ($1 \le j \le K$, $1 \le k \le K$)

In this sample, the board is $3 \times 2$ and 4 tiles are used. The tiles are as follows.

The figure below shows the layout. The numbers in the figure are tile numbers.

The beauty of this design is 26.

• Tile 2 (color 2) and tile 4 (color 1) share an edge, so they score 7.
• Tile 2 (color 2) and tile 1 (color 1) share an edge, so they score 7.
• Tile 4 (color 1) and tile 1 (color 1) share an edge, so they score 2.
• Tile 4 (color 1) and tile 3 (color 3) share an edge, so they score 5.
• Tile 1 (color 1) and tile 3 (color 3) share an edge, so they score 5.