You are given an array A of length N and Q tasks.

Each task is of the following type:

LR V: Apply the bitwise$-$and operator with V for all A$,$ where Li$<=$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 lines contains a task in the described format

Output format

$$ Print the final array after performing all the tasks.

Constraints

$1<$ N $<10^5$

$1$