P8955 "VUSC" Card Tricks

**upd 2023.1.17 The testdata has been strengthened.** **upd 2023.10.18 The memory limit has been adjusted to 100 MiB.** Bessie is playing a card game. This game has some ~~mysterious~~ rules. Bessie needs to use some programming skills to speed up the computation.

The deck can be seen as a sequence of length $N$, where the value at position $i$ is $a_i$. $(1\le i\le N)$. There are $Q$ operations. Each operation gives $l_i, r_i, v_i$, and for all $l_i\le j \le r_i$, do $a_j\gets a_j \lor v_i$. Here $\lor$ means the bitwise OR operation, i.e. `|` in C++. For $i=1,2,\dots,N$, find after which operation $a_i$ becomes **strictly greater than** $P$ for the first time, where $P$ is a given constant. The testdata guarantees that initially, $P\ge\max\{a_i\}$.

The first line contains three integers $N, Q, P$. The second line contains $N$ integers; the $i$-th number is the initial value of $a_i$. The next $Q$ lines each contain three integers $l_i, r_i, v_i$.

Output $N$ numbers $id_1, id_2, \dots, id_N$. The $i$-th number means that after the $id_i$-th operation, $a_i$ becomes strictly greater than $P$ for the first time. **If $a_i$ is always less than or equal to $P$, output $-1$ at this position.**

#### Sample #1 Explanation After the first operation, the sequence is $1,2,3,4,5$. After the second operation, the sequence is $11,2,3,4,5$. After the third operation, the sequence is $11,6,7,4,5$. …… The final sequence is $11,14,15,4,23$. --- #### Constraints All testdata satisfies: $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$. Test points $1\sim2$ additionally satisfy $1\le N,Q\le 10^3$. Test point $3$ additionally satisfies $l_i=r_i$. Test point $4$ additionally satisfies $l_i=1, r_i=N$. Test points $5\sim10$ have no additional constraints. **The data size of this problem is large, so please pay attention to constant-factor optimizations.** Translated by ChatGPT 5