题目描述

译自 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

在此样例中共有 $3$ 行，你需要令其中恰好两行的函数值为 $1$，另一行的函数值为 $0$。 让我们看看第一行的 $val$ 数组是什么样的。 前四个值通过格子中的权值和阈值计算：

• $val[1] = [x_{1,1} < z_1] = [0 < 0] = 0$；
• $val[2] = [x_{1,2} < z_2] = [1 < 1] = 0$；
• $val[3] = [x_{1,3} < z_3] = [2 < 2] = 0$；
• $val[4] = [x_{1,4} < z_4] = [2 < 3] = 1$。

接下来，对第一行执行线性规划：

• $val[5] = (val[1]\ \texttt{and}\ val[2]) = (0\ \texttt{and}\ 0) = 0$；
• $val[6] = (val[3]\ \texttt{and}\ val[4]) = (0\ \texttt{and}\ 1) = 0$；
• $val[7] = (val[5]\ \texttt{or}\ val[6]) = (0\ \texttt{or}\ 0) = 0$。

因此，第一行的函数值为 $0$。 顺带一提，若我们整理一下这些式子，可得：

$$[((x_{1,1} < z_1)\ \texttt{and}\ (x_{1,2} < z_2))\ \texttt{or}\ ((x_{1,3} < z_3)\ \texttt{and}\ (x_{1,4} < z_4))]$$

类似地，第二行和第三行的函数值分别为

$$[(((x_{2,1} < z_1)\ \texttt{or}\ (x_{2,2} < z_2))\ \texttt{and}\ (x_{2,3} < z_3))\ \texttt{or}\ (x_{2,4} < z_4)]$$

和

$$[((x_{3,1} < z_1)\ \texttt{and}\ (x_{3,4} < z_4))\ \texttt{or}\ ((x_{3,2} < z_2)\ \texttt{and}\ (x_{3,3} < z_3))]$$

当我们令 $z_1 = 0,z_2 = 1,z_3 = 2,z_4 = 3$ 时，我们可以得到以下表达式： 第二行：

$$[(((2 < 0)\ \texttt{or}\ (2 < 1))\ \texttt{and}\ (1 < 2))\ \texttt{or}\ (0 < 3)] = 1$$

第三行：

$$[((1 < 0)\ \texttt{and}\ (1 < 3))\ \texttt{or}\ ((0 < 1)\ \texttt{and}\ (0 < 2))] = 1$$

请注意这不是唯一的解，可行的解还包括 $z_1 = 0, z_2 = 0, z_3 = 3, z_4 = 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$。
具体数据限制如下表：

子任务编号	限制	分值
$1$	$n \le 2,m \le 10^3$	$10$
$2$	$n \le 2,m \le 10^5$
$3$	$n \le 10,m \le 2$
$4$	$x_{i,j} = i-1$	$5$
$5$	$op_p=1$
$6$	$n \le 100$	$20$
$7$	每一行的 NMLP 相同	$10$
$8$	-	$30$