Problem Background

The long night accompanies the breaking dawn, and the dawn breaks the waves, accompanying the long night.

It is already fully autumn.

Even so, the cypress (ZYPRESSEN) remains as dark as ever.

Problem Description

You are given a sequence \(a\) of length \(n\), and there are \(q\) queries. Each query is as follows:

• You are given an interval \([l, r]\). For all \(i, j, k\) such that \(l \le i < j < k \le r\) and the sides of a triangle are \(a_i, a_j, a_k\), you need to find the minimum value of \(a_i + a_j + a_k\).

A triangle with sides \(a, b, c\) (where \(a \le b \le c\)) can be formed if and only if \(a + b > c\).

Input Format

The first line contains two integers \(n\) and \(q\).

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

The next \(q\) lines, each containing two integers \(l\) and \(r\), represent the queries.

Output Format

Output \(q\) lines, each containing an integer as the answer. If there are no valid \(i, j, k\), output yumi!.

Sample Input and Output

Input Sample #1

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

Output Sample #1

yumi!
yumi!
28
24
28
yumi!

Input Sample #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 Sample #2

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

Notes

Sample Explanation 1

For the interval \([3, 5]\), since \(1 + 5 < 12\), there is no valid triangle.

For the intervals \([2, 5]\) and \([2, 6]\), choose \(a_i = 11, a_j = 5, a_k = 12\).

For the interval \([1, 7]\), choose \(a_i = 3, a_j = 11, a_k = 10\).

Data Size and Constraints

This problem uses batched testing.

Special Conditions: \(a_i\) is generated randomly within the range.

For all data, it is guaranteed that \(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\).

见题面 Input 部分

见题面 Output 部分