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

# Problem
The final of Berland Chess Team Championship is going to be held soon. Two teams consisting of $$$n$$$ chess players each will compete for first place in the tournament. The skill of the $$$i$$$-th player in the first team is $$$a_i$$$, and the skill of the $$$i$$$-th player in the second team is $$$b_i$$$. The match will be held as follows: each player of the first team will play a game against one player from the second team in such a way that every player has exactly one opponent. Formally, if the player $$$i$$$ from the first team opposes the player $$$p_i$$$ from the second team, then $$$[p_1, p_2, \dots, p_n]$$$ is a permutation (a sequence where each integer from $$$1$$$ to $$$n$$$ appears exactly once).

Whenever two players of almost equal skill play a game, it will likely result in a tie. Chess fans don't like ties, so the organizers of the match should distribute the players in such a way that ties are unlikely.

Let the unfairness of the match be the following value: $$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$. Your task is to assign each player from the first team an opponent from the second team so that the unfairness is maximum possible (the greater it is, the smaller the probability of ties is, that's why you should maximize it).

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

Each test case consists of three lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 3000$$$) — the number of players in each team.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$$$) — the skills of players of the first team.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_n \le 10^6$$$) — the skills of players of the second team.

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

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

Print $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ on a separate line. All integers from $$$1$$$ to $$$n$$$ should occur among them exactly once. The value of $$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$ should be maximum possible. If there are multiple answers, print any of them.

## Examples
```input
4
4
1 2 3 4
1 2 3 4
2
1 100
100 101
2
1 100
50 51
5
1 1 1 1 1
3 3 3 3 3
```
```output
3 4 1 2
1 2
2 1
5 4 2 3 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a matrix consisting of $$$n$$$ rows and $$$m$$$ columns. The matrix contains lowercase letters of the Latin alphabet.

You can perform the following operation any number of times you want to: choose two integers $$$i$$$ ($$$1 \le i \le m$$$) and $$$k$$$ ($$$0 < k < n$$$), and shift every column $$$j$$$ such that $$$i \le j \le m$$$ cyclically by $$$k$$$. The shift is performed upwards.

For example, if you have a matrix

$$$\left( \begin{array} \\ a & b & c \\ d & e & f \\ g & h & i \end{array}\right) $$$

$$$\left( \begin{array} \\ a & e & f \\ d & h & i \\ g & b & c \end{array}\right) $$$

You have to process $$$q$$$ queries. Each of the queries is a string of length $$$m$$$ consisting of lowercase letters of the Latin alphabet. For each query, you have to calculate the minimum number of operations described above you have to perform so that at least one row of the matrix is equal to the string from the query. Note that all queries are independent, that is, the operations you perform in a query don't affect the initial matrix in other queries.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n, m, q \le 2.5 \cdot 10^5$$$; $$$n \cdot m \le 5 \cdot 10^5$$$; $$$q \cdot m \le 5 \cdot 10^5$$$) — the number of rows and columns in the matrix and the number of queries, respectively.

The next $$$n$$$ lines contains $$$m$$$ lowercase Latin letters each — elements of the matrix.

The following $$$q$$$ lines contains a description of queries — strings of length $$$m$$$ consisting of lowercase letters of the Latin alphabet.

## Output Format
Print $$$q$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of operations you have to perform so that the matrix contains a string from the $$$i$$$-th query or $$$-1$$$ if the specified string cannot be obtained.

## Examples
```input
3 5 4
abacc
ccbba
ccabc
abacc
acbbc
ababa
acbbc
```
```output
0
2
1
2
```
-----
```input
6 4 4
daac
bcba
acad
cbdc
aaaa
bcbb
dcdd
acba
bbbb
dbcd
```
```output
3
1
2
-1
```
-----
```input
5 10 5
ltjksdyfgg
cbhpsereqn
ijndtzbzcf
ghgcgeadep
bfzdgxqmqe
ibgcgzyfep
bbhdgxqmqg
ltgcgxrzep
ljnpseldgn
ghhpseyzcf
```
```output
5
3
5
-1
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: 6.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of integers $$$a$$$ of size $$$n$$$. This array is non-decreasing, i. e. $$$a_1 \le a_2 \le \dots \le a_n$$$.

You have to find arrays of integers $$$b$$$ of size $$$2n - 1$$$, such that:

- $$$b_{2i-1} = a_i$$$ ($$$1 \le i \le n$$$);
- array $$$b$$$ is non-decreasing;
- $$$b_1 \oplus b_2 \oplus \dots \oplus b_{2n-1} = 0$$$ ($$$\oplus$$$ denotes bitwise XOR operation: https://en.wikipedia.org/wiki/Exclusive_or. In Kotlin, it is xor function).

Calculate the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 17$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers ($$$0 \le a_i \le 2^{60} - 1; a_i \le a_{i+1}$$$) — elements of the array $$$a$$$.

## Output Format
Print a single integer — the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

## Examples
```input
3
0 1 3
```
```output
2
```
-----
```input
4
0 3 6 7
```
```output
6
```
-----
```input
5
1 5 9 10 23
```
```output
20
```
-----
```input
10
39 62 64 79 81 83 96 109 120 122
```
```output
678132
```

Now solve the problem and return the code.