暂无测试数据。

春节假期，小蒜公园的人气非常火爆，为了不影响交通，公园提前在门口修筑了地下通道。

已知，公园在马路左边修建了 $n$ 个地下通道的入口，在右边修建了 $n$ 个出口，直通售票处，左右两边分别自上而下标记为 $1\sim n$。行人可以通过地下通道从任意入口进入，并且从任意出口出去。公园开园时，第 $i$ 个售票处有 $w_i$ 张门票。

景区开园了，依次来了 $q$ 个旅游团，第 $i$ 个旅游团中有 $a_i$ 个人，他们会从左边第 $b_i$ 个通道进入地下通道，他们需要选择一个出口，需要满足选择的出口连通的售票处剩余的票数 $\geq a_i$，如果有多个出口满足条件，则选择距离 $b_i$ 最近的出口（假设从 $k$ 出去，则距离为：$|b_i - k|$），如果还有多个出口满足条件，则选择编号最小的出口。这个旅游团通过售票处后，售票处的门票数量要减少 $a_i$。

请你计算出每个旅游团从哪一个出口出去，如果没有符合要求的出口，则输出 $-1$，并忽略这个旅游团。

输入格式

第一行输入两个正整数 $n,q$ 表示地下通道左右两边出口、入口的数量和旅游团的数量。

接下来一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个售票处门票的数量。

接下来 $q$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 个旅游团的人数为 $a_i$，从第 $b_i$ 个入口进入。

输出格式

输出共 $q$ 行，第 $i$ 行，表示第 $i$ 个旅游团要从哪个出口出去，如果没有满足条件的出口，则输出 $-1$。

数据范围

对于 $30\%$ 的数据，$1\leq n,q\leq 3000$；

对于 $60\%$ 的数据，$1\leq n,q\leq 10^5$；

对于另外 $20\%$ 的数据，保证 $a_i = 1$；

对于 $100\%$ 的数据，$1\leq n,q\leq 5\times 10^5, 0\leq a_i, w_i\leq 10^9, 0\leq b_i \leq n$；

5 5
9 8 6 10 5
4 5
2 5
8 1
9 3
3 1

5
4
1
-1
2