Colored Tiles 2

In 2018, the International Olympiad in Informatics will be held in Japan. To celebrate, 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. The designers of JOI proposed the following:

• The artwork is made on a rectangular board with H × W cells. We pave the board with N tiles. The tiles do not overlap.
• The size of tile i (1 ≤ i ≤ N) is either 1 × 1 or 1 × 2. The color of tile i is Ci.
• We may rotate a 1 × 2 tile and use it as a 2 × 1 tile.

They also proposed the kinds of tiles for the artwork. However, they did not propose how to pave the tiles on the board, which is the most important part of the design. Because the designs JOI proposes are always beautiful, the committee decided to follow JOI's proposal for the kinds of tiles. The committee has to decide how to pave the tiles on the board. The committee decided to pave the tiles so as 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, its score is Aj,k.
• The beauty of the design is the total sum of the scores of the edges of the cells on the board.

If two 1 × 2 tiles share the edges of two cells, we count the scores of these two edges independently. You are to find a way to pave the tiles on the board whose beauty is as large as possible.

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

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

• The first line contains four space-separated integers H, W, K, N. The rectangular board consists of H × W cells, there are K kinds of colors of the tiles, and N tiles are used in the design.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains two space-separated integers Si, Ci. The size of tile i is 1 × Si, and the color of tile i is Ci.
• The j-th line (1 ≤ j ≤ K) of the following K lines contains K space-separated integers Aj,1, Aj,2, . . . , Aj,K. When two tiles with color j and color k share an edge, the score is Aj,k.

Submit an output data file for each input data file. The output data file consists of N lines. The i-th line (1 ≤ i ≤ N) describes how to place tile i on the board in the following format.

• When Si = 1, the i-th line should contain two space-separated integers Ai, Bi. Tile i is placed on the cell in the Ai-th row from the top and the Bi-th column from the left.
• When Si = 2, the i-th line should contain four space-separated integers Ai, Bi, Ci, Di. Tile i is placed on the board so that it covers the cell in the Ai-th row from the top and the Bi-th column from the left, and the cell in the Ci-th row from the top and the Di-th column from the left.

All input data satisfy the following conditions.

• 1 ≤ H ≤ 100.
• 1 ≤ W ≤ 100.
• 1 ≤ K ≤ 100.
• 1 ≤ N ≤ 10 000.
• 1 ≤ Si ≤ 2 (1 ≤ i ≤ N).
• 1 ≤ Ci ≤ K (1 ≤ i ≤ N).
• H × W = S1 + S2 + . . . + SN.
• 0 ≤ Aj,k ≤ 1 000 (1 ≤ j ≤ K, 1 ≤ k ≤ K).
• Aj,k = Ak,j (1 ≤ j ≤ K, 1 ≤ k ≤ K).

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

There is a 1 × 1 tile with color 1, a 1 × 2 tile with color 2, a 1 × 1 tile with color 3, and a 1 × 2 tile with color 1.

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

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

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