yl-9/probench huggingface dataset:
# Gorilla and Permutation

## Problem Description

Gorilla and Noobish\_Monk found three numbers $ n $ , $ m $ , and $ k $ ( $ m < k $ ). They decided to construct a permutation $ ^{\dagger} $ of length $ n $ .

For the permutation, Noobish\_Monk came up with the following function: $ g(i) $ is the sum of all the numbers in the permutation on a prefix of length $ i $ that are not greater than $ m $ . Similarly, Gorilla came up with the function $ f $ , where $ f(i) $ is the sum of all the numbers in the permutation on a prefix of length $ i $ that are not less than $ k $ . A prefix of length $ i $ is a subarray consisting of the first $ i $ elements of the original array.

For example, if $ n = 5 $ , $ m = 2 $ , $ k = 5 $ , and the permutation is $ [5, 3, 4, 1, 2] $ , then:

- $ f(1) = 5 $ , because $ 5 \ge 5 $ ; $ g(1) = 0 $ , because $ 5 > 2 $ ;
- $ f(2) = 5 $ , because $ 3 < 5 $ ; $ g(2) = 0 $ , because $ 3 > 2 $ ;
- $ f(3) = 5 $ , because $ 4 < 5 $ ; $ g(3) = 0 $ , because $ 4 > 2 $ ;
- $ f(4) = 5 $ , because $ 1 < 5 $ ; $ g(4) = 1 $ , because $ 1 \le 2 $ ;
- $ f(5) = 5 $ , because $ 2 < 5 $ ; $ g(5) = 1 + 2 = 3 $ , because $ 2 \le 2 $ .

Help them find a permutation for which the value of $ \left(\sum_{i=1}^n f(i) - \sum_{i=1}^n g(i)\right) $ is maximized.

 $ ^{\dagger} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in any order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation (as $ 2 $ appears twice in the array) and $ [1,3,4] $ is also not a permutation (as $ n=3 $ , but $ 4 $ appears in the array).

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The only line of each case contains three integers $ n $ , $ m $ , $ k $ ( $ 2\le n \le 10^5 $ ; $ 1 \le m < k \le n $ ) — the size of the permutation to be constructed and two integers.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output the permutation — a set of numbers that satisfies the conditions of the problem. If there are multiple solutions, output any of them.

## Sample #1

### Sample Input #1

```
3
5 2 5
3 1 3
10 3 8
```

### Sample Output #1

```
5 3 4 1 2
3 2 1
10 9 8 4 7 5 6 1 2 3
```

## Hint

In the first example, $ \left(\sum_{i=1}^n f(i) - \sum_{i=1}^n g(i)\right) = 5 \cdot 5 - (0 \cdot 3 + 1 + 3) = 25 - 4 = 21 $

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, math
Difficulty: 900
# Angry Monk

## Problem Description

To celebrate his recovery, k1o0n has baked an enormous $ n $ metres long potato casserole.

Turns out, Noobish\_Monk just can't stand potatoes, so he decided to ruin k1o0n's meal. He has cut it into $ k $ pieces, of lengths $ a_1, a_2, \dots, a_k $ meters.

k1o0n wasn't keen on that. Luckily, everything can be fixed. In order to do that, k1o0n can do one of the following operations:

- Pick a piece with length $ a_i \ge 2 $ and divide it into two pieces with lengths $ 1 $ and $ a_i - 1 $ . As a result, the number of pieces will increase by $ 1 $ ;
- Pick a slice $ a_i $ and another slice with length $ a_j=1 $ ( $ i \ne j $ ) and merge them into one piece with length $ a_i+1 $ . As a result, the number of pieces will decrease by $ 1 $ .

Help k1o0n to find the minimum number of operations he needs to do in order to merge the casserole into one piece with length $ n $ .

For example, if $ n=5 $ , $ k=2 $ and $ a = [3, 2] $ , it is optimal to do the following:

