说明

已经完全是秋季了。

即使如此，丝柏（ZYPRESSEN）也是一如既往的黢黑吧。

给你一个长度为 $n$ 的序列 $a$，共有 $q$ 次询问，每次询问如下：

• 给你一个区间 $[l,r]$，对于所有的 $i,j,k$ 满足 $l\le i<j<k\le r$ 且三边长度分别为 $a_i,a_j,a_k$ 的三角形存在，你需要求出 $a_i+a_j+a_k$ 的最小值。

三边长度分别为 $a,b,c(a\le b\le c)$ 时，能构成三角形当且仅当 $a+b>c$。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_{1\dots n}$。

接下来 $q$ 行，每行两个整数 $l,r$ 表示询问。

输出格式

$q$ 行，每行一个整数表示答案。如果不存在符合条件的 $i,j,k$，输出 yumi!。

7 6
3 11 1 5 12 19 10
1 1
3 5
2 5
1 7
2 6
1 4

yumi!
yumi!
28
24
28
yumi!

20 20
26 17 11 89 56 33 72 73 43 77 80 87 97 17 43 74 72 91 49 69
10 19
2 4
3 5
2 11
1 12
10 19
3 5
8 15
8 12
14 20
5 11
13 18
2 18
17 19
1 9
5 8
9 12
1 11
4 13
3 18

109
yumi!
yumi!
87
54
109
yumi!
103
193
109
132
163
45
212
54
161
200
54
132
87

提示

样例解释 1

对于区间 $[3,5]$，因为 $1+5<12$，所以不存在合法的三角形。

对于区间 $[2,5]$ 和 $[2,6]$，选取 $a_i=11,a_j=5,a_k=12$。

对于区间 $[1,7]$，选取 $a_i=3,a_j=11,a_k=10$。

数据规模与约定

本题采用捆绑测试。

特殊性质：保证 $a_i$ 在范围内等概率随机生成。

对于所有数据，保证 $1\le n\le 2.5\times 10^5$，$1\le q\le 5\times 10^5$，$1\le a_i\le 10^7$，$1\le l\le r\le n$。