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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has just finished writing down the lecture on elvish languages. The language this week was "VwV" (pronounced as "uwu"). The writing system of this language consists of only two lowercase Latin letters: 'v' and 'w'.

Unfortunately, Polycarp has written all the lecture in cursive and without any spaces, so the notes look like a neverending sequence of squiggles. To be exact, Polycarp can't tell 'w' apart from 'vv' in his notes as both of them consist of the same two squiggles.

Luckily, his brother Monocarp has better writing habits, so Polycarp managed to take his notes and now wants to make his own notes more readable. To do that he can follow the notes of Monocarp and underline some letters in his own notes in such a way that there is no more ambiguity. If he underlines a 'v', then it can't be mistaken for a part of some 'w', and if the underlines a 'w', then it can't be mistaken for two adjacent letters 'v'.

What is the minimum number of letters Polycarp should underline to make his notes unambiguous?

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

Each of the next $$$t$$$ lines contains a non-empty string in VwV language, which consists only of lowercase Latin letters 'v' and 'w'. The length of the string does not exceed $$$100$$$.

## Output Format
For each testcase print a single integer: the minimum number of letters Polycarp should underline so that there is no ambiguity in his notes.

## Examples
```input
5
vv
v
w
vwv
vwvvwv
```
```output
1
0
1
1
3
```

## Note
In the first testcase it's enough to underline any of the two letters 'v'.

In the second testcase the letter 'v' is not ambiguous by itself already, so you don't have to underline anything.

In the third testcase you have to underline 'w', so that you don't mix it up with two letters 'v'.

In the fourth testcase you can underline 'w' to avoid all the ambiguity.

In the fifth testcase you can underline both letters 'w' and any of the two letters 'v' between them.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a local shop in your area getting prepared for the great holiday of Black Friday. There are $$$n$$$ items with prices $$$p_1, p_2, \dots, p_n$$$ on the display. They are ordered by price, so $$$p_1 \le p_2 \le \dots \le p_n$$$.

The shop has a prechosen discount value $$$k$$$. The Black Friday discount is applied in the following way: for a single purchase of $$$x$$$ items, you get the cheapest $$$\lfloor \frac x k \rfloor$$$ items of them for free ($$$\lfloor \frac x k \rfloor$$$ is $$$x$$$ divided by $$$k$$$ rounded down to the nearest integer). You can include each item in your purchase no more than once.

For example, if there are items with prices $$$[1, 1, 2, 2, 2, 3, 4, 5, 6]$$$ in the shop, and you buy items with prices $$$[1, 2, 2, 4, 5]$$$, and $$$k = 2$$$, then you get the cheapest $$$\lfloor \frac 5 2 \rfloor = 2$$$ for free. They are items with prices $$$1$$$ and $$$2$$$.

So you, being the naive customer, don't care about how much money you spend. However, you want the total price of the items you get for free to be as large as possible.

What is the maximum total price of the items you can get for free on a single purchase?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of testcases.

Then the description of $$$t$$$ testcases follows.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 200$$$; $$$1 \le k \le n$$$) — the number of items in the shop and the discount value, respectively.

The second line of each testcase contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$) — the prices of the items on the display of the shop. The items are ordered by their price, so $$$p_1 \le p_2 \le \dots \le p_n$$$.

## Output Format
Print a single integer for each testcase: the maximum total price of the items you can get for free on a single purchase.

