蚂蚁搬家
暂无测试数据。
很久很久以前，有很多蚂蚁部落共同生活在一片祥和的村庄里。但在某一天，村庄里突然出现了一只食蚁兽，蚂蚁们为了保全性命而决定搬家。
然而这个村庄四面环山，想要离开这个村庄必须要从地洞里离开，村子里一共有 $2n$ 个地洞，分布在山的左右，一边 $n$ 个。左边的任意一个地洞都可以通到右边 $n$ 个地洞中的任意的一个，如图所示（两侧地洞从上至下编号为 $1$ 到 $n$）。
对于右边的第 $i$ 个出口，附近有数量为 $w_i$ 的食物。
现在前后依次来了 $q$ 个蚂蚁部落，第 $i$ 个部落有 $a_i$ 只蚂蚁，它们会从左边第 $b_i$ 个地洞离开，并且选择一个右侧的出口，出口的食物必须大于等于 $a_i$，如果有多个满足要求的出口，则选择距离 $b_i$ 最近的（假设蚂蚁从右边的编号为 $k$ 的地洞出来，那么距离定义为 $|k-b_i|$）。如果有多个洞口符合要求，选择编号最小的出口离开，并且占据这个出口数量为 $a_i$ 的食物，当前洞口的食物数量减少 $a_i$。
请输出每群蚂蚁会选择哪个出口，如果没有符合要求的出口，输出 $-1$，并且忽略这群蚂蚁。
输入格式
第一行两个整数 $n$ 和 $q$。
接下来 $n$ 行，每行一个整数 $w_i$，表示右方第 $i$ 个洞口的食物数量。
接下来 $q$ 行，每行两个整数 $a_i$ 和 $b_i$，表示蚂蚁数量和它们离开的洞口。
输出格式
一共 $q$ 行，每行一个整数，表示第 $i$ 群蚂蚁会选择哪个出口。
数据规模
对于 $30\%$ 的数据：$n,q \le 3000$。
对于 $60\%$ 的数据：$n,q \le 100000$。
对于另外 $20\%$ 的数据保证：$a_i=1$。
对于 $100\%$ 的数据：$n,q \le 500000$，$a_i,w_i \le 10^9$，$b_i \le n$。
更多样例
样例解释
原始的剩余食物为 $9,8,6,10,5$。
查询 $4,5$，选择第 $5$ 个洞口出来，剩下食物为 $9,8,6,10,1$。
查询 $2,5$，选择第 $4$ 个洞口出来，剩下食物为 $9,8,6,8,1$。
查询 $8,1$，选择第 $1$ 个洞口出来，剩下食物为 $1,8,6,8,1$。
查询 $9,3$，这时候没有满足条件的洞口了，忽略之。
查询 $3,1$，选择第 $2$ 个洞口出来，剩下食物为 $1,5,6,8,1$。
5 5
9 8 6 10 5
4 5
2 5
8 1
9 3
3 1
5
4
1
-1
2