You are given an array \(A\) of length \(N\). You are also given \(Q\) tasks.

Each task is of the following type:

L R V: Apply the bitwise-and operator with V for all \(A_{i} \; where \; L \le i \le R\)

You need to print the array after performing all the tasks.

Input format

First line: Two integers, \(N\) (denoting the length of array) and \(Q\) (denoting the number of tasks)
Second line: \(N\) space-separated elements of the array
Each of the following \(Q\) lines contains a task in the described format

Output format

Print the final array after performing all the \(Q\) tasks.

Constraints

\(1 \le N \le 10^{5}\)

\(1 \le Q \le 2*10^{5}\)

\(1 \le A_{i},V \le 10^{9}\)

\(1 \le L \le R \le N\)