## Examples
```input
5
5 2
1 3 4 6 7
6 3
1 2 3 4 5 6
6 3
3 3 4 4 5 5
1 1
7
4 4
1 3 3 7
```
```output
7
4
6
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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.
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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has a favorite sequence $$$a[1 \dots n]$$$ consisting of $$$n$$$ integers. He wrote it out on the whiteboard as follows:

- he wrote the number $$$a_1$$$ to the left side (at the beginning of the whiteboard);
- he wrote the number $$$a_2$$$ to the right side (at the end of the whiteboard);
- then as far to the left as possible (but to the right from $$$a_1$$$), he wrote the number $$$a_3$$$;
- then as far to the right as possible (but to the left from $$$a_2$$$), he wrote the number $$$a_4$$$;
- Polycarp continued to act as well, until he wrote out the entire sequence on the whiteboard.

The beginning of the result looks like this (of course, if $$$n \ge 4$$$).

For example, if $$$n=7$$$ and $$$a=[3, 1, 4, 1, 5, 9, 2]$$$, then Polycarp will write a sequence on the whiteboard $$$[3, 4, 5, 2, 9, 1, 1]$$$.

You saw the sequence written on the whiteboard and now you want to restore Polycarp's favorite sequence.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 300$$$) — the length of the sequence written on the whiteboard.

The next line contains $$$n$$$ integers $$$b_1, b_2,\ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the sequence written on the whiteboard.

## Output Format
Output $$$t$$$ answers to the test cases. Each answer — is a sequence $$$a$$$ that Polycarp wrote out on the whiteboard.

## Examples
```input
6
7
3 4 5 2 9 1 1
4
9 2 7 1
11
8 4 3 1 2 7 8 7 9 4 2
1
42
2
11 7
8
1 1 1 1 1 1 1 1
```
```output
3 1 4 1 5 9 2 
9 1 2 7 
8 2 4 4 3 9 1 7 2 8 7 
42 
11 7 
1 1 1 1 1 1 1 1
```

## Note
In the first test case, the sequence $$$a$$$ matches the sequence from the statement. The whiteboard states after each step look like this:

$$$[3] \Rightarrow [3, 1] \Rightarrow [3, 4, 1] \Rightarrow [3, 4, 1, 1] \Rightarrow [3, 4, 5, 1, 1] \Rightarrow [3, 4, 5, 9, 1, 1] \Rightarrow [3, 4, 5, 2, 9, 1, 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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has a string $$$s[1 \dots n]$$$ of length $$$n$$$ consisting of decimal digits. Polycarp performs the following operation with the string $$$s$$$ no more than once (i.e. he can perform operation $$$0$$$ or $$$1$$$ time):

- Polycarp selects two numbers $$$i$$$ and $$$j$$$ ($$$1 \leq i \leq j \leq n$$$) and removes characters from the $$$s$$$ string at the positions $$$i, i+1, i+2, \ldots, j$$$ (i.e. removes substring $$$s[i \dots j]$$$). More formally, Polycarp turns the string $$$s$$$ into the string $$$s_1 s_2 \ldots s_{i-1} s_{j+1} s_{j+2} \ldots s_{n}$$$.

For example, the string $$$s = $$$"20192020" Polycarp can turn into strings:

- "2020" (in this case $$$(i, j)=(3, 6)$$$ or $$$(i, j)=(1, 4)$$$);
- "2019220" (in this case $$$(i, j)=(6, 6)$$$);
- "020" (in this case $$$(i, j)=(1, 5)$$$);
- other operations are also possible, only a few of them are listed above.

Polycarp likes the string "2020" very much, so he is wondering if it is possible to turn the string $$$s$$$ into a string "2020" in no more than one operation? Note that you can perform zero operations.

## Input Format
The first line contains a positive integer $$$t$$$ ($$$1 \leq t \leq 1000 $$$) — number of test cases in the test. Then $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$4 \leq n \leq 200$$$) — length of the string $$$s$$$. The next line contains a string $$$s$$$ of length $$$n$$$ consisting of decimal digits. It is allowed that the string $$$s$$$ starts with digit 0.

## Output Format
For each test case, output on a separate line:

- "YES" if Polycarp can turn the string $$$s$$$ into a string "2020" in no more than one operation (i.e. he can perform $$$0$$$ or $$$1$$$ operation);
- "NO" otherwise.

You may print every letter of "YES" and "NO" in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

## Examples
```input
6
8
20192020
8
22019020
4
2020
5
20002
6
729040
6
200200
```
```output
YES
YES
YES
NO
NO
NO
```

## Note
In the first test case, Polycarp could choose $$$i=3$$$ and $$$j=6$$$.

In the second test case, Polycarp could choose $$$i=2$$$ and $$$j=5$$$.

In the third test case, Polycarp did not perform any operations with the string.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive number $$$x$$$. Find the smallest positive integer number that has the sum of digits equal to $$$x$$$ and all digits are distinct (unique).

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

Each test case consists of a single integer number $$$x$$$ ($$$1 \le x \le 50$$$).

## Output Format
Output $$$t$$$ answers to the test cases:

- if a positive integer number with the sum of digits equal to $$$x$$$ and all digits are different exists, print the smallest such number;
- otherwise print -1.

## Examples
```input
4
1
5
15
50
```
```output
1
5
69
-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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of this problem. The only difference between easy and hard versions is the constraints on $$$k$$$ and $$$m$$$ (in this version $$$k=2$$$ and $$$m=3$$$). Also, in this version of the problem, you DON'T NEED to output the answer by modulo.

You are given a sequence $$$a$$$ of length $$$n$$$ consisting of integers from $$$1$$$ to $$$n$$$. The sequence may contain duplicates (i.e. some elements can be equal).

Find the number of tuples of $$$m = 3$$$ elements such that the maximum number in the tuple differs from the minimum by no more than $$$k = 2$$$. Formally, you need to find the number of triples of indices $$$i < j < z$$$ such that

$$$$$$\max(a_i, a_j, a_z) - \min(a_i, a_j, a_z) \le 2.$$$$$$

For example, if $$$n=4$$$ and $$$a=[1,2,4,3]$$$, then there are two such triples ($$$i=1, j=2, z=4$$$ and $$$i=2, j=3, z=4$$$). If $$$n=4$$$ and $$$a=[1,1,1,1]$$$, then all four possible triples are suitable.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases. Then $$$t$$$ test cases follow.

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

The next line contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the sequence $$$a$$$.

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

## Output Format
Output $$$t$$$ answers to the given test cases. Each answer is the required number of triples of elements, such that the maximum value in the triple differs from the minimum by no more than $$$2$$$. Note that in difference to the hard version of the problem, you don't need to output the answer by modulo. You must output the exact value of the answer.

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

Now solve the problem and return the code.