1. Divide the piece with length $ 2 $ into two pieces with lengths $ 2-1=1 $ and $ 1 $ , as a result $ a = [3, 1, 1] $ .
2. Merge the piece with length $ 3 $ and the piece with length $ 1 $ , as a result $ a = [4, 1] $ .
3. Merge the piece with length $ 4 $ and the piece with length $ 1 $ , as a result $ a = [5] $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ).

Description of each test case consists of two lines. The first line contains two integers $ n $ and $ k $ ( $ 2 \le n \le 10^9 $ , $ 2 \le k \le 10^5 $ ) — length of casserole and the number of pieces.

The second line contains $ k $ integers $ a_1, a_2, \ldots, a_k $ ( $ 1 \le a_i \le n - 1 $ , $ \sum a_i = n $ ) — lengths of pieces of casserole, which Noobish\_Monk has cut.

It is guaranteed that the sum of $ k $ over all $ t $ test cases doesn't exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output the minimum number of operations K1o0n needs to restore his pie after the terror of Noobish\_Monk.

## Sample #1

### Sample Input #1

```
4
5 3
3 1 1
5 2
3 2
11 4
2 3 1 5
16 6
1 6 1 1 1 6
```

### Sample Output #1

```
2
3
9
15
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, math, sortings
Difficulty: 800
# Only Pluses

## Problem Description

Kmes has written three integers $ a $ , $ b $ and $ c $ in order to remember that he has to give Noobish\_Monk $ a \times b \times c $ bananas.

Noobish\_Monk has found these integers and decided to do the following at most $ 5 $ times:

- pick one of these integers;
- increase it by $ 1 $ .

For example, if $ a = 2 $ , $ b = 3 $ and $ c = 4 $ , then one can increase $ a $ three times by one and increase $ b $ two times. After that $ a = 5 $ , $ b = 5 $ , $ c = 4 $ . Then the total number of bananas will be $ 5 \times 5 \times 4 = 100 $ .

What is the maximum value of $ a \times b \times c $ Noobish\_Monk can achieve with these operations?

## Input Format

Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains three integers $ a $ , $ b $ and $ c $ ( $ 1 \le a, b, c \le 10 $ ) — Kmes's integers.

## Output Format

For each test case, output a single integer — the maximum amount of bananas Noobish\_Monk can get.

## Sample #1

### Sample Input #1

```
2
2 3 4
10 1 10
```

### Sample Output #1

```
100
600
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, greedy, math, sortings
Difficulty: 800
# Prime Split Game

## Problem Description

Alice and Bob are playing a game with $ n $ piles of stones, where the $ i $ -th pile has $ a_i $ stones. Players take turns making moves, with Alice going first.

On each move, the player does the following three-step process:

1. Choose an integer $ k $ ( $ 1 \leq k \leq \frac n 2 $ ). Note that the value of $ k $ can be different for different moves.
2. Remove $ k $ piles of stones.
3. Choose another $ k $ piles of stones and split each pile into two piles. The number of stones in each new pile must be a prime number.

The player who is unable to make a move loses.

Determine who will win if both players play optimally.

## Input Format

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of piles of stones.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 2 \cdot 10^5 $ ) — the number of stones in the piles.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise.

You can output each letter in any case (upper or lower). For example, the strings "alIcE", "Alice", and "alice" will all be considered identical.

## Sample #1

### Sample Input #1

```
4
2
2 1
3
3 5 7
4
4 6 8 10
5
8 8 8 8 8
```

### Sample Output #1

```
Bob
Alice
Alice
Bob
```

## Hint

In the first test case, there are $ 2 $ piles of stones with $ 2 $ and $ 1 $ stones respectively. Since neither $ 1 $ nor $ 2 $ can be split into two prime numbers, Alice cannot make a move, so Bob wins.

