yl-9/probench huggingface dataset:
# Grid Puzzle

## Problem Description

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

There is an $ n \times n $ grid. In the $ i $ -th row, the first $ a_i $ cells are black and the other cells are white. In other words, note $ (i,j) $ as the cell in the $ i $ -th row and $ j $ -th column, cells $ (i,1), (i,2), \ldots, (i,a_i) $ are black, and cells $ (i,a_i+1), \ldots, (i,n) $ are white.

You can do the following operations any number of times in any order:

- Dye a $ 2 \times 2 $ subgrid white;
- Dye a whole row white. Note you can not dye a whole column white.

Find the minimum number of operations to dye all cells white.

## 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 contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the size of the array $ a $ .
- The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq n $ ).

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

## Output Format

For each test case, output a single integer — the minimum number of operations to dye all cells white.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0
3
2
1
2
2
3
2
4
6
```

## Hint

In the first test case, you don't need to do any operation.

In the second test case, you can do:

- Dye $ (1,1), (1,2), (2,1) $ , and $ (2,2) $ white;
- Dye $ (2,3), (2,4), (3,3) $ , and $ (3,4) $ white;
- Dye $ (3,1), (3,2), (4,1) $ , and $ (4,2) $ white.

It can be proven $ 3 $ is the minimum number of operations.

In the third test case, you can do:

- Dye the first row white;
- Dye $ (2,1), (2,2), (3,1) $ , and $ (3,2) $ white.

It can be proven $ 2 $ is the minimum number of operations.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, brute force, dp, greedy, implementation
Difficulty: 1800
# Mad MAD Sum

## Problem Description

We define the $ \operatorname{MAD} $ (Maximum Appearing Duplicate) in an array as the largest number that appears at least twice in the array. Specifically, if there is no number that appears at least twice, the $ \operatorname{MAD} $ value is $ 0 $ .

For example, $ \operatorname{MAD}([1, 2, 1]) = 1 $ , $ \operatorname{MAD}([2, 2, 3, 3]) = 3 $ , $ \operatorname{MAD}([1, 2, 3, 4]) = 0 $ .

You are given an array $ a $ of size $ n $ . Initially, a variable $ sum $ is set to $ 0 $ .

The following process will be executed in a sequential loop until all numbers in $ a $ become $ 0 $ :

1. Set $ sum := sum + \sum_{i=1}^{n} a_i $ ;
2. Let $ b $ be an array of size $ n $ . Set $ b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i]) $ for all $ 1 \le i \le n $ , and then set $ a_i := b_i $ for all $ 1 \le i \le n $ .

Find the value of $ sum $ after the process.

## Input Format

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

For each test case:

- The first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the size of the array $ a $ ;
- The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array.

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

## Output Format

For each test case, output the value of $ sum $ in a new line.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1
13
9
40
```

## Hint

In the first test case, $ a=[1] $ initially.

In the first loop:

1. Set $ sum := sum + a_1 = 0+1=1 $ ;
2. Set $ b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0 $ , and then set $ a_1 := b_1 $ .

After the first loop, $ a=[0] $ and the process ends. The value of $ sum $ after the process is $ 1 $ .

In the second test case, $ a=[2,2,3] $ initially.

After the first loop, $ a=[0,2,2] $ and $ sum=7 $ .

After the second loop, $ a=[0,0,2] $ and $ sum=11 $ .

After the third loop, $ a=[0,0,0] $ and $ sum=13 $ . Then the process ends.

The value of $ sum $ after the process is $ 13 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, greedy, math
Difficulty: 1500
# Array Craft

## Problem Description

For an array $ b $ of size $ m $ , we define:

- the maximum prefix position of $ b $ is the smallest index $ i $ that satisfies $ b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j) $ ;
- the maximum suffix position of $ b $ is the largest index $ i $ that satisfies $ b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m) $ .

You are given three integers $ n $ , $ x $ , and $ y $ ( $ x > y $ ). Construct an array $ a $ of size $ n $ satisfying:

- $ a_i $ is either $ 1 $ or $ -1 $ for all $ 1 \le i \le n $ ;
- the maximum prefix position of $ a $ is $ x $ ;
- the maximum suffix position of $ a $ is $ y $ .

If there are multiple arrays that meet the conditions, print any. It can be proven that such an array always exists under the given conditions.

