JOI 艺术博物馆计划举办一场画展。博物馆拥有 $N$ 幅画，编号为 $1$ 到 $N$，第 $i$ 幅画（$1 \le i \le N$）的美感度为 $A_i$。在展览中，这些画将从左到右排成一行，但具体的排列顺序尚未确定。

将有 $M$ 本杂志对展览进行报道。这些杂志按影响力从大到小编号为 $1$ 到 $M$。每本杂志将刊登排列中某一段连续画作的照片。具体而言，杂志 $j$（$1 \le j \le M$）将刊登从左起第 $L_j$ 幅到第 $R_j$ 幅画的照片。杂志 $j$（$1 \le j \le M$）文章的吸引力定义为它所覆盖画作中的最大美感度。

JOI 君作为 JOI 艺术博物馆的馆长，旨在安排画作的顺序，使得这些杂志能够写出吸引力更大的文章，从而吸引更多人参观展览。由于影响力越大的杂志覆盖的受众越广，他希望优先提高影响力较大的杂志文章的吸引力。更准确地说，令 $b_j$ 为杂志 $j$（$1 \le j \le M$）文章的吸引力，JOI 君希望安排画作顺序，使得序列 $b = (b_1, b_2, \dots, b_M)$ 在字典序下最大。这里，对于两个不同的序列 $b = (b_1, b_2, \dots, b_M)$ 和 $b' = (b'_1, b'_2, \dots, b'_M)$，若在第一个使得 $b_k \neq b'_k$ 的索引 $k$（$1 \le k \le M$）处满足 $b_k > b'_k$，则称 $b$ 在字典序下大于 $b'$。

请编写一个程序，在给定画作信息和杂志覆盖范围的情况下，计算当画作排列使得序列 $b = (b_1, b_2, \dots, b_M)$ 的字典序最大时，每本杂志文章的吸引力。

输入格式

从标准输入读取以下数据：

$N \ M$ $A_1 \ A_2 \ \dots \ A_N$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_M \ R_M$

输出格式

向标准输出写入 $M$ 行。第 $j$ 行（$1 \le j \le M$）应包含 $b_j$，即杂志 $j$ 文章的吸引力。这里，序列 $b = (b_1, b_2, \dots, b_M)$ 必须在字典序下最大。

数据范围

• $1 \le N \le 100\,000$。
• $1 \le M \le 100\,000$。
• $1 \le A_i \le N$（$1 \le i \le N$）。
• $1 \le L_j \le R_j \le N$（$1 \le j \le M$）。
• 给定值均为整数。

子任务

1. (19 分) $N \le 400, M \le 400$。
2. (9 分) $N \le 400$。
3. (19 分) $A_i \le 5$（$1 \le i \le N$）。
4. (12 分) $A_i = i$（$1 \le i \le N$）。
5. (17 分) 对于每个 $k$（$1 \le k \le N$），满足 $A_i = k$ 的 $i$（$1 \le i \le N$）的数量最多为 $5$。
6. (24 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

2
2
1
2

说明

当画作按从左到右的顺序 $2, 3, 4, 1$ 排列时，各杂志文章的吸引力确定如下：

• 杂志 1：覆盖第 2 幅画。由于该画美感度为 2，文章吸引力为 2。
• 杂志 2：覆盖第 3 和第 4 幅画。由于这些画的美感度分别为 1 和 2，文章吸引力为 2。
• 杂志 3：覆盖第 1 幅画。由于该画美感度为 1，文章吸引力为 1。
• 杂志 4：覆盖第 4 和第 1 幅画。由于这些画的美感度分别为 2 和 1，文章吸引力为 2。

因此，序列 $b$ 为 $(2, 2, 1, 2)$。由于不存在能使序列字典序更大的画作排列，输出应为 $2, 2, 1, 2$，每行一个。

样例输入 2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

样例输出 2

4
4
3
2
4
1
1
3

样例输入 3

12 10
6 2 2 5 2 5 2 3 3 3 2 2
3 5
10 12
12 12
2 4
8 9
10 11
1 3
7 9
9 10
10 11

样例输出 3

6
5
5
6
5
3
6
5
5
3