Andrej 是一位典型的现代学生，梦想着有一天能买得起房。由于购买不动产绝非易事，他正在规划自己的人生，试图弄清楚他到底能在何时以何种方式负担得起一套房。为了买房，他打算申请一笔抵押贷款，这笔贷款需要在未来几个月内分期偿还。在接下来的 $n$ 个月里，他每个月都有收入 $a_i$，这些收入可以用于偿还抵押贷款（其他开支已经计算在内，因此 $a_i$ 可能是负数）。他现在正在查看各种房产和抵押贷款列表，试图找出他能负担得起哪一个。

假设他申请了一笔抵押贷款，需要在 $k$ 个月内每月支付 $x$ 单位的钱，从第 $i$ 个月开始，到第 $i + k - 1$ 个月结束。在这几个月中的每一个月，他都需要能够支付 $x$ 单位的钱。如果他在第 $i$ 个月有剩余收入，即 $a_i > x$，他可以将剩余部分存起来，用于支付未来的部分款项（第 $i+1$ 到 $i+k-1$ 个月的情况相同）。但是，他不能指望在第 $i$ 个月之前存下任何钱，无论那些月份的收入如何。他会把那些钱全部花在当前的房租和牛油果吐司上。

给定 Andrej 未来 $n$ 个月的收入列表以及 $m$ 个不同的时间区间。第 $i$ 个时间区间由两个数字 $s_i$ 和 $k_i$ 定义。抵押贷款从第 $s_i$ 个月开始，持续 $k_i$ 个月，即最后一次还款是在第 $s_i + k_i - 1$ 个月。对于每一个时间区间，确定 Andrej 能负担得起的最大月还款额。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示月数和不同时间区间的数量。第二行包含 $n$ 个空格分隔的整数 $a_1, \dots, a_n$，表示 Andrej 未来 $n$ 个月的收入。接下来有 $m$ 行描述不同的时间区间，每行包含两个空格分隔的整数 $s_i$ 和 $k_i$。

数据范围

• $1 \le n, m \le 2 \cdot 10^5$
• $-10^9 \le a_i \le 10^9$
• $1 \le s_i \le n; \forall i$
• $1 \le k_i$ 且 $s_i + k_i - 1 \le n; \forall i$

输出格式

输出 $m$ 行，每行对应一个时间区间。输出 Andrej 能为第 $i$ 个抵押贷款负担得起的最大整数月还款额。如果该数字严格小于 $0$，则输出 "stay with parents"（不含引号）。

样例

样例输入 1

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

样例输出 1

4
3
8
stay with parents
0

说明

对于第一个区间，每月 4 单位的还款额是 Andrej 能负担得起的最大值。如果每月还款 5 单位，他会在最后一次还款时耗尽资金。第 6 个月的负收入意味着 Andrej 无法负担区间 4 的任何抵押贷款，无论其金额大小。