Horizontal Pod Autoscaler (Infrastructure Automation Internship)

A log [1,p,x] directly sets the count of 1-based service p to x, which may decrease it; [2,−1,x] raises every count below x to x. Apply the logs in order and return the final array.

输入格式

The first line contains n m, the second line contains the initial counts, followed by m lines of logs. 1≤n,m≤200000, initial values are 1..10⁹, assigned values are 0..10⁹, and 1≤p≤n.

输出格式

First output n, then output the final n counts.

样例 1

输入：

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

输出：

4
10 30 10 10

样例 2

输入：

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

输出：

5
8 8 20 8 10

样例 3

输入：

1 2
10
2 -1 100
1 1 0

输出：

1
0

样例说明

The answers to the three public examples are, in order: 4 10 30 10 10; 5 8 8 20 8 10; 1 0. The examples were rechecked by independent enumeration, state search, or direct simulation.