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
Among Johnny's numerous hobbies, there are two seemingly harmless ones: applying bitwise operations and sneaking into his dad's office. As it is usually the case with small children, Johnny is unaware that combining these two activities can get him in a lot of trouble.

There is a set $$$S$$$ containing very important numbers on his dad's desk. The minute Johnny heard about it, he decided that it's a good idea to choose a positive integer $$$k$$$ and replace each element $$$s$$$ of the set $$$S$$$ with $$$s \oplus k$$$ ($$$\oplus$$$ denotes the exclusive or operation).

Help him choose such $$$k$$$ that Johnny's dad will not see any difference after his son is done playing (i.e. Johnny will get the same set as before playing). It is possible that no such number exists. It is also possible that there are many of them. In such a case, output the smallest one. Note that the order of elements in a set doesn't matter, i.e. set $$$\{1, 2, 3\}$$$ equals to set $$$\{2, 1, 3\}$$$.

Formally, find the smallest positive integer $$$k$$$ such that $$$\{s \oplus k | s \in S\} = S$$$ or report that there is no such number.

For example, if $$$S = \{1, 3, 4\}$$$ and $$$k = 2$$$, new set will be equal to $$$\{3, 1, 6\}$$$. If $$$S = \{0, 1, 2, 3\}$$$ and $$$k = 1$$$, after playing set will stay the same.

## Input Format
In the first line of input, there is a single integer $$$t$$$ ($$$1 \leq t \leq 1024$$$), the number of test cases. In the next lines, $$$t$$$ test cases follow. Each of them consists of two lines.

In the first line there is a single integer $$$n$$$ ($$$1 \leq n \leq 1024$$$) denoting the number of elements in set $$$S$$$. Second line consists of $$$n$$$ distinct integers $$$s_i$$$ ($$$0 \leq s_i < 1024$$$), elements of $$$S$$$.

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

## Output Format
Print $$$t$$$ lines; $$$i$$$-th line should contain the answer to the $$$i$$$-th test case, the minimal positive integer $$$k$$$ satisfying the conditions or $$$-1$$$ if no such $$$k$$$ exists.

## Examples
```input
6
4
1 0 2 3
6
10 7 14 8 3 12
2
0 2
3
1 2 3
6
1 4 6 10 11 12
2
0 1023
```
```output
1
4
2
-1
-1
1023
```

## Note
In the first test case, the answer is $$$1$$$ because it is a minimum positive integer and it satisfies all the conditions.

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
The last contest held on Johnny's favorite competitive programming platform has been received rather positively. However, Johnny's rating has dropped again! He thinks that the presented tasks are lovely, but don't show the truth about competitors' skills.

The boy is now looking at the ratings of consecutive participants written in a binary system. He thinks that the more such ratings differ, the more unfair is that such people are next to each other. He defines the difference between two numbers as the number of bit positions, where one number has zero, and another has one (we suppose that numbers are padded with leading zeros to the same length). For example, the difference of $$$5 = 101_2$$$ and $$$14 = 1110_2$$$ equals to $$$3$$$, since $$$0101$$$ and $$$1110$$$ differ in $$$3$$$ positions. Johnny defines the unfairness of the contest as the sum of such differences counted for neighboring participants.

Johnny has just sent you the rating sequence and wants you to find the unfairness of the competition. You have noticed that you've got a sequence of consecutive integers from $$$0$$$ to $$$n$$$. That's strange, but the boy stubbornly says that everything is right. So help him and find the desired unfairness for received numbers.

## Input Format
The input consists of multiple test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases. The following $$$t$$$ lines contain a description of test cases.

The first and only line in each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{18})$$$.

## Output Format
Output $$$t$$$ lines. For each test case, you should output a single line with one integer — the unfairness of the contest if the rating sequence equals to $$$0$$$, $$$1$$$, ..., $$$n - 1$$$, $$$n$$$.

## Examples
```input
5
5
7
11
1
2000000000000
```
```output
8
11
19
1
3999999999987
```

## Note
For $$$n = 5$$$ we calculate unfairness of the following sequence (numbers from $$$0$$$ to $$$5$$$ written in binary with extra leading zeroes, so they all have the same length):

- $$$000$$$
- $$$001$$$
- $$$010$$$
- $$$011$$$
- $$$100$$$
- $$$101$$$

The differences are equal to $$$1$$$, $$$2$$$, $$$1$$$, $$$3$$$, $$$1$$$ respectively, so unfairness is equal to $$$1 + 2 + 1 + 3 + 1 = 8$$$.

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 an array consisting of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Initially $$$a_x = 1$$$, all other elements are equal to $$$0$$$.

You have to perform $$$m$$$ operations. During the $$$i$$$-th operation, you choose two indices $$$c$$$ and $$$d$$$ such that $$$l_i \le c, d \le r_i$$$, and swap $$$a_c$$$ and $$$a_d$$$.

Calculate the number of indices $$$k$$$ such that it is possible to choose the operations so that $$$a_k = 1$$$ in the end.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the description of $$$t$$$ testcases follow.

The first line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 100$$$; $$$1 \le x \le n$$$).

