Problem Description

At the end of the month, the boss of a company prepares a salary distribution plan for the $k$ employees in the company (they are numbered $1 \sim k$). This plan can be represented by a sequence $a$ of length $k$, where $a_i$ denotes the salary of the $i$-th person. Now, this plan is placed on the desk in the office, unattended.

Some employees decide to replace this salary distribution plan so that they can get more salary. So, some employees prepare a forged plan $b$ (also a sequence of length $k$) that will not be noticed by the boss, and choose a moment to sneak into the office. He will peek at the plan $a^{'}$ that is currently on the desk. If this employee’s index is $i$ and $b_i > a^{'}_i$, then he will replace the entire plan with $b$. To ensure the replacement succeeds, an employee may sneak into the office at multiple moments, and may forge different plans. However, at any single moment, at most one employee sneaks into the office.

Assume there are $n$ moments in one day when employees sneak into the office. We number these moments from $1$ to $n$ in time order. Now, you are given, for each moment $t$, the employee $p_t$ who sneaks in and the forged plan $b_t$ he brings at time $t$. You are also given $q$ queries; each query provides the boss’s initial plan. Please compute the final plan left on the desk.

Input Format

The first line contains three integers $n$, $q$, $k$, denoting the number of moments, the number of queries, and the number of employees.

The next $n$ lines each contain $k+1$ integers $p_t, b_{t,1}, \cdots, b_{t_k}$, denoting the employee who sneaks in at time $t$ and the plan he prepares.

The next $q$ lines each contain $k$ integers $a_1, \cdots, a_k$, denoting the boss’s initial plan.

Output Format

Output $q$ lines. Each line contains $k$ integers, denoting the final plan.

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

7 3 5
7 3 5
9 10 6
7 3 5
7 3 5
10 6 10
7 3 5
7 3 5
7 3 5
7 3 5

Hint

Subtasks

There is $20\%$ of the testdata with $n, q \le 1{,}000$.

There is another $10\%$ of the testdata with $k = 1$.

For all testdata, $n, q \le 10^5$, $k \le 20$.

Notes

The input and output size of this problem is large. It is recommended to use scanf/printf for I/O. If you use cin/cout, it is recommended to add std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); at the beginning of the main function.

Translated by ChatGPT 5