apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a grid with $$$n$$$ rows and $$$m$$$ columns, where each cell has a positive integer written on it. Let's call a grid good, if in each row the sequence of numbers is sorted in a non-decreasing order. It means, that for each $$$1 \le i \le n$$$ and $$$2 \le j \le m$$$ the following holds: $$$a_{i,j} \ge a_{i, j-1}$$$.

You have to to do the following operation exactly once: choose two columns with indexes $$$i$$$ and $$$j$$$ (not necessarily different), $$$1 \le i, j \le m$$$, and swap them.

You are asked to determine whether it is possible to make the grid good after the swap and, if it is, find the columns that need to be swapped.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of rows and columns respectively.

Each of the next $$$n$$$ rows contains $$$m$$$ integers, $$$j$$$-th element of $$$i$$$-th row is $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — the number written in the $$$j$$$-th cell of the $$$i$$$-th row.

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

## Output Format
If after the swap it is impossible to get a good grid, output $$$-1$$$.

In the other case output $$$2$$$ integers — the indices of the columns that should be swapped to get a good grid.

If there are multiple solutions, print any.

## Examples
```input
5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2
```
```output
1 1
-1
1 2
1 3
1 1
```

## Note
In the first test case the grid is initially good, so we can, for example, swap the first column with itself.

In the second test case it is impossible to make the grid good.

In the third test case it is needed to swap the first and the second column, then the grid becomes good.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as $$$\operatorname{DIFF}(a) - \operatorname{MEX}(a)$$$, where $$$\operatorname{MEX}$$$ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $$$\operatorname{DIFF}$$$ is the number of different numbers in the array.

For example, $$$\operatorname{MEX}(\{1, 2, 3\}) = 0$$$, $$$\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

You should find the minimal cost of the array $$$a$$$ if you are allowed to make at most $$$k$$$ operations.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$) — the length of the array $$$a$$$ and the number of operations that you are allowed to make.

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 $$$10^5$$$.

## Output Format
For each test case output a single integer — minimal cost that it is possible to get making at most $$$k$$$ operations.

## Examples
```input
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
```
```output
0
1
2
0
```

## Note
In the first test case no operations are needed to minimize the value of $$$\operatorname{DIFF} - \operatorname{MEX}$$$.

In the second test case it is possible to replace $$$5$$$ by $$$1$$$. After that the array $$$a$$$ is $$$[0,\, 2,\, 4,\, 1]$$$, $$$\operatorname{DIFF} = 4$$$, $$$\operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3$$$, so the answer is $$$1$$$.

In the third test case one possible array $$$a$$$ is $$$[4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]$$$, $$$\operatorname{DIFF} = 5$$$, $$$\operatorname{MEX} = 3$$$.

In the fourth test case one possible array $$$a$$$ is $$$[1,\, 2,\, 3,\, 0,\, 0,\, 0]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's consider Euclid's algorithm for finding the greatest common divisor, where $$$t$$$ is a list:

There is an array $$$p$$$ of pairs of positive integers that are not greater than $$$m$$$. Initially, the list $$$t$$$ is empty. Then the function is run on each pair in $$$p$$$. After that the list $$$t$$$ is shuffled and given to you.

You have to find an array $$$p$$$ of any size not greater than $$$2 \cdot 10^4$$$ that produces the given list $$$t$$$, or tell that no such array exists.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$t$$$ and the constraint for integers in pairs.

The second line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le m$$$) — the elements of the array $$$t$$$.

## Output Format
- If the answer does not exist, output $$$-1$$$.
- If the answer exists, in the first line output $$$k$$$ ($$$1 \le k \le 2 \cdot 10^4$$$) — the size of your array $$$p$$$, i. e. the number of pairs in the answer. The $$$i$$$-th of the next $$$k$$$ lines should contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$) — the $$$i$$$-th pair in $$$p$$$.

If there are multiple valid answers you can output any of them.

## Examples
```input
7 20
1 8 1 6 3 2 3
```
```output
3
19 11
15 9
3 7
```
-----
```input
2 10
7 1
```
```output
-1
```
-----
```input
2 15
1 7
```
```output
1
15 8
```
-----
```input
1 1000000000
845063470
```
```output
-1
```

## Note
In the first sample let's consider the array $$$t$$$ for each pair:

