Discount Events (Range Floor Update + Point Set)

Given an array of item prices, execute queries of three columns in order. 1 x v: set the price of item x directly to v, which may lower it; 2 v r: set every price to max(price,v), where the third column r is an unused placeholder. Output the prices after all queries.

输入格式

Input, in order, n, n initial prices, q, and q lines of three-integer queries. Full original ranges: 1≤n,q≤200000, 0≤initial prices and valid v≤1000000000, point index 1≤x≤n. The original text did not give a separate numeric bound for the third placeholder of type2; this site interprets it per the original Java int[][] as −2147483648..2147483647, ignores its value, and does not require it to equal the threshold. The standard input is an explicit arrangement of the original function parameters.

输出格式

Output the n final prices in the original item order, separated by whitespace.

样例 1

输入：

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

输出：

8 9 8

样例 2

输入：

5
1 2 3 4 5
5
1 3 4
1 5 1
2 3 3
1 1 1
1 2 2

输出：

1 2 4 4 3

样例 3

输入：

4
9 6 3 1
2
2 8 8
2 11 11

输出：

11 11 11 11

样例说明

The 001 original example keeps 8 9 8. In 006 Sample0, the third item of the original output, 3, is wrong; with the original five queries it should be 1 2 4 4 3; the intermediate state after the global floor 3 should be 3 3 4 4 3, and later point assignments can lower values again. The four 11s of Sample1 are correct, but keeping 1 at the end of the original explanation is wrong; writing 1 or 11 in the third column of type2 does not affect the result. The full basis for the corrections is in the editorial.