我们知道ZYC到处种满了桃子树，但是桃子树太占位置了，所以ZYC的桃子树全被砍了。

愤怒的ZYC决定开始种姜，他在 $702$ 的土地上种满了 $n$ 颗姜，每颗姜的初始高度为 $a_i$ ,为了使得姜长得更高，ZYC决定拔姜助长，他开始对姜施展魔法！他希望施法后 $n$ 颗姜中最矮的姜的高度尽可能高。

据 $702$ 史书记载，ZYC拥有两种魔法：

• 把某颗姜的高度拔高 $1$ 个单位，可施展至多 $x$ 次；

• 把某颗姜的高度变成指定高度，可施展至多 $y$ 次。

现在问题来了，对于给定的 ${x,y}$ ，在ZYC施法之后，所有姜中最矮的姜会长多高？

具体来说，一共有 $m$ 次询问，每次询问由 ${x_i,y_i}$ 组成，每次询问后，输出施法后所有姜中最矮的姜会长多高。注意，每次询问之间相互独立，也就是下次询问开始前，所有姜的高度都会恢复初始高度。

第一行输入两个整数 $n,m\ (1\le n,m\le 10^5)$，表示姜的个数以及询问次数。
第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$，表示 $n$ 颗姜的初始高度。
接下来输入 $m$ 行，每行两个整数 $x_i,y_i\ (0\le x_i\le 10^{18},0\le y_i\lt n)$，表示两种魔法的施法次数上限。

输出共 $m$ 行，每行输出一个整数，表示对于给定的 $x_i,y_i$ 施法后最矮的姜的高度。