## 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 only line contains three integers $ n $ , $ x $ , and $ y $ ( $ 2 \leq n \leq 10^5, 1 \le y \lt x \le n) $ .

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

## Output Format

For each test case, output $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ in a new line.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1 1
1 -1 1 1
1 1 -1 1 1 -1
```

## Hint

In the second test case,

- $ i=x=4 $ is the smallest index that satisfies $ a_1+\ldots +a_i=\max_{j=1}^{n}(a_1+\ldots+a_j)=2 $ ;
- $ i=y=3 $ is the greatest index that satisfies $ a_i+\ldots +a_n=\max_{j=1}^{n}(a_j+\ldots+a_n)=2 $ .

Thus, the array $ a=[1,-1,1,1] $ is considered correct.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy
Difficulty: 1200
# Submission Bait

## Problem Description

Alice and Bob are playing a game in an array $ a $ of size $ n $ .

They take turns to do operations, with Alice starting first. The player who can not operate will lose. At first, a variable $ mx $ is set to $ 0 $ .

In one operation, a player can do:

- Choose an index $ i $ ( $ 1 \le i \le n $ ) such that $ a_{i} \geq mx $ and set $ mx $ to $ a_{i} $ . Then, set $ a_{i} $ to $ 0 $ .

Determine whether Alice has a winning strategy.

## Input Format

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

For each test case:

- The first line contains an integer $ n $ ( $ 2 \leq n \leq 50 $ ) — the size of the array.
- The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array.

## Output Format

For each test case, if Alice has a winning strategy, output "YES". Otherwise, output "NO".

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

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

### Sample Output #1

```
YES
NO
YES
NO
YES
```

## Hint

In the first test case, Alice can choose $ i=1 $ since $ a_1=2 \ge mx=0 $ .

After Alice's operation, $ a=[0,1] $ and $ mx=2 $ . Bob can not do any operation. Alice wins.

In the second test case, Alice doesn't have a winning strategy.

For example, if Alice chooses $ i=1 $ , after Alice's operation: $ a=[0,1] $ and $ mx=1 $ . Then, Bob can choose $ i=2 $ since $ a_2=1 \ge mx=1 $ . After Bob's operation: $ a=[0,0] $ and $ mx=1 $ . Alice can not do any operation. Bob wins.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, games, greedy, sortings
Difficulty: 900
# Heartbeat

## Problem Description

For an array $ u_1, u_2, \ldots, u_n $ , define

- a prefix maximum as an index $ i $ such that $ u_i>u_j $ for all $ j<i $ ;
- a suffix maximum as an index $ i $ such that $ u_i>u_j $ for all $ j>i $ ;
- an ascent as an index $ i $ ( $ i>1 $ ) such that $ u_i>u_{i-1} $ .

You are given three cost arrays: $ [a_1, a_2, \ldots, a_n] $ , $ [b_1, b_2, \ldots, b_n] $ , and $ [c_0, c_1, \ldots, c_{n-1}] $ .

Define the cost of an array that has $ x $ prefix maximums, $ y $ suffix maximums, and $ z $ ascents as $ a_x\cdot b_y\cdot c_z $ .

Let the sum of costs of all permutations of $ 1,2,\ldots,n $ be $ f(n) $ . Find $ f(1) $ , $ f(2) $ , ..., $ f(n) $ modulo $ 998\,244\,353 $ .

## Input Format

The first line contains an integer $ n $ ( $ 1\le n\le 700 $ ).

The second line contains $ n $ integers $ a_1,\ldots,a_n $ ( $ 0\le a_i<998\,244\,353 $ ).

The third line contains $ n $ integers $ b_1,\ldots,b_n $ ( $ 0\le b_i<998\,244\,353 $ ).

The fourth line contains $ n $ integers $ c_0,\ldots,c_{n-1} $ ( $ 0\le c_i<998\,244\,353 $ ).

## Output Format

Print $ n $ integers: the $ i $ -th one is $ f(i) $ modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
3
1 1 1
1 1 1
1 1 1
```

### Sample Output #1

```
1 2 6
```

## Sample #2

### Sample Input #2

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

### Sample Output #2

```
6 13 34
```

## Sample #3

### Sample Input #3

```
5
1 4 2 5 3
2 5 1 3 4
300000000 100000000 500000000 400000000 200000000
```

### Sample Output #3

