Andrewid在墙上钉了n颗钉子，编号从1到n，第i颗钉子的坐标是(x_i,0)。
Andrewid喜欢在钉子上用不可伸长的细绳悬挂一个重物，当重物竖直下垂时向右推重物，使重物绕着钉子旋转起来。设重物挂在第i个钉子上，绳子长度为l，则竖直下垂时重物的坐标是(x_i,-l)。重物开始旋转之后，细绳可能会碰到钉子，钉子会阻碍绳子的运动，使重物绕着这个钉子旋转。如果绳子同时碰到了多个钉子，那么重物会绕着与上次的钉子最远的一颗钉子旋转，而旋转的半径也会变成剩下绳子的长度。不妨认为钉子很小，绕过钉子不会减少绳子的长度。特别的，如果剩下的绳子长度为0，重物会绕着这个钉子旋转。
显然，重物最终会绕着某一个钉子一直旋转下去，根本停不下来。Andrewid一共玩了m次，每次都希望你告诉他那颗钉子的编号。Andrewid推重物时力气很大，整个过程中绳子都是绷紧的。

第一行两个整数n,m，表示钉子的数量和Andrewid玩重物的次数。
第二行n个整数x₁,x₂,...,x_n，表示每颗钉子的横坐标。保证互不相同。
接下来m行，每行两个整数a_i,l_i，表示在编号为a_i的钉子下面用长度为l_i的绳子挂了一个重物。

输出m行，第i行输出一个整数，表示玩第i次时最终重物旋转围绕的钉子编号。

样例解释：
第一组

第二组


数据范围：
1<=n,m<=2*10⁵
-10⁹<=x_i<=10⁹
1<=a_i<=n
1<=l_i<=10⁹