Discount Events

Operation 1 x v sets the price of item x directly to v (it may decrease); operation 2 v v raises every price below v to v. Execute them in the given order and output the final array.

输入格式

The first line contains n q, the second line contains n prices, followed by q lines of operations. Indices are 1-based, and the two values after type 2 are equal. This site sets 1≤n,q≤100000, and all prices and v are in 1..10⁹.

输出格式

Output the n final prices.

样例 1

输入：

2 2
1 9
2 5 5
1 2 2

输出：

5 2

样例 2

输入：

2 2
10 1
1 1 3
2 7 7

输出：

7 7

样例 3

输入：

1 3
5
1 1 2
1 1 9
2 6 6

输出：

9

样例说明

Example 1: after the floor the prices are 5, 9, then the second item is lowered to 2, so the final result is 5 2. Example 2: first 3, 1, then a uniform floor gives 7 7. Example 3: the final point assignment of 9 is not lowered by the floor 6, so the answer is 9.