```
600000000 303511294 612289529 324650937 947905622
```

## Hint

In the second example:

- Consider permutation $ [1,2,3] $ . Indices $ 1,2,3 $ are prefix maximums. Index $ 3 $ is the only suffix maximum. Indices $ 2,3 $ are ascents. In conclusion, it has $ 3 $ prefix maximums, $ 1 $ suffix maximums, and $ 2 $ ascents. Therefore, its cost is $ a_3b_1c_2=12 $ .
- Permutation $ [1,3,2] $ has $ 2 $ prefix maximums, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 6 $ .
- Permutation $ [2,1,3] $ has $ 2 $ prefix maximums, $ 1 $ suffix maximum, and $ 1 $ ascent. Its cost is $ 4 $ .
- Permutation $ [2,3,1] $ has $ 2 $ prefix maximums, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 6 $ .
- Permutation $ [3,1,2] $ has $ 1 $ prefix maximum, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 3 $ .
- Permutation $ [3,2,1] $ has $ 1 $ prefix maximum, $ 3 $ suffix maximums, and $ 0 $ ascents. Its cost is $ 3 $ .

The sum of all permutations' costs is $ 34 $ , so $ f(3)=34 $ .

## Limit



Time Limit
5.00s

Memory Limit
500.00MB

Tags: combinatorics, dp, fft, math
Difficulty: 3000
# Range Minimum Sum

## Problem Description

For an array $ [a_1,a_2,\ldots,a_n] $ of length $ n $ , define $ f(a) $ as the sum of the minimum element over all subsegments. That is, $ $$$f(a)=\sum_{l=1}^n\sum_{r=l}^n \min_{l\le i\le r}a_i. $ $ </p><p>A permutation is a sequence of integers from  $ 1 $  to  $ n $  of length  $ n $  containing each number exactly once. You are given a permutation  $ \[a\_1,a\_2,\\ldots,a\_n\] $ . For each  $ i $ , solve the following problem independently:</p><ul> <li> Erase  $ a\_i $  from  $ a $ , concatenating the remaining parts, resulting in  $ b = \[a\_1,a\_2,\\ldots,a\_{i-1},\\;a\_{i+1},\\ldots,a\_{n}\] $ . </li><li> Calculate  $ f(b)$$$.

## Input Format

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

The first line of each test case contains an integer $ n $ ( $ 1\le n\le 5\cdot 10^5 $ ).

The second line of each test case contains $ n $ distinct integers $ a_1,\ldots,a_n $ ( $ 1\le a_i\le n $ ).

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

## Output Format

