商队路线是一系列相隔不到一天路程的露营地。露营地可以是几乎没有水的干营地，也可以是水源充足、或许还有动物饲料的绿洲。商队旅行总是从一个绿洲出发，在另一个绿洲结束，且从不返回之前的营地。

商队旅行由目的地绿洲和到达该目的地所需的天数定义。例如，如果绿洲位于营地 2、3、5、7、11 等处，且商队想要在 10 天后到达营地 7，商队可以等待 3 天然后直接前往营地 7，或者立即出发并在营地 7 等待 3 天，或者在营地 2、3 和 5 处各等待 1 天。商队旅行计划是指每天选择停留在哪个营地。例如，在 2、3、5 处各等待 1 天会得到旅行计划 1, 2, 2, 3, 3, 4, 5, 5, 6, 7。

编写一个程序，输入商队路线上的绿洲位置以及商队旅行的目的地和天数，输出不同旅行计划的数量。

例如：当绿洲位于营地 2、3、5、7、11 时，前往营地 5 的 7 天旅行共有 10 种旅行计划，如下所示（0 表示在起点休息）。

0012345, 0122345, 0123345, 0123455, 1222345, 1223345, 1223455, 1233345, 1233455, 1234555

输入格式

输入包含多行。第一行包含两个空格分隔的十进制整数 $N$ 和 $M$，其中 $N$ 是指定的绿洲位置数量，$M$ 是需要计算旅行计划数量的商队旅行次数（$5 \le N \le 20$，$1 \le M \le 10$）。

第二行包含 $N$ 个空格分隔的十进制整数，表示到达每个绿洲所需的天数 $O_n$，按递增顺序排列（$O_{n-1} < O_n$，$1 \le O_n \le 60$）。

接下来的 $M$ 行，每行包含两个空格分隔的十进制整数 $D_m$ 和 $T_m$，其中 $D_m$ 是列表中目的地绿洲的索引，$T_m$ 是到达该目的地所需的天数（$1 \le D_m \le N$，$O[D_m] \le T_m \le 60$）。

输出格式

输出共有 $M$ 行。第 $k$ 行输出一个十进制整数，表示对于第二行输入的营地路线，按照第 $k+2$ 行输入的旅行要求所能产生的不同旅行计划的数量。

样例

样例输入 1

5 1
2 3 5 7 11
3 7

样例输出 1

10

样例输入 2

8 3
2 3 5 7 11 13 17 19
3 7
5 15
8 24

样例输出 2

10
126
1287