Each of next $$$m$$$ lines contains the descriptions of the operations; the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

## Output Format
For each test case print one integer — the number of indices $$$k$$$ such that it is possible to choose the operations so that $$$a_k = 1$$$ in the end.

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

## Note
In the first test case, it is possible to achieve $$$a_k = 1$$$ for every $$$k$$$. To do so, you may use the following operations:

1. swap $$$a_k$$$ and $$$a_4$$$;
2. swap $$$a_2$$$ and $$$a_2$$$;
3. swap $$$a_5$$$ and $$$a_5$$$.

In the second test case, only $$$k = 1$$$ and $$$k = 2$$$ are possible answers. To achieve $$$a_1 = 1$$$, you have to swap $$$a_1$$$ and $$$a_1$$$ during the second operation. To achieve $$$a_2 = 1$$$, you have to swap $$$a_1$$$ and $$$a_2$$$ during the second operation.

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.5 seconds
Memory limit: 256.0 MB

# Problem
You are given a matrix with $$$n$$$ rows (numbered from $$$1$$$ to $$$n$$$) and $$$m$$$ columns (numbered from $$$1$$$ to $$$m$$$). A number $$$a_{i, j}$$$ is written in the cell belonging to the $$$i$$$-th row and the $$$j$$$-th column, each number is either $$$0$$$ or $$$1$$$.

A chip is initially in the cell $$$(1, 1)$$$, and it will be moved to the cell $$$(n, m)$$$. During each move, it either moves to the next cell in the current row, or in the current column (if the current cell is $$$(x, y)$$$, then after the move it can be either $$$(x + 1, y)$$$ or $$$(x, y + 1)$$$). The chip cannot leave the matrix.

Consider each path of the chip from $$$(1, 1)$$$ to $$$(n, m)$$$. A path is called palindromic if the number in the first cell is equal to the number in the last cell, the number in the second cell is equal to the number in the second-to-last cell, and so on.

Your goal is to change the values in the minimum number of cells so that every path is palindromic.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 30$$$) — the dimensions of the matrix.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains $$$m$$$ integers $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, m}$$$ ($$$0 \le a_{i, j} \le 1$$$).

## Output Format
For each test case, print one integer — the minimum number of cells you have to change so that every path in the matrix is palindromic.

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

## Note
The resulting matrices in the first three test cases:

$$$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}$$$

$$$\begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}$$$

$$$\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$$$

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 two arrays $$$a_1, a_2, \dots , a_n$$$ and $$$b_1, b_2, \dots , b_m$$$. Array $$$b$$$ is sorted in ascending order ($$$b_i < b_{i + 1}$$$ for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$).

You have to divide the array $$$a$$$ into $$$m$$$ consecutive subarrays so that, for each $$$i$$$ from $$$1$$$ to $$$m$$$, the minimum on the $$$i$$$-th subarray is equal to $$$b_i$$$. Note that each element belongs to exactly one subarray, and they are formed in such a way: the first several elements of $$$a$$$ compose the first subarray, the next several elements of $$$a$$$ compose the second subarray, and so on.

For example, if $$$a = [12, 10, 20, 20, 25, 30]$$$ and $$$b = [10, 20, 30]$$$ then there are two good partitions of array $$$a$$$:

1. $$$[12, 10, 20], [20, 25], [30]$$$;
2. $$$[12, 10], [20, 20, 25], [30]$$$.

You have to calculate the number of ways to divide the array $$$a$$$. Since the number can be pretty large print it modulo 998244353.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of arrays $$$a$$$ and $$$b$$$ respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots , b_m$$$ ($$$1 \le b_i \le 10^9; b_i < b_{i+1}$$$) — the array $$$b$$$.

## Output Format
In only line print one integer — the number of ways to divide the array $$$a$$$ modulo 998244353.

## Examples
```input
6 3
12 10 20 20 25 30
10 20 30
```
```output
2
```
-----
```input
4 2
1 3 3 7
3 7
```
```output
0
```
-----
```input
8 2
1 2 2 2 2 2 2 2
1 2
```
```output
7
```

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Let's denote the function $$$f(s)$$$ that takes a string $$$s$$$ consisting of lowercase Latin letters and dots, and returns a string consisting of lowercase Latin letters as follows:

1. let $$$r$$$ be an empty string;
2. process the characters of $$$s$$$ from left to right. For each character $$$c$$$, do the following: if $$$c$$$ is a lowercase Latin letter, append $$$c$$$ at the end of the string $$$r$$$; otherwise, delete the last character from $$$r$$$ (if $$$r$$$ is empty before deleting the last character — the function crashes);
3. return $$$r$$$ as the result of the function.

You are given two strings $$$s$$$ and $$$t$$$. You have to delete the minimum possible number of characters from $$$s$$$ so that $$$f(s) = t$$$ (and the function does not crash). Note that you aren't allowed to insert new characters into $$$s$$$ or reorder the existing ones.

## Input Format
The input consists of two lines: the first one contains $$$s$$$ — a string consisting of lowercase Latin letters and dots, the second one contains $$$t$$$ — a string consisting of lowercase Latin letters ($$$1 \le |t| \le |s| \le 10000$$$).