For each test case, print one line containing $ n $ integers. The $ i $ -th integer should be the answer when erasing $ a_i $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0 
4 7 5 
19 21 27 17 19 
79 100 72 68 67 80 73 80
```

## Hint

In the second test case, $ a=[3,1,2] $ .

- When removing $ a_1 $ , $ b=[1,2] $ . $ f(b)=1+2+\min\{1,2\}=4 $ .
- When removing $ a_2 $ , $ b=[3,2] $ . $ f(b)=3+2+\min\{3,2\}=7 $ .
- When removing $ a_3 $ , $ b=[3,1] $ . $ f(b)=3+1+\min\{3,1\}=5 $ .

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: binary search, brute force, data structures, divide and conquer, implementation
Difficulty: 2300
# Increasing Sequence with Fixed OR

## Problem Description

You are given a positive integer $ n $ . Find the longest sequence of positive integers $ a=[a_1,a_2,\ldots,a_k] $ that satisfies the following conditions, and print the sequence:

- $ a_i\le n $ for all $ 1\le i\le k $ .
- $ a $ is strictly increasing. That is, $ a_i>a_{i-1} $ for all $ 2\le i\le k $ .
- $ a_i\,|\,a_{i-1}=n $ for all $ 2\le i\le k $ , where $ | $ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

## Input Format

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

The only line of each test case contains one integer $ n $ ( $ 1\le n\le 10^{18} $ ).

It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $ 5\cdot 10^5 $ .

## Output Format

For each testcase, print two lines. In the first line, print the length of your constructed sequence, $ k $ . In the second line, print $ k $ positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.

## Sample #1

### Sample Input #1

```
4
1
3
14
23
```

### Sample Output #1

```
1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23
```

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: bitmasks, constructive algorithms, greedy
Difficulty: 1300
# Make Majority

## Problem Description

You are given a sequence $ [a_1,\ldots,a_n] $ where each element $ a_i $ is either $ 0 $ or $ 1 $ . You can apply several (possibly zero) operations to the sequence. In each operation, you select two integers $ 1\le l\le r\le |a| $ (where $ |a| $ is the current length of $ a $ ) and replace $ [a_l,\ldots,a_r] $ with a single element $ x $ , where $ x $ is the majority of $ [a_l,\ldots,a_r] $ .

Here, the majority of a sequence consisting of $ 0 $ and $ 1 $ is defined as follows: suppose there are $ c_0 $ zeros and $ c_1 $ ones in the sequence, respectively.

- If $ c_0\ge c_1 $ , the majority is $ 0 $ .
- If $ c_0<c_1 $ , the majority is $ 1 $ .

For example, suppose $ a=[1,0,0,0,1,1] $ . If we select $ l=1,r=2 $ , the resulting sequence will be $ [0,0,0,1,1] $ . If we select $ l=4,r=6 $ , the resulting sequence will be $ [1,0,0,1] $ .

Determine if you can make $ a=[1] $ with a finite number of operations.

## Input Format

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

The first line of each testcase contains one integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ).

The second line of each testcase contains a string consisting of $ 0 $ and $ 1 $ , describing the sequence $ a $ .

It's guaranteed that the sum of $ n $ over all testcases does not exceed $ 2\cdot 10^5 $ .

## Output Format

For each testcase, if it's possible to make $ a=[1] $ , print YES. Otherwise, print NO. 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

```
5
1
0
1
1
2
01
9
100000001
9
000011000
```

### Sample Output #1

```
No
Yes
No
Yes
No
```

## Hint

In the fourth testcase of the example, initially $ a=[1,0,0,0,0,0,0,0,1] $ . A valid sequence of operations is:

1. Select $ l=2,r=8 $ and apply the operation. $ a $ becomes $ [1,0,1] $ .
2. Select $ l=1,r=3 $ and apply the operation. $ a $ becomes $ [1] $ .

## Limit



Time Limit
1.50s

Memory Limit
500.00MB

Tags: greedy, implementation
Difficulty: 900
# Split the Multiset

## Problem Description

A multiset is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. For example, $ \{2,2,4\} $ is a multiset.

You have a multiset $ S $ . Initially, the multiset contains only one positive integer $ n $ . That is, $ S=\{n\} $ . Additionally, there is a given positive integer $ k $ .

In one operation, you can select any positive integer $ u $ in $ S $ and remove one copy of $ u $ from $ S $ . Then, insert no more than $ k $ positive integers into $ S $ so that the sum of all inserted integers is equal to $ u $ .

Find the minimum number of operations to make $ S $ contain $ n $ ones.

## Input Format

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

The only line of each testcase contains two integers $ n,k $ ( $ 1\le n\le 1000,2\le k\le 1000 $ ).

## Output Format

For each testcase, print one integer, which is the required answer.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0
4
3
5
```

## Hint

For the first test case, initially $ S=\{1\} $ , already satisfying the requirement. Therefore, we need zero operations.

For the second test case, initially $ S=\{5\} $ . We can apply the following operations:

- Select $ u=5 $ , remove $ u $ from $ S $ , and insert $ 2,3 $ into $ S $ . Now, $ S=\{2,3\} $ .
- Select $ u=2 $ , remove $ u $ from $ S $ , and insert $ 1,1 $ into $ S $ . Now, $ S=\{1,1,3\} $ .
- Select $ u=3 $ , remove $ u $ from $ S $ , and insert $ 1,2 $ into $ S $ . Now, $ S=\{1,1,1,2\} $ .
- Select $ u=2 $ , remove $ u $ from $ S $ , and insert $ 1,1 $ into $ S $ . Now, $ S=\{1,1,1,1,1\} $ .

Using $ 4 $ operations in total, we achieve the goal.

For the third test case, initially $ S=\{6\} $ . We can apply the following operations:

- Select $ u=6 $ , remove $ u $ from $ S $ , and insert $ 1,2,3 $ into $ S $ . Now, $ S=\{1,2,3\} $ .
- Select $ u=2 $ , remove $ u $ from $ S $ , and insert $ 1,1 $ into $ S $ . Now, $ S=\{1,1,1,3\} $ .
- Select $ u=3 $ , remove $ u $ from $ S $ , and insert $ 1,1,1 $ into $ S $ . Now, $ S=\{1,1,1,1,1,1\} $ .

