Bitwise OR Card Operations

You are given an array of N cards, where the card at position i (1 ≤ i ≤ N) has an initial value a_i. You are also given a constant P such that P ≥ max(a_i) initially.

There are Q operations. In the i-th operation, you are given three integers l_i, r_i, and v_i. For every index j satisfying l_i ≤ j ≤ r_i, the value of the card is updated as follows:

\( a_j \gets a_j \lor v_i \)

where \( \lor \) denotes the bitwise OR operation (as in C++ using the | operator).

Your task is to determine, for each card (i.e. for each index from 1 to N), the index of the operation after which the card's value becomes strictly greater than P for the first time. If a card's value never becomes strictly greater than P after all operations, output -1 for that card.

inputFormat

The first line contains three integers N, Q, and P.

The second line contains N integers, representing the initial values of the cards: a₁, a₂, …, a_N.

Each of the following Q lines contains three integers l_i, r_i, v_i representing an operation.

outputFormat

Output N integers in one line, where the i-th integer is the index of the operation after which a_i becomes strictly greater than P for the first time. If it never becomes greater than P, output -1 for that card.

sample

5 3 5
1 2 3 4 5
1 3 1
2 5 2
1 5 4

-1 3 3 2 2