高速布尔函数计算锦标赛的评审团正在为机器人选手准备题目。

机器人题目是一张 $m$ 行 $n$ 列的表格，每个单元格中包含一个整数。记第 $i$ 行第 $j$ 列的数为 $x_{i,j}$。每一列中的数值构成 $0$ 到 $m-1$ 的一个排列。也就是说，对于任意 $j$，该列中所有数互不相同，并且满足：

$$0\le x_{i,j}<m.$$

对每一列，还会给定一个阈值 $z_j$，其中 $z_j$ 是 $0$ 到 $m$ 之间的非负整数。机器人需要计算的布尔函数的输入变量为表达式：

$$x_{i,j}<z_j.$$

若不等式成立，则该逻辑表达式值为 $1$，否则为 $0$。

比赛过程中，选手需要计算 $m$ 个布尔函数，每一行对应一个函数。每个布尔函数用一个无重复单调线性程序表示。

考虑第 $i$ 行对应的程序。它包含 $n-1$ 条指令，编号为 $1$ 到 $n-1$。第 $p$ 条指令由三个数 $a_p,b_p,op_p$ 给出。$op_p$ 有两种取值：

• $op_p=1$ 表示 and，即逻辑与；
• $op_p=2$ 表示 or，即逻辑或。

$a_p,b_p$ 是第 $p$ 条指令的参数编号，满足：

$$1\le a_p,b_p<n+p.$$

定义数组 $val[1..2n-1]$，其中每个值均为 $0$ 或 $1$。首先根据阈值初始化：

$$val[j]=\begin{cases} 1,&x_{i,j}<z_j,\\ 0,&\text{否则}. \end{cases}$$

然后根据第 $p$ 条指令计算 $val[n+p]$：

• 若 $op_p=1$，则

$$val[n+p]=val[a_p]\ \text{and}\ val[b_p].$$

• 若 $op_p=2$，则

$$val[n+p]=val[a_p]\ \text{or}\ val[b_p].$$

程序是无重复的，即所有 $2n-2$ 个参数 $a_p,b_p$ 两两不同。换句话说，每个已有值至多作为某一条后续指令的输入使用一次。

程序运行结果为 $val[2n-1]$。

评审团已经准备好了表格 $x_{i,j}$，并为每一行选择了对应的布尔函数及其线性程序。现在还需要为每一列选择阈值。若恰好有 $s$ 个程序返回 $1$，其余 $m-s$ 个程序返回 $0$，则评审团认为这个题目是平衡的。

你的任务是找到一组阈值 $z_1,z_2,\ldots,z_n$，使得恰好 $s$ 个给定函数的值为 $1$。可以证明，在本题限制下，一定存在符合要求的阈值。

输入格式

第一行包含三个整数 $n,m,s$。

$$1\le n\le 3\cdot 10^5, \qquad 1\le m\le 3\cdot 10^5, \qquad n\cdot m\le 3\cdot 10^5, \qquad 0\le s\le m.$$

接下来有 $m$ 个程序块，每个程序块包含 $n-1$ 行，表示表格中某一行对应的无重复单调线性程序。每个程序块的第 $p$ 行包含三个整数：

$$a_p,b_p,op_p.$$

满足：

$$1\le a_p<n+p, \qquad 1\le b_p<n+p, \qquad op_p\in\{1,2\}.$$

保证同一个程序块中所有 $a_p,b_p$ 两两不同。

最后 $m$ 行给出表格。第 $i$ 行包含 $n$ 个整数，第 $j$ 个整数为 $x_{i,j}$。

$$0\le x_{i,j}\le m-1.$$

保证每一列中的数两两不同，即若 $i\ne k$，则对所有 $j$ 都有：

$$x_{i,j}\ne x_{k,j}.$$

输出格式

输出 $n$ 个整数：

$$z_1,z_2,\ldots,z_n.$$

其中：

$$0\le z_j\le m.$$

如果有多组答案，输出任意一组即可。

子任务

子任务	分值	附加限制	必须通过的子任务	反馈
1	10	$n\le 2,\ m\le 10^3$	-	第一处错误
2		$n\le 2,\ m\le 10^5$	1
3		$n\le 10,\ m\le 2$	-
4	5	$x_{i,j}=i-1$
5		所有操作均为 and
6	20	$n\le 100$	1, 2, 3
7	10	所有行的无重复单调线性程序完全相同	-
8	30	无	1–7

样例

样例输入

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$ 行表格，每一行对应一个布尔公式。需要找到 $4$ 个阈值，使得恰好两个公式返回 $1$，另一个返回 $0$。

对第一行，阈值为 $z_1=0,z_2=1,z_3=2,z_4=3$ 时，初始输入为：

• $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]\ \text{and}\ val[2])=0$；
• $val[6]=(val[3]\ \text{and}\ val[4])=0$；
• $val[7]=(val[5]\ \text{or}\ val[6])=0$。

因此第一行的布尔函数结果为 $0$。

第二行对应公式：

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

第三行对应公式：

$$(((x_{3,1}<z_1)\ \text{and}\ (x_{3,4}<z_4))\ \text{or}\ ((x_{3,2}<z_2)\ \text{and}\ (x_{3,3}<z_3))).$$

代入样例输出的阈值后，第二行和第三行的函数值均为 $1$，第一行为 $0$。

这不是唯一答案，例如 $z_1=0,z_2=0,z_3=3,z_4=3$ 也满足要求。