Background

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.

Problem Description

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\}$.

Input Format

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 Format

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.

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

Hint

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