Additional constraint on the input: it is possible to remove some number of characters from $$$s$$$ so that $$$f(s) = t$$$.

## Output Format
Print one integer — the minimum possible number of characters you have to delete from $$$s$$$ so $$$f(s)$$$ does not crash and returns $$$t$$$ as the result of the function.

## Examples
```input
a.ba.b.
abb
```
```output
2
```
-----
```input
.bbac..a.c.cd
bacd
```
```output
3
```
-----
```input
c..code..c...o.d.de
code
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ strings $$$s_1, s_2, \ldots, s_n$$$ consisting of lowercase Latin letters.

In one operation you can remove a character from a string $$$s_i$$$ and insert it to an arbitrary position in a string $$$s_j$$$ ($$$j$$$ may be equal to $$$i$$$). You may perform this operation any number of times. Is it possible to make all $$$n$$$ strings equal?

## Input Format
The first line contains $$$t$$$ ($$$1 \le t \le 10$$$): the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$): the number of strings.

$$$n$$$ lines follow, the $$$i$$$-th line contains $$$s_i$$$ ($$$1 \le \lvert s_i \rvert \le 1000$$$).

The sum of lengths of all strings in all test cases does not exceed $$$1000$$$.

## Output Format
If it is possible to make the strings equal, print "YES" (without quotes).

Otherwise, print "NO" (without quotes).

You can output each character in either lowercase or uppercase.

## Examples
```input
4
2
caa
cbb
3
cba
cba
cbb
4
ccab
cbac
bca
acbcc
4
acb
caf
c
cbafc
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, you can do the following:

- Remove the third character of the first string and insert it after the second character of the second string, making the two strings "ca" and "cbab" respectively.
- Remove the second character of the second string and insert it after the second character of the first string, making both strings equal to "cab".

In the second test case, it is impossible to make all $$$n$$$ strings equal.

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 call a list of positive integers $$$a_0, a_1, ..., a_{n-1}$$$ a power sequence if there is a positive integer $$$c$$$, so that for every $$$0 \le i \le n-1$$$ then $$$a_i = c^i$$$.

Given a list of $$$n$$$ positive integers $$$a_0, a_1, ..., a_{n-1}$$$, you are allowed to:

- Reorder the list (i.e. pick a permutation $$$p$$$ of $$$\{0,1,...,n - 1\}$$$ and change $$$a_i$$$ to $$$a_{p_i}$$$), then
- Do the following operation any number of times: pick an index $$$i$$$ and change $$$a_i$$$ to $$$a_i - 1$$$ or $$$a_i + 1$$$ (i.e. increment or decrement $$$a_i$$$ by $$$1$$$) with a cost of $$$1$$$.

Find the minimum cost to transform $$$a_0, a_1, ..., a_{n-1}$$$ into a power sequence.

## Input Format
The first line contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_0, a_1, ..., a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$).

## Output Format
Print the minimum cost to transform $$$a_0, a_1, ..., a_{n-1}$$$ into a power sequence.

## Examples
```input
3
1 3 2
```
```output
1
```
-----
```input
3
1000000000 1000000000 1000000000
```
```output
1999982505
```

## Note
In the first example, we first reorder $$$\{1, 3, 2\}$$$ into $$$\{1, 2, 3\}$$$, then increment $$$a_2$$$ to $$$4$$$ with cost $$$1$$$ to get a power sequence $$$\{1, 2, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Initially, you have the array $$$a$$$ consisting of one element $$$1$$$ ($$$a = [1]$$$).

In one move, you can do one of the following things:

- Increase some (single) element of $$$a$$$ by $$$1$$$ (choose some $$$i$$$ from $$$1$$$ to the current length of $$$a$$$ and increase $$$a_i$$$ by one);
- Append the copy of some (single) element of $$$a$$$ to the end of the array (choose some $$$i$$$ from $$$1$$$ to the current length of $$$a$$$ and append $$$a_i$$$ to the end of the array).

For example, consider the sequence of five moves:

1. You take the first element $$$a_1$$$, append its copy to the end of the array and get $$$a = [1, 1]$$$.
2. You take the first element $$$a_1$$$, increase it by $$$1$$$ and get $$$a = [2, 1]$$$.
3. You take the second element $$$a_2$$$, append its copy to the end of the array and get $$$a = [2, 1, 1]$$$.
4. You take the first element $$$a_1$$$, append its copy to the end of the array and get $$$a = [2, 1, 1, 2]$$$.
5. You take the fourth element $$$a_4$$$, increase it by $$$1$$$ and get $$$a = [2, 1, 1, 3]$$$.

Your task is to find the minimum number of moves required to obtain the array with the sum at least $$$n$$$.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the lower bound on the sum of the array.

## Output Format
For each test case, print the answer: the minimum number of moves required to obtain the array with the sum at least $$$n$$$.

## Examples
```input
5
1
5
42
1337
1000000000
```
```output
0
3
11
72
63244
```

Now solve the problem and return the code.