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$