Horizontal Pod Autoscaler

Maintain the pod counts of n microservices. Operation 1 sets the count of a given service directly to x (which may increase or decrease it); operation 2 raises the count of every service below x to x. Execute all operations in order and output the final array.

输入格式

The first line contains n, m; the second line contains n initial pods; then m lines follow, each containing typ p x. typ=1 sets 1-based service p directly to x; when typ=2, p must be -1, and max(pods[i],x) is applied to all pods. This site adds 1≤n,m≤200000, 1≤pods[i]≤10^9, 0≤x≤10^9, and defines this stdin/stdout protocol.

输出格式

Output the n final pod counts, separated by spaces.

样例 1

输入：

4 3
2 4 1 4
1 2 30
1 3 4
2 -1 10

输出：

10 30 10 10

样例 2

输入：

5 3
3 50 2 1 10
1 2 0
2 -1 8
1 3 20

输出：

8 8 20 8 10