In the second test case, there are $ 3 $ piles of stones with $ 3 $ , $ 5 $ , and $ 7 $ stones respectively. Alice can choose $ k = 1 $ , remove the pile of $ 7 $ stones, and then split the pile of $ 5 $ stones into two piles of prime numbers of stones, $ 2 $ and $ 3 $ . Then, the piles consist of $ 3 $ piles of stones with $ 3 $ , $ 2 $ , and $ 3 $ stones respectively, leaving Bob with no valid moves, so Alice wins.

In the third test case, there are $ 4 $ piles of stones with $ 4 $ , $ 6 $ , $ 8 $ , and $ 10 $ stones respectively. Alice can choose $ k = 2 $ , removing two piles of $ 8 $ and $ 10 $ stones. She splits the pile of $ 4 $ stones into two piles of prime numbers of stones, $ 2 $ and $ 2 $ , and the pile of $ 6 $ stones into two piles of $ 3 $ and $ 3 $ stones. Then, Bob has no valid moves, so Alice wins.

In the fourth test case, there are $ 5 $ piles of stones, each containing $ 8 $ stones. It can be shown that if both players play optimally, Bob will win.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, dp, fft, games, math, number theory
Difficulty: 3300
# Triangle Formation

## Problem Description

You are given $ n $ sticks, numbered from $ 1 $ to $ n $ . The length of the $ i $ -th stick is $ a_i $ .

You need to answer $ q $ queries. In each query, you are given two integers $ l $ and $ r $ ( $ 1 \le l < r \le n $ , $ r - l + 1 \ge 6 $ ). Determine whether it is possible to choose $ 6 $ distinct sticks from the sticks numbered $ l $ to $ r $ , to form $ 2 $ non-degenerate triangles $ ^{\text{∗}} $ .

 $ ^{\text{∗}} $ A triangle with side lengths $ a $ , $ b $ , and $ c $ is called non-degenerate if:

- $ a < b + c $ ,
- $ b < a + c $ , and
- $ c < a + b $ .

## Input Format

The first line contains two integers $ n $ and $ q $ ( $ 6 \le n \le 10^5 $ , $ 1 \le q \le 10^5 $ ) — the number of sticks and the number of queries respectively.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — $ a_i $ denotes the length of the $ i $ -th stick.

Each of the following $ q $ lines contains two integers $ l $ and $ r $ ( $ 1 \le l < r \le n $ , $ r - l + 1 \ge 6 $ ) — the parameters of each query.

## Output Format

