Graphic Layers Merging

You are given N layers, each represented as an M × M matrix where each cell denotes a brightness value. You need to perform a series of merge operations and then answer several queries about pixel brightness.

Each merge operation is a pair of indices (A, B), meaning that for every cell position (i, j), you should update layer A (i.e. the A-th layer) by taking the maximum of its current value and the value from layer B at that same position:

$$\text{layer}_{A}[i][j] = \max(\text{layer}_{A}[i][j], \text{layer}_{B}[i][j]) $$

The operations are performed sequentially in the given order. After performing all operations, you will answer Q queries. Each query consists of three integers L, R, and C, which asks for the brightness value at row R and column C of layer L (all indices are 1-based).

Follow the input/output format strictly. The input is read from standard input, and the output is printed to standard output.

inputFormat

The first line contains four integers: N M K Q, where:

• N is the number of layers.
• M is the number of rows (and columns) in each layer.
• K is the number of merge operations.
• Q is the number of queries.

Then the next N×M lines each contain M integers representing the rows of each layer. The layers are given in order; each layer consists of M consecutive rows.

This is followed by K lines, each containing two integers A and B representing a merge operation (merge layer A with layer B as described).

Finally, there are Q lines, each containing three integers L, R, and C, representing a query on the brightness of the pixel at row R and column C in layer L.

outputFormat

For each query, print the brightness value at the specified position in a separate line.

## sample

3 2 3 2
1 2
3 4
5 6
7 8
1 2
3 4
1 2
1 2
2 3
1 3
1 1 2
2 1 1

6
5

</p>