Adjust Prices

Execute the operations in order: 1 x v changes the price of item x to v; 2 v 0 raises every price below v to v. The original problem writes the second type of operation as 2 v v; because the last two fields duplicate each other, this site normalizes it to 2 v 0, and the second field v still denotes the global lower bound.

输入格式

n q (1≤n,q≤100000), the initial price array, then q lines of operations. Prices are in 1..10⁹, and point indices are 1-based.

输出格式

Output the final prices.

样例 1

输入：

3 3
3 1 8
2 5 0
1 2 2
2 7 0

输出：

7 7 8

样例 2

输入：

1 2
1
1 1 9
2 4 0

输出：

9

样例 3

输入：

2 2
10 20
2 10 0
1 1 1

输出：

1 20