Discount Events

This problem has the same operation semantics as DoorDash #1 Adjust Prices; it keeps the original number #4 and its company tag. Operation 1 x v sets item x to v; operation 2 v v raises the prices below v to v. The original example is kept as public example 1, and this site adds two more examples. The bounds and input protocol explicitly listed on the page are all CSWork supplements.

输入格式

The first line contains n q, the second line contains n initial prices, and each of the next q lines contains three integers. Operation 1 x v is a point assignment; operation 2 v v is a global lower bound (the third v is repeated per the source format). CSWork-supplemented ranges: 1≤n,q≤100000, and all prices and v are in 1..10^9; indices start from 1.

输出格式

Output the n prices after executing all operations in order.

样例 1

输入：

3 3
7 5 4
2 6 6
1 2 9
2 8 8

输出：

8 9 8

样例 2

输入：

1 2
1
1 1 9
2 4 4

输出：

9

样例 3

输入：

2 2
10 20
2 10 10
1 1 1

输出：

1 20

样例说明

The editorial is written separately for this number and its original example.