题目背景

upd 2023.1.17 20:44 数据已加强。赛时的乱搞应该全部卡掉了。

Bessie 正在玩一场卡牌游戏！

这个游戏有一些神秘的规则。Bessie 需要用一些编程技巧，加快计算。

题目描述

牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\le i\le N)$

有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\forall l_i\le j \le r_i,a_j\gets a_j \lor v_i$。

其中 $\lor$ 表示按位或操作，即 C++ 中的 |。

对于 $i=1,2,\dots,N$，求出在哪一次操作后，$a_i$ 首次严格大于 $P$，其中 $P$ 为一给定常数。

数据保证在初始情况下，$P\ge\max\{a_i\}$。

输入格式

第一行三个整数 $N,Q,P$。

第二行 $N$ 个整数，第 $i$ 个数为 $a_i$ 的初始值。

接下来 $Q$ 行，每行三个整数，$l_i,r_i,v_i$。

输出格式

输出 $N$ 个数 $id_1,id_2,\dots,id_N$，第 $i$ 个数表示在第 $id_i$ 次操作后，$a_i$ 首次严格大于 $P$。

如果 $a_i$ 始终小于等于 $P$，请在这一位输出 $-1$。

5 7 10
1 2 3 4 5
1 1 1
1 1 10
2 5 4
2 3 8
5 5 2
5 5 1
5 5 16

2 4 4 -1 7

10 10 86
26 27 33 1 21 31 9 22 17 14
6 10 76
5 8 85
4 5 89
3 9 87
2 9 100
7 10 83
1 6 75
1 4 66
3 10 68
3 4 72

7 5 4 3 3 1 2 1 1 6

提示

样例 #1 解释

第一次操作后的数列为 $1,2,3,4,5$。

第二次操作后的数列为 $11,2,3,4,5$。

第三次操作后的数列为 $11,6,7,4,5$。

……

最终的数列为 $11,14,15,4,23$。

---

数据范围

全部数据满足：$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$。

测试点 $1\sim2$ 另满足 $1\le N,Q\le 10^3$。

测试点 $3$ 另满足 $l_i=r_i$。

测试点 $4$ 另满足 $l_i=1,r_i=N$。

测试点 $5\sim10$ 无额外限制。

本题数据规模较大，请注意常数优化。