题目描述

译自 ROIR 2020 Day1 T4. Олимпиада для роботов

机器人高速布尔函数计算锦标赛的任务由评委会准备。

机器人的一个任务是一张 $m$ 行 $n$ 列的表格，其中每个格子有一个整数权值，且记第 $i$ 行 $j$ 列的格子的权值为 $x_{i,j}$。
对于每一列，该列中所有格子的权值组成了一个 $0\ldots m-1$ 的排列。换句话说，每列中所有格子的权值互不相同：
若 $i \ne k$，则对于所有的 $j$ 有 $x_{i,j} \ne x_{k,j}$，且有 $0 \le x_{i,j} < m$。

对于每一列，评委会设置了一个阈值 —— 一个在 $[0,m]$ 内的非负整数 $z_j$。你需要以所有形如 $x_{i,j} < z_j$ 的逻辑表达式的值为参数计算布尔函数的值。一个逻辑表达式的值为 $1$ 当且仅当这个表达式成立，否则为 $0$。

在比赛中，选手们需要计算 $m$ 个布尔函数的值 —— 对每一行计算一次。每个布尔函数以一个非重复单调线性规划（NMLP）定义。

考虑第 $i$ 行的 NMLP。
这是由 $n-1$ 条以 $1 \ldots n-1$ 编号的指令组成的一个序列，第 $p$ 条指令给定三个数：$a_p, b_p, op_p$。$op_p$ 只有两种取值：$1$ 表示与运算，$2$ 表示或运算。
而 $a_p,b_p$ 则是第 $p$ 个指令的参数，满足 $1 \le a_p,b_p < n+p$。

考虑一个仅包含 $0$ 和 $1$ 的数组 $val[1\ldots 2n-1]$。对于 $1 \le j \le n$，$val[j] = [x_{i,j} < z_j]$，其中 $[P]$ 表示表达式 $P$ 的值。
而 $val[n+p]$ 的值通过第 $p$ 条指令计算。

• 对于 $op_p = 1$，$val[n+p] = (val[a_p]\ \texttt{and}\ val[b_p])$。
• 对于 $op_p = 2$，$val[n+p] = (val[a_p]\ \texttt{or}\ val[b_p])$。

该规划是非重复的，也就是说，对于 $p = 1\ldots n-1$，所有 $2n-2$ 个 $a_p,b_p$ 的值互不相同。

程序执行的结果即为 $val[2n-1]$。

目前评委会已经准备好了所有的 $x_{i,j}$，需要由你来确定每一列的阈值才能完整地准备这个任务。
评委会认为一个任务是平衡的，当且仅当所有 $m$ 行中恰有 $s$ 行的布尔函数最后得到的结果为 $1$，其余 $m-s$ 行得到 $0$。
你的任务即为替评委会找到合适的阈值。

对于此题，可以证明一定存在至少一种选择阈值的方案满足上述条件。

输入格式

第一行，三个整数 $n,m,s$。
以下 $m(n-1)$ 行，第 $i \cdot (n-1) + p\;(1 \le p \le n-1)$ 行包含三个整数 $a_p,b_p,op_p$，表示第 $i$ 行的第 $p$ 个操作。
以下 $m$ 行，每行 $n$ 个整数，表示所有的 $x_{i,j}$。

输出格式

输出 $n$ 个整数 $z_1, z_2, \ldots, z_n\;(0 \le z_j \le m)$。
如有多解，任意输出一个即可。

4 3 2
1 2 1
3 4 1
5 6 2
1 2 2
3 5 1
4 6 2
1 4 1
2 3 1
5 6 2
0 1 2 2
2 2 1 0
1 0 0 1

0 1 2 3

数据范围与提示

对于 $100\%$ 的数据，$1 \le n,m \le 3 \cdot 10^5,n \cdot m \le 3 \cdot 10^5,0 \le s \le m,1 \le a_p, b_p \le n+p,0 \le x_{i,j} < m$。
具体数据限制如下表：