For each query, output "YES" (without quotes) if it is possible to form $ 2 $ triangles, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
10 5
5 2 2 10 4 10 6 1 5 3
1 6
2 7
2 8
5 10
4 10
```

### Sample Output #1

```
YES
NO
YES
NO
YES
```

## Hint

In the first query, the lengths of the sticks are $ [5, 2, 2, 10, 4, 10] $ . Two sets of sticks $ [2, 4, 5] $ and $ [2, 10, 10] $ can be selected to form $ 2 $ non-degenerate triangles.

In the second query, the lengths of the sticks are $ [2, 2, 10, 4, 10, 6] $ . It can be shown that it is impossible to form $ 2 $ non-degenerate triangles.

In the third query, the lengths of the sticks are $ [2, 2, 10, 4, 10, 6, 1] $ . Two sets of sticks $ [1, 2, 2] $ and $ [4, 10, 10] $ can be selected to form $ 2 $ non-degenerate triangles.

In the fourth query, the lengths of the sticks are $ [4, 10, 6, 1, 5, 3] $ . It can be shown that it is impossible to form $ 2 $ non-degenerate triangles.

In the fifth query, the lengths of the sticks are $ [10, 4, 10, 6, 1, 5, 3] $ . Two sets of sticks $ [1, 10, 10] $ and $ [3, 4, 5] $ can be selected to form $ 2 $ non-degenerate triangles.

## Limit



Time Limit
5.00s

Memory Limit
250.00MB

Tags: brute force, greedy, implementation, math, sortings
Difficulty: 2200
# Prime XOR Coloring

## Problem Description

You are given an undirected graph with $ n $ vertices, numbered from $ 1 $ to $ n $ . There is an edge between vertices $ u $ and $ v $ if and only if $ u \oplus v $ is a [prime number](https://en.wikipedia.org/wiki/Prime_number), where $ \oplus $ denotes the [bitwise XOR operator](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Color all vertices of the graph using the minimum number of colors, such that no two vertices directly connected by an edge have the same color.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of test cases follows.

The only line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the graph.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output two lines.

The first line should contain a single integer $ k $ ( $ 1 \le k \le n $ ) — the minimum number of colors required.

The second line should contain $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \le c_i \le k $ ) — the color of each vertex.

If there are multiple solutions, output any of them.

## Sample #1

### Sample Input #1

```
6
1
2
3
4
5
6
```

### Sample Output #1

```
1
1
2
1 2
2
1 2 2
3
1 2 2 3
3
1 2 2 3 3
4
1 2 2 3 3 4
```

## Hint

In the first test case, the minimum number of colors is $ 1 $ , because there is only one vertex.

In the second test case, the minimum number of colors is $ 2 $ , because there is an edge connecting $ 1 $ and $ 2 $ ( $ 1 \oplus 2 = 3 $ , which is a prime number).

In the third test case, the minimum number of colors is still $ 2 $ , because $ 2 $ and $ 3 $ can be colored the same since there is no edge between $ 2 $ and $ 3 $ ( $ 2 \oplus 3 = 1 $ , which is not a prime number).

In the fourth test case, it can be shown that the minimum number of colors is $ 3 $ .

In the fifth test case, it can be shown that the minimum number of colors is $ 3 $ .

In the sixth test case, it can be shown that the minimum number of colors is $ 4 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, constructive algorithms, graphs, greedy, math, number theory
Difficulty: 1900
# Absolute Zero

## Problem Description

You are given an array $ a $ of $ n $ integers.

In one operation, you will perform the following two-step move:

1. Choose an integer $ x $ ( $ 0 \le x \le 10^{9} $ ).
2. Replace each $ a_i $ with $ |a_i - x| $ , where $ |v| $ denotes the [absolute value](https://en.wikipedia.org/wiki/Absolute_value) of $ v $ .

For example, by choosing $ x = 8 $ , the array $ [5, 7, 10] $ will be changed into $ [|5-8|, |7-8|, |10-8|] = [3,1,2] $ .

Construct a sequence of operations to make all elements of $ a $ equal to $ 0 $ in at most $ 40 $ operations or determine that it is impossible. You do not need to minimize the number of operations.

## Input Format

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the elements of the array $ a $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer $ -1 $ if it is impossible to make all array elements equal to $ 0 $ in at most $ 40 $ operations.

Otherwise, output two lines. The first line of output should contain a single integer $ k $ ( $ 0 \le k \le 40 $ ) — the number of operations. The second line of output should contain $ k $ integers $ x_1, x_2, \ldots, x_k $ ( $ 0 \le x_i \le 10^{9} $ ) — the sequence of operations, denoting that on the $ i $ -th operation, you chose $ x=x_i $ .

If there are multiple solutions, output any of them.

You do not need to minimize the number of operations.

## Sample #1

### Sample Input #1

```
5
1
5
2
0 0
3
4 6 8
4
80 40 20 10
5
1 2 3 4 5
```

### Sample Output #1

```
1
5
0