Using $ 3 $ operations in total, we achieve the goal.

For the fourth test case, initially $ S=\{16\} $ . We can apply the following operations:

- Select $ u=16 $ , remove $ u $ from $ S $ , and insert $ 4,4,4,4 $ into $ S $ . Now, $ S=\{4,4,4,4\} $ .
- Repeat for $ 4 $ times: select $ u=4 $ , remove $ u $ from $ S $ , and insert $ 1,1,1,1 $ into $ S $ .

Using $ 5 $ operations in total, we achieve the goal.

## Limit



Time Limit
1.00s

Memory Limit
500.00MB

Tags: brute force, greedy, implementation, math
Difficulty: 900
# Your Loss

## Problem Description

You are given a tree with $ n $ nodes numbered from $ 1 $ to $ n $ , along with an array of size $ n $ . The value of $ i $ -th node is $ a_{i} $ . There are $ q $ queries. In each query, you are given 2 nodes numbered as $ x $ and $ y $ .

Consider the path from the node numbered as $ x $ to the node numbered as $ y $ . Let the path be represented by $ x = p_0, p_1, p_2, \ldots, p_r = y $ , where $ p_i $ are the intermediate nodes. Compute the sum of $ a_{p_i}\oplus i $ for each $ i $ such that $ 0 \le i \le r $ where $ \oplus $ is the [XOR](https://en.wikipedia.org/wiki/Exclusive_or) operator.

More formally, compute
$$
\sum_{i =0}^{r} a_{p_i}\oplus i
$$
.

## Input Format

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

The first line of each set of input data contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ) — the number of nodes.

The next $ n-1 $ lines of each set of input data contain $ 2 $ integers, $ u $ and $ v $ representing an edge between the node numbered $ u $ and the node numbered $ v $ . It is guaranteed that $ u \ne v $ and that the edges form a tree.

The next line of each set of input data contains $ n $ integers, $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 5 \cdot 10^5 $ ) — values of the nodes.

The next line contains a single integer $ q $ ( $ 1 \le q \le 10^5 $ ) — the number of queries.

The next $ q $ lines describe the queries. The $ i $ -th query contains $ 2 $ integers $ x $ and $ y $ ( $ 1 \le x,y \le n $ ) denoting the starting and the ending node of the path.

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

## Output Format

For each query, output a single number — the sum from the problem statement.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
14
10
2
```

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: bitmasks, brute force, dp, trees
Difficulty: 3000
# array-value

## Problem Description

You have an array of non-negative integers $ a_1, a_2, \ldots, a_n $ .

The value of a sub-array of length $ \ge 2 $ , $ a[l, r] = [a_l, a_{l+1}, \ldots, a_r] $ is the minimum value of $ a_i \oplus a_j $ such that $ l \le i < j \le r $ , where $ \oplus $ is the xor (exclusive-or) operator.

You have to find the $ k $ -th smallest value over all sub-arrays of length $ \ge 2 $ .

## Input Format

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

The first line of each test case contains integer numbers $ n $ and $ k $ ( $ 2 \le n \le 10^5 $ , $ 1 \le k \le \frac{n\cdot(n-1)}{2} $ ).

The second line of the input contains $ n $ non-negative integer numbers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the array itself.

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

## Output Format

Print the $ k $ -th smallest value obtained over all subarrays of length at least $ 2 $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1
7
12
3
```

## Hint

In the first testcase, we have subarrays with their smallest exclusive-or pair as:

 $ [1,2]: 3 $

 $ [2,3]: 1 $

 $ [3,4]: 7 $

 $ [4,5]: 1 $

 $ [1,2,3]: 1 $

 $ [2,3,4]: 1 $

 $ [3,4,5]: 1 $

 $ [1,2,3,4]: 1 $

 $ [2,3,4,5]: 1 $

 $ [1,2,3,4,5]: 1 $

The sorted order would be: $ 1, 1, 1, 1, 1, 1, 1, 1, 3, 7 $ . Therefore, the second smallest element would be $ 1 $ .

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: binary search, bitmasks, data structures, greedy, two pointers
Difficulty: 2500