{"raw_statement":[{"iden":"background","content":"**upd 2023.1.17 数据已加强。** \n\n**upd 2023.10.18 空间限制调整为 100 MiB。**\n\nBessie 正在玩一场卡牌游戏！\n\n这个游戏有一些~~神秘的~~规则。Bessie 需要用一些编程技巧，加快计算。"},{"iden":"statement","content":"牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\\le i\\le N)$\n\n有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\\forall l_i\\le j \\le r_i,a_j\\gets a_j \\lor v_i$。\n\n其中 $\\lor$ 表示按位或操作，即 C++ 中的 `|`。\n\n对于 $i=1,2,\\dots,N$，求出在哪一次操作后，$a_i$ **首次严格大于** $P$，其中 $P$ 为一给定常数。\n\n数据保证在初始情况下，$P\\ge\\max\\{a_i\\}$。"},{"iden":"input","content":"第一行三个整数 $N,Q,P$。\n\n第二行 $N$ 个整数，第 $i$ 个数为 $a_i$ 的初始值。\n\n接下来 $Q$ 行，每行三个整数，$l_i,r_i,v_i$。"},{"iden":"output","content":"输出 $N$ 个数 $id_1,id_2,\\dots,id_N$，第 $i$ 个数表示在第 $id_i$ 次操作后，$a_i$ 首次严格大于 $P$。\n\n**如果 $a_i$ 始终小于等于 $P$，请在这一位输出 $-1$。**"},{"iden":"note","content":"#### 样例 #1 解释\n\n第一次操作后的数列为 $1,2,3,4,5$。\n\n第二次操作后的数列为 $11,2,3,4,5$。\n\n第三次操作后的数列为 $11,6,7,4,5$。\n\n……\n\n最终的数列为 $11,14,15,4,23$。\n\n---\n\n#### 数据范围\n全部数据满足：$1\\le N,Q \\le 10^6$，$1\\le l_i\\le r_i \\le N$，$1\\le a_i,v_i,P\\le 10^9$。\n\n测试点 $1\\sim2$ 另满足 $1\\le N,Q\\le 10^3$。\n\n测试点 $3$ 另满足 $l_i=r_i$。\n\n测试点 $4$ 另满足 $l_i=1,r_i=N$。\n\n测试点 $5\\sim10$ 无额外限制。\n\n**本题数据规模较大，请注意常数优化。**"}],"translated_statement":null,"sample_group":[["5 7 10\n1 2 3 4 5\n1 1 1\n1 1 10\n2 5 4\n2 3 8\n5 5 2\n5 5 1\n5 5 16","2 4 4 -1 7"],["10 10 86\n26 27 33 1 21 31 9 22 17 14\n6 10 76\n5 8 85\n4 5 89\n3 9 87\n2 9 100\n7 10 83\n1 6 75\n1 4 66\n3 10 68\n3 4 72","7 5 4 3 3 1 2 1 1 6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}