- $$$(19,\, 11)$$$: $$$t = [8, 3, 2, 1]$$$;
- $$$(15,\, 9)$$$: $$$t = [6, 3]$$$;
- $$$(3,\, 7)$$$: $$$t = [1]$$$.

So in total $$$t = [8, 3, 2, 1, 6, 3, 1]$$$, which is the same as the input $$$t$$$ (up to a permutation).

In the second test case it is impossible to find such array $$$p$$$ of pairs that all integers are not greater than $$$10$$$ and $$$t = [7, 1]$$$

In the third test case for the pair $$$(15,\, 8)$$$ array $$$t$$$ will be $$$[7, 1]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary string $$$s$$$. You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of $$$s$$$ should be in exactly one substring.

## 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.

Each test case contains a binary string $$$s$$$ ($$$1 \le |s| \le 10^6$$$).

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

## Output Format
For each test case output the answer to the problem as follows:

- If the answer does not exist, output $$$-1$$$.
- If the answer exists, firstly output an integer $$$k$$$ — the number of substrings in the answer. After that output $$$k$$$ non-intersecting substrings, for $$$i$$$-th substring output two integers $$$l_i, r_i$$$ ($$$1 \le l_i, r_i \le |s|$$$) — the description of $$$i$$$-th substring.

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

## Examples
```input
4
00000
01101
0111011001011
000111100111110
```
```output
-1

3
1 3
4 4
5 5

8
1 2
3 3
4 4
5 6
7 7
8 10
11 12
13 13

5
1 5
6 7
8 11
12 14
15 15
```

## Note
In the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2.

In the second test case such cut is valid:

- $$$011_2 = 3_{10}$$$,
- $$$0_2 = 0_{10}$$$,
- $$$1_2 = 1_{10}$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive integer $$$n$$$. Your task is to find any three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) for which $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$, or determine that there are no such integers.

Here $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$. For example, $$$2 \oplus 4 = 6$$$ and $$$3 \oplus 1=2$$$.

## 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 following lines contain the descriptions of the test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

## Output Format
For each test case, print any three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) for which $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$. If no such integers exist, print $$$-1$$$.

## Examples
```input
5
4
1
12
2046
194723326
```
```output
3 3 1
-1
2 4 6
69 420 666
12345678 87654321 100000000
```

## Note
In the first test case, $$$a=3$$$, $$$b=3$$$, $$$c=1$$$, so $$$(3 \oplus 3)+(3 \oplus 1) + (3 \oplus 1)=0+2+2=4$$$.

In the second test case, there are no solutions.

In the third test case, $$$(2 \oplus 4)+(4 \oplus 6) + (2 \oplus 6)=6+2+4=12$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two even integers $$$n$$$ and $$$m$$$. Your task is to find any binary matrix $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns where every cell $$$(i,j)$$$ has exactly two neighbours with a different value than $$$a_{i,j}$$$.

Two cells in the matrix are considered neighbours if and only if they share a side. More formally, the neighbours of cell $$$(x,y)$$$ are: $$$(x-1,y)$$$, $$$(x,y+1)$$$, $$$(x+1,y)$$$ and $$$(x,y-1)$$$.

It can be proven that under the given constraints, an answer always exists.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

The only line of each test case contains two even integers $$$n$$$ and $$$m$$$ ($$$2 \le n,m \le 50$$$) — the height and width of the binary matrix, respectively.

## Output Format
For each test case, print $$$n$$$ lines, each of which contains $$$m$$$ numbers, equal to $$$0$$$ or $$$1$$$ — any binary matrix which satisfies the constraints described in the statement.

It can be proven that under the given constraints, an answer always exists.

## Examples
```input
3
2 4
2 2
4 4
```
```output
1 0 0 1
0 1 1 0
1 0
0 1
1 0 1 0
0 0 1 1
1 1 0 0
0 1 0 1
```

## Note
White means $$$0$$$, black means $$$1$$$.

The binary matrix from the first test caseThe binary matrix from the second test caseThe binary matrix from the third test case

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$a_1,a_2,\ldots,a_n$$$ of integers from $$$0$$$ to $$$n - 1$$$. Your task is to find how many permutations $$$b_1,b_2,\ldots,b_n$$$ are similar to permutation $$$a$$$.

Two permutations $$$a$$$ and $$$b$$$ of size $$$n$$$ are considered similar if for all intervals $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$), the following condition is satisfied: $$$$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$$$$$ where the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\ldots,c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in collection $$$c$$$. For example, $$$\operatorname{MEX}([1,2,3,4,5])=0$$$, and $$$\operatorname{MEX}([0,1,2,4,5])=3$$$.

