Robot Boolean Function Tournament

This problem is adapted from ROIR 2020 Day1 T4. In this problem, you are given an m×n table, where each cell has an integer weight. For every column j, the weights form a permutation of {0, 1, …, m−1}. In addition, for each column j a threshold z_j (an integer in [0, m]) is to be chosen by you.

For each row i the following process is executed. First, for each column j set

$$val[j] = [x_{i,j} < z_j]$$

(where [P] equals 1 if the predicate P holds and 0 otherwise). Then a non‐repetitive monotone linear program (NMLP) is evaluated on these bits. The NMLP consists of n−1 instructions. For p=1,…,n−1, the p-th instruction is described by three integers a_p, b_p and op_p (with 1 ≤ a_p, b_p

$$val[n+p] = \begin{cases} val[a_p] \land val[b_p] & \text{if } op_p = 1,\\[5mm] val[a_p] \lor val[b_p] & \text{if } op_p = 2. \end{cases}$$

The final result for row i is val[2n−1]. Your task is to choose the thresholds z₁, z₂, …, z_n so that exactly s rows have final result 1 (and the remaining m−s rows yield 0). It can be proven that at least one solution always exists.

inputFormat

The first line contains three integers m, n and s.

The next m lines each contain n integers. In every column, these m numbers are a permutation of 0, 1, …, m−1.

The following n−1 lines each contain three integers: a_p, b_p and op_p (where op_p=1 indicates logical AND and op_p=2 indicates logical OR) for the p-th instruction (1 ≤ p ≤ n−1, and 1 ≤ a_p, b_p < n+p, with all these values distinct).

outputFormat

Output n integers — the thresholds z₁, z₂, …, z_n that yield exactly s rows with final result equal to 1. If there are multiple solutions, output any one of them.

sample

3 2 0
0 1
2 0
1 2
1 2 1

0 0