在即将到来的假期里，许多人都想去进行一次难忘的旅行。为了充分享受旅程，每个人都希望和一群朋友一起去。一家旅行社提供了若干次旅行。旅行社提供团体旅行，但对于每次旅行，团体的规模是有限制的：给出了人数的最小值 and 最大值。每个团体只能选择一次旅行。此外，每次旅行只能被一个团体选择。旅行社向你寻求帮助。他们希望组织尽可能多的旅行。你的任务是将人群团体与旅行进行匹配，使得能够组织的旅行数量最大。

写一个程序：

• 从标准输入读取团体和旅行的描述，
• 以使安排的旅行数量达到最大化的方式匹配团体和旅行，
• 将结果写入标准输出。

如果有多种可能的解决方案，你的程序应该输出其中任意一种。

输入格式

输入的第一行包含两个整数：$n$ 和 $m$，由单个空格分隔，$1 \le n \le 400000$，$1 \le m \le 400000$；$n$ 是团体的数量，$m$ 是旅行的数量。团体从 $1$ 到 $n$ 编号，旅行从 $1$ 到 $m$ 编号。

接下来的 $n$ 行包含团体的人数，每行一个。第 $i + 1$ 行包含整数 $s_i$ —— 第 $i$ 个团体的规模，$1 \le s_i \le 10^9$。

接下来的 $m$ 行包含旅行的描述，每行一次旅行。第 $n + j + 1$ 行包含两个整数：$l_j$ 和 $u_j$，由单个空格分隔。$l_j$ 是该旅行可以安排的团体人数的最小值，$u_j$ 是最大值，$1 \le l_j \le u_j \le 10^9$。

输出格式

输出的第一行应包含一个整数 $k \ge 0$ —— 可以安排的最大旅行数量。

接下来的 $k$ 行应包含匹配的描述。这些行中的每一行都应包含一对由单个空格分隔的整数：团体的编号和旅行的编号。

可能有多种答案，你的程序可以打印其中任意一种。

样例

输入格式 1

5 4
54
6
9
42
15
6 6
20 50
2 8
7 20

输出格式 1

3
2 1
3 4
4 2