{"raw_statement":[{"iden":"statement","content":"**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T4.** ***[Олимпиада для роботов\n](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者 alpha1022***\n\n机器人高速布尔函数计算锦标赛的任务由评委会准备。\n\n机器人的一个任务是一张 $m$ 行 $n$ 列的表格，其中每个格子有一个整数权值，且记第 $i$ 行 $j$ 列的格子的权值为 $x_{i,j}$。  \n对于每一列，该列中所有格子的权值组成了一个 $0\\ldots m-1$ 的排列。换句话说，每列中所有格子的权值互不相同：  \n若 $i \\ne k$，则对于所有的 $j$ 有 $x_{i,j} \\ne x_{k,j}$，且有 $0 \\le x_{i,j} < m$。\n\n对于每一列，评委会设置了一个阈值 —— 一个在 $[0,m]$ 内的非负整数 $z_j$。你需要以所有形如 $x_{i,j} < z_j$ 的逻辑表达式的值为参数计算布尔函数的值。一个逻辑表达式的值为 $1$ 当且仅当这个表达式成立，否则为 $0$。\n\n在比赛中，选手们需要计算 $m$ 个布尔函数的值 —— 对每一行计算一次。每个布尔函数以一个**非重复单调线性规划**（NMLP）定义。\n\n考虑第 $i$ 行的 NMLP。  \n这是由 $n-1$ 条以 $1 \\ldots n-1$ 编号的指令组成的一个序列，第 $p$ 条指令给定三个数：$a_p, b_p, op_p$。$op_p$ 只有两种取值：$1$ 表示与运算，$2$ 表示或运算。  \n而 $a_p,b_p$ 则是第 $p$ 个指令的参数，满足 $1 \\le a_p,b_p < n+p$。\n\n考虑一个仅包含 $0$ 和 $1$ 的数组 $val[1\\ldots 2n-1]$。对于 $1 \\le j \\le n$，$val[j] = [x_{i,j} < z_j]$，其中 $[P]$ 表示表达式 $P$ 的值。  \n而 $val[n+p]$ 的值通过第 $p$ 条指令计算。\n - 对于 $op_p = 1$，$val[n+p] = (val[a_p]\\ \\texttt{and}\\ val[b_p])$。\n - 对于 $op_p = 2$，$val[n+p] = (val[a_p]\\ \\texttt{or}\\ val[b_p])$。\n\n该规划是非重复的，也就是说，对于 $p = 1\\ldots n-1$，所有 $2n-2$ 个 $a_p,b_p$ 的值互不相同。\n\n程序执行的结果即为 $val[2n-1]$。\n\n目前评委会已经准备好了所有的 $x_{i,j}$，需要由你来确定每一列的阈值才能完整地准备这个任务。  \n评委会认为一个任务是平衡的，当且仅当所有 $m$ 行中恰有 $s$ 行的布尔函数最后得到的结果为 $1$，其余 $m-s$ 行得到 $0$。  \n你的任务即为替评委会找到合适的阈值。\n\n对于此题，可以证明一定存在至少一种选择阈值的方案满足上述条件。"},{"iden":"input","content":"第一行，三个整数 $n,m,s$。  \n以下 $m(n-1)$ 行，第 $i \\cdot (n-1) + p\\;(1 \\le p \\le n-1)$ 行包含三个整数 $a_p,b_p,op_p$，表示第 $i$ 行的第 $p$ 个操作。  \n以下 $m$ 行，每行 $n$ 个整数，表示所有的 $x_{i,j}$。"},{"iden":"output","content":"输出 $n$ 个整数 $z_1, z_2, \\ldots, z_n\\;(0 \\le z_j \\le m)$。  \n如有多解，任意输出一个即可。"},{"iden":"note","content":"#### 【样例解释】\n在此样例中共有 $3$ 行，你需要令其中恰好两行的函数值为 $1$，另一行的函数值为 $0$。\n让我们看看第一行的 $val$ 数组是什么样的。\n前四个值通过格子中的权值和阈值计算：\n- $val[1] = [x_{1,1} < z_1] = [0 < 0] = 0$；\n- $val[2] = [x_{1,2} < z_2] = [1 < 1] = 0$；\n- $val[3] = [x_{1,3} < z_3] = [2 < 2] = 0$；\n- $val[4] = [x_{1,4} < z_4] = [2 < 3] = 1$。\n\n接下来，对第一行执行线性规划：\n- $val[5] = (val[1]\\ \\texttt{and}\\ val[2]) = (0\\ \\texttt{and}\\ 0) = 0$；\n- $val[6] = (val[3]\\ \\texttt{and}\\ val[4]) = (0\\ \\texttt{and}\\ 1) = 0$；\n- $val[7] = (val[5]\\ \\texttt{or}\\ val[6]) = (0\\ \\texttt{or}\\ 0) = 0$。\n\n因此，第一行的函数值为 $0$。\n顺带一提，若我们整理一下这些式子，可得：\n$$\n[((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))]\n$$\n\n类似地，第二行和第三行的函数值分别为\n$$\n[(((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)]\n$$\n\n和\n$$\n[((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))]\n$$\n\n当我们令 $z_1 = 0,z_2 = 1,z_3 = 2,z_4 = 3$ 时，我们可以得到以下表达式：\n第二行：\n$$\n[(((2 < 0)\\ \\texttt{or}\\ (2 < 1))\\ \\texttt{and}\\ (1 < 2))\\ \\texttt{or}\\ (0 < 3)] = 1\n$$\n\n第三行：\n$$\n[((1 < 0)\\ \\texttt{and}\\ (1 < 3))\\ \\texttt{or}\\ ((0 < 1)\\ \\texttt{and}\\ (0 < 2))] = 1\n$$\n\n请注意这不是唯一的解，可行的解还包括 $z_1 = 0, z_2 = 0, z_3 = 3, z_4 = 3$。\n\n\n#### 【数据范围】\n对于 $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$。  \n具体数据限制如下表：\n\n|子任务编号|限制|分值|\n|:-:|:-:|:-:|\n|$1$|$n \\le 2,m \\le 10^3$|$10$|\n|$2$|$n \\le 2,m \\le 10^5$|$10$|\n|$3$|$n \\le 10,m \\le 2$|$10$|\n|$4$|$x_{i,j} = i-1$|$5$|\n|$5$|$op_p=1$|$5$|\n|$6$|$n \\le 100$|$20$|\n|$7$|每一行的 NMLP 相同|$10$|\n|$8$|-|$30$|"}],"translated_statement":null,"sample_group":[["4 3 2\n1 2 1\n3 4 1\n5 6 2\n1 2 2\n3 5 1\n4 6 2\n1 4 1\n2 3 1\n5 6 2\n0 1 2 2\n2 2 1 0\n1 0 0 1","0 1 2 3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}