You are given a sequence $a$ of length $n$ and $q$ queries. Each query provides an interval $[l, r]$. Find the minimum value of $a_i + a_j + a_k$ among all triples $(i, j, k)$ such that $l \le i < j < k \le r$ and $2\max(a_i, a_j, a_k) < a_i + a_j + a_k$.

Input

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers $a_{1\dots n}$.

The next $q$ lines each contain two integers $l$ and $r$ representing the query.

Output

Output $q$ lines, each containing an integer representing the answer.

Specifically, if no such triple exists, output yumi!.

Examples

Input 1

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

Output 1

yumi!
yumi!
28
24
28
yumi!

Input 2

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

Output 2

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

Subtasks

Idea: critnos, Solution: critnos & zhoukangyang, Code: critnos, Data: critnos & Otomachi_Una_

All data satisfies $1 \le n \le 2.5 \times 10^5$, $1 \le q \le 5 \times 10^5$, $1 \le a_i \le 10^7$, and $1 \le l \le r \le n$.