3
6 1 1
7
60 40 20 10 30 25 5
-1
```

## Hint

In the first test case, we can perform only one operation by choosing $ x = 5 $ , changing the array from $ [5] $ to $ [0] $ .

In the second test case, no operations are needed because all elements of the array are already $ 0 $ .

In the third test case, we can choose $ x = 6 $ to change the array from $ [4, 6, 8] $ to $ [2, 0, 2] $ , then choose $ x = 1 $ to change it to $ [1, 1, 1] $ , and finally choose $ x = 1 $ again to change the array into $ [0, 0, 0] $ .

In the fourth test case, we can make all elements $ 0 $ by following the operation sequence $ (60, 40, 20, 10, 30, 25, 5) $ .

In the fifth test case, it can be shown that it is impossible to make all elements $ 0 $ in at most $ 40 $ operations. Therefore, the output is $ -1 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math
Difficulty: 1300
# AND Reconstruction

## Problem Description

You are given an array $ b $ of $ n - 1 $ integers.

An array $ a $ of $ n $ integers is called good if $ b_i = a_i \, \& \, a_{i + 1} $ for $ 1 \le i \le n-1 $ , where $ \& $ denotes the [bitwise AND operator](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

Construct a good array, or report that no good arrays exist.

## Input Format

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^5 $ ) — the length of the array $ a $ .

The second line of each test case contains $ n - 1 $ integers $ b_1, b_2, \ldots, b_{n - 1} $ ( $ 0 \le b_i < 2^{30} $ ) — the elements of the array $ b $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

## Output Format

For each test case, output a single integer $ -1 $ if no good arrays exist.

Otherwise, output $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i < 2^{30} $ ) — the elements of a good array $ a $ .

If there are multiple solutions, you may output any of them.

## Sample #1

### Sample Input #1

```
4
2
1
3
2 0
4
1 2 3
5
3 5 4 2
```

### Sample Output #1

```
5 3
3 2 1
-1
3 7 5 6 3
```

## Hint

In the first test case, $ b = [1] $ . A possible good array is $ a=[5, 3] $ , because $ a_1 \, \& \, a_2 = 5 \, \& \, 3 = 1 = b_1 $ .

In the second test case, $ b = [2, 0] $ . A possible good array is $ a=[3, 2, 1] $ , because $ a_1 \, \& \, a_2 = 3 \, \& \, 2 = 2 = b_1 $ and $ a_2 \, \& \, a_3 = 2 \, \& \, 1 = 0 = b_2 $ .

In the third test case, $ b = [1, 2, 3] $ . It can be shown that no good arrays exist, so the output is $ -1 $ .

In the fourth test case, $ b = [3, 5, 4, 2] $ . A possible good array is $ a=[3, 7, 5, 6, 3] $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: bitmasks, constructive algorithms, greedy
Difficulty: 1100
# Maximize the Last Element

## Problem Description

You are given an array $ a $ of $ n $ integers, where $ n $ is odd.

In one operation, you will remove two adjacent elements from the array $ a $ , and then concatenate the remaining parts of the array. For example, given the array $ [4,7,4,2,9] $ , we can obtain the arrays $ [4,2,9] $ and $ [4,7,9] $ by the operations $ [\underline{4,7}, 4,2,9] \to [4,2,9] $ and $ [4,7,\underline{4,2},9] \to [4,7,9] $ respectively. However, we cannot obtain the array $ [7,2,9] $ as it requires deleting non-adjacent elements $ [\underline{4},7,\underline{4},2,9] $ .

You will repeatedly perform this operation until exactly one element remains in $ a $ .

Find the maximum possible value of the remaining element in $ a $ .

## Input Format

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 99 $ ; $ n $ is odd) — the length of the array $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 100 $ ) — the elements of the array $ a $ .

Note that there is no bound on the sum of $ n $ over all test cases.

## Output Format

For each test case, output a single integer — the maximum possible value of the remaining element in $ a $ .

## Sample #1

### Sample Input #1

```
4
1
6
3
1 3 2
5
4 7 4 2 9
7
3 1 4 1 5 9 2
```

### Sample Output #1

```
6
2
9
5
```

## Hint

In the first test case, the array $ a $ is $ [6] $ . Since there is only one element, no operations are needed. The maximum possible value of the remaining element is $ 6 $ .

In the second test case, the array $ a $ is $ [1, 3, 2] $ . We can remove the first two elements $ [\underline{1, 3}, 2] \to [2] $ , or remove the last two elements $ [1, \underline{3, 2}] \to [1] $ . Therefore, the maximum possible value of the remaining element is $ 2 $ .

In the third test case, the array $ a $ is $ [4, 7, 4, 2, 9] $ . One way to maximize the remaining element is $ [4, \underline{7, 4}, 2, 9] \to [\underline{4, 2}, 9] \to [9] $ . Therefore, the maximum possible value of the remaining element is $ 9 $ .

In the fourth test case, the array $ a $ is $ [3, 1, 4, 1, 5, 9, 2] $ . It can be shown that the maximum possible value of the remaining element is $ 5 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Polygonal Segments

## Problem Description

You are given an array $ a $ of size $ n $ .

A segment $ [l, r](1 \le l < r \le n) $ is called a polygonal segment only if the following conditions hold:

- $ (r-l+1) \geq 3 $ ;
- Considering $ a_l, a_{l+1}, \ldots, a_r $ as side lengths, these sides can form a polygon with $ (r-l+1) $ sides.

Process $ q $ queries of two types:

- "1 l r": find the length of the longest segment among all polygonal segments $ [l_0,r_0] $ satisfying $ l \le l_0 \le r_0 \le r $ . If there is no such polygonal segment, output $ -1 $ instead;
- "2 i x": assign $ a_i := x $ .

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

For each test case:

- The first line of each testcase contains two integers $ n $ , $ q $ ( $ 4 \le n \le 2\cdot 10^5 $ , $ 1 \le q \le 10^5 $ );
- The second line of each testcase contains $ n $ integers $ a_1,a_2,\ldots, a_n $ ( $ 1 \le a_i \le 10^{12} $ );
- The following $ q $ lines contain the description of queries. Each line is of one of two types:
  - "1 l r" ( $ 1 \le l < r \le n $ , $ r-l+1\ge 3 $ );
  - "2 i x" ( $ 1 \le i \le n $ , $ 1 \le x \le 10^{12} $ ).

It is guaranteed that the sum of $ n $ over all test cases will not exceed $ 2 \cdot 10^5 $ , and the sum of $ q $ over all test cases will not exceed $ 10^5 $ .

## Output Format

For each query, if there is no suitable segment, output $ -1 $ in a new line. Otherwise, output the length of the longest segment satisfying the condition above in a new line.

## Sample #1

### Sample Input #1

```
2
5 6
3 1 2 2 8
1 1 3
1 1 4
1 1 5
2 1 5
1 1 4
1 1 5
4 10
500000000000 500000000000 1000000000000 500000000000
1 1 3
1 2 4
1 1 4
2 1 499999999999
2 3 999999999999
1 1 3
1 2 4
1 1 4
2 3 1000000000000
1 1 3
```

### Sample Output #1

```
-1
4
4
3
5
-1
-1
4
-1
3
4
-1
```

## Hint

In the first query of the first test case, there is no polygonal segment under the given condition. For example, considering segment $ [1,3] $ , you can not form a triangle with side lengths of $ a_1=3 $ , $ a_2=1 $ , and $ a_3=2 $ .

In the second query of the first test case, the longest polygonal segment is $ [1,4] $ . You can form a quadrilateral with side lengths of $ a_1=3 $ , $ a_2=1 $ , $ a_3=2 $ , and $ a_4=2 $ .

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1990F/581888fa1d57458ff95b2d8a702e4ff9b8a8fc11.png) An example of a quadrilateral with side lengths of $ 3 $ , $ 1 $ , $ 2 $ , and $ 2 $ .

## Limit



Time Limit
8.00s

Memory Limit
500.00MB

Tags: brute force, data structures, divide and conquer, dp, greedy, two pointers
Difficulty: 2800