Mystery Table Position Finder

Scarlet has a mysterious \(n\times m\) table. She fills this table with consecutive positive integers starting from \(1\) in the following manner: she begins from a certain cell in the first row and then proceeds from left to right, and then top to bottom until the last row is filled.

However, the filling does not necessarily start at column \(1\) of row \(1\); it starts at an unknown column \(x\) in the first row. Hence, the first row has its cells from column \(x\) to column \(m\) filled, and every subsequent row is filled completely from column \(1\) to column \(m\). Thus, the total number of filled cells is given by \[ T = (m - x + 1) + (n-1)\cdot m. \]

To help you determine the value of \(x\), Scarlet provides you with \(s\) groups of consecutive numbers that lie in the same row of the filled table. For each such group, you are given three integers \(r\), \(c\), and \(k\). This means that in the \(r\)th row, at column \(c\), the value in the table is \(k\). Note that since the numbers in any filled row are consecutive, the following holds:

• If \(r = 1\): the value at column \(c\) is \(c - x + 1\), so \(x = c - k + 1\).
• If \(r \ge 2\): the row is completely filled and the value at column \(c\) is \((m - x + 1) + (r-2)\cdot m + c\), so \(x = m + 1 + (r-2)\cdot m + c - k\).

After that, Scarlet will ask you \(q\) queries. In each query, you are given a number and you must determine its position (row and column) in the table.

inputFormat

The input is given as follows:

n m s q
r1 c1 k1
... (s lines in total)
query1
...
queryq

Here, the first line contains four integers \(n\), \(m\), \(s\), and \(q\), where \(n\) and \(m\) are the dimensions of the table. The next \(s\) lines each contain three integers \(r\), \(c\), and \(k\) representing that in the \(r\)th row at column \(c\), the value is \(k\) (this cell belongs to a group of consecutive numbers in that row). The following \(q\) lines each contain a single integer representing a query number.

outputFormat

For each query, output two integers separated by a space that represent the row and column where the queried number is located. It is guaranteed that the query numbers are valid (i.e. between \(1\) and \(T\), the total number of filled cells).

sample

3 5 1 4
1 3 2
1
8
14
5

1 2
2 4
3 5
2 1