时空限制

1S/512M

题目描述

在一个走廊上安装了 $n$ 盏灯，编号为 $1, 2, \dots, n$。

每盏灯都有一个圆形开关。第 $i$ 盏灯共有 $h_i$ 个挡位，编号依次为 $0, 1, \dots, h_i-1$。

拨动开关的规则如下：

• 如果当前挡位小于 $h_i-1$，拨动一下后，挡位编号会加 $1$；
• 如果当前挡位恰好是 $h_i-1$，拨动一下后，挡位会回到 $0$。

初始时，所有灯的挡位均为 $0$。现在进行 $Q$ 次操作，每次操作给定一个区间 $[l, r]$，电工会将该区间内所有灯的开关各拨动一下。

请输出所有操作完成后，每盏灯最终所在的挡位编号。

格式

输入格式

第一行包含两个整数 $n, Q$，分别表示灯的数量和操作的次数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $h_i$，即第 $i$ 盏灯的开关挡位总数。

接下来 $Q$ 行，每行包含两个整数 $l, r$，描述了一次操作的区间。

输出格式

输出一行，包含 $n$ 个整数，用空格隔开，依次表示第 $1, 2, \dots, n$ 盏灯的开关最终所在的挡位编号。

样例

样例输入 #1

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

样例输出 #1

1 0 1 2 1

样例解释 #1

• 一开始时，挡位分别为 $[0,0,0,0,0]$。
• 第 $1$ 次操作后档位分别为 $[1,1,1,0,0]$。
• 第 $2$ 次操作后档位分别为 $[1,0,0,1,0]$。
• 第 $3$ 次操作后档位分别为 $[1,0,1,2,1]$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100 \%$ 的数据，$1 \le n, Q \le 2 \times 10^5$，$2 \le h_i \le 9$，$1 \le l \le r \le n$。