Since the total number of such permutations can be very large, you will have to print its remainder modulo $$$10^9+7$$$.

In this problem, a permutation of size $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$0$$$ to $$$n-1$$$ in arbitrary order. For example, $$$[1,0,2,4,3]$$$ is a permutation, while $$$[0,1,1]$$$ is not, since $$$1$$$ appears twice in the array. $$$[0,1,3]$$$ is also not a permutation, since $$$n=3$$$ and there is a $$$3$$$ in the array.

## Input Format
Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

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

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$) — the elements of permutation $$$a$$$.

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

## Output Format
For each test case, print a single integer, the number of permutations similar to permutation $$$a$$$, taken modulo $$$10^9+7$$$.

## Examples
```input
5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4
```
```output
2
1
1
4
72
```

## Note
For the first test case, the only permutations similar to $$$a=[4,0,3,2,1]$$$ are $$$[4,0,3,2,1]$$$ and $$$[4,0,2,3,1]$$$.

For the second and third test cases, the given permutations are only similar to themselves.

For the fourth test case, there are $$$4$$$ permutations similar to $$$a=[1,2,4,0,5,3]$$$:

- $$$[1,2,4,0,5,3]$$$;
- $$$[1,2,5,0,4,3]$$$;
- $$$[1,4,2,0,5,3]$$$;
- $$$[1,5,2,0,4,3]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$ and an array $$$a_1,a_2,\ldots,a_n$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \lt n$$$) for which $$$a_i \neq a_{i+1}$$$ and delete both $$$a_i$$$ and $$$a_{i+1}$$$ from the array. After deleting $$$a_i$$$ and $$$a_{i+1}$$$, the remaining parts of the array are concatenated.

For example, if $$$a=[1,4,3,3,6,2]$$$, then after performing an operation with $$$i=2$$$, the resulting array will be $$$[1,3,6,2]$$$.

What is the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing several (perhaps none) of the aforementioned operations?

## Input Format
Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

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

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

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10\,000$$$.

## Output Format
For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing a sequence of operations.

## Examples
```input
5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3
```
```output
3
1
0
4
2
```

## Note
For the first testcase, an optimal sequence of operations would be: $$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$.

For the second testcase, all elements in the array are already equal.

For the third testcase, the only possible sequence of operations is: $$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$. Note that, according to the statement, the elements deleted at each step must be different.

For the fourth testcase, the optimal sequence of operations is: $$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$.

For the fifth testcase, one possible reachable array of two equal elements is $$$[4,4]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are beta testing the new secret Terraria update. This update will add quests to the game!

Simply, the world map can be represented as an array of length $$$n$$$, where the $$$i$$$-th column of the world has height $$$a_i$$$.

There are $$$m$$$ quests you have to test. The $$$j$$$-th of them is represented by two integers $$$s_j$$$ and $$$t_j$$$. In this quest, you have to go from the column $$$s_j$$$ to the column $$$t_j$$$. At the start of the quest, you are appearing at the column $$$s_j$$$.

In one move, you can go from the column $$$x$$$ to the column $$$x-1$$$ or to the column $$$x+1$$$. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height $$$p$$$ to the column with the height $$$q$$$, then you get some amount of fall damage. If the height $$$p$$$ is greater than the height $$$q$$$, you get $$$p - q$$$ fall damage, otherwise you fly up and get $$$0$$$ damage.

For each of the given quests, determine the minimum amount of fall damage you can get during this quest.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5; 1 \le m \le 10^5$$$) — the number of columns in the world and the number of quests you have to test, respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the height of the $$$i$$$-th column of the world.

The next $$$m$$$ lines describe quests. The $$$j$$$-th of them contains two integers $$$s_j$$$ and $$$t_j$$$ ($$$1 \le s_j, t_j \le n; s_j \ne t_j$$$), which means you have to move from the column $$$s_j$$$ to the column $$$t_j$$$ during the $$$j$$$-th quest.

Note that $$$s_j$$$ can be greater than $$$t_j$$$.

## Output Format
Print $$$m$$$ integers. The $$$j$$$-th of them should be the minimum amount of fall damage you can get during the $$$j$$$-th quest completion.

## Examples
```input
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2
```
```output
2
10
0
7
3
1
```

Now solve the problem and return the code.