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
A string $$$s$$$ of length $$$n$$$, consisting of lowercase letters of the English alphabet, is given.

You must choose some number $$$k$$$ between $$$0$$$ and $$$n$$$. Then, you select $$$k$$$ characters of $$$s$$$ and permute them however you want. In this process, the positions of the other $$$n-k$$$ characters remain unchanged. You have to perform this operation exactly once.

For example, if $$$s=\texttt{"andrea"}$$$, you can choose the $$$k=4$$$ characters $$$\texttt{"a_d_ea"}$$$ and permute them into $$$\texttt{"d_e_aa"}$$$ so that after the operation the string becomes $$$\texttt{"dneraa"}$$$.

Determine the minimum $$$k$$$ so that it is possible to sort $$$s$$$ alphabetically (that is, after the operation its characters appear in alphabetical order).

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$. It is guaranteed that $$$s$$$ contains only lowercase letters of the English alphabet.

## Output Format
For each test case, output the minimum $$$k$$$ that allows you to obtain a string sorted alphabetically, through the operation described above.

## Examples
```input
4
3
lol
10
codeforces
5
aaaaa
4
dcba
```
```output
2
6
0
4
```

## Note
In the first test case, we can choose the $$$k=2$$$ characters $$$\texttt{"_ol"}$$$ and rearrange them as $$$\texttt{"_lo"}$$$ (so the resulting string is $$$\texttt{"llo"}$$$). It is not possible to sort the string choosing strictly less than $$$2$$$ characters.

In the second test case, one possible way to sort $$$s$$$ is to consider the $$$k=6$$$ characters $$$\texttt{"_o__force_"}$$$ and rearrange them as $$$\texttt{"_c__efoor_"}$$$ (so the resulting string is $$$\texttt{"ccdeefoors"}$$$). One can show that it is not possible to sort the string choosing strictly less than $$$6$$$ characters.

In the third test case, string $$$s$$$ is already sorted (so we can choose $$$k=0$$$ characters).

In the fourth test case, we can choose all $$$k=4$$$ characters $$$\texttt{"dcba"}$$$ and reverse the whole string (so the resulting string is $$$\texttt{"abcd"}$$$).

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
On a circle lie $$$2n$$$ distinct points, with the following property: however you choose $$$3$$$ chords that connect $$$3$$$ disjoint pairs of points, no point strictly inside the circle belongs to all $$$3$$$ chords. The points are numbered $$$1, \, 2, \, \dots, \, 2n$$$ in clockwise order.

Initially, $$$k$$$ chords connect $$$k$$$ pairs of points, in such a way that all the $$$2k$$$ endpoints of these chords are distinct.

You want to draw $$$n - k$$$ additional chords that connect the remaining $$$2(n - k)$$$ points (each point must be an endpoint of exactly one chord).

In the end, let $$$x$$$ be the total number of intersections among all $$$n$$$ chords. Compute the maximum value that $$$x$$$ can attain if you choose the $$$n - k$$$ chords optimally.

Note that the exact position of the $$$2n$$$ points is not relevant, as long as the property stated in the first paragraph holds.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le n$$$) — half the number of points and the number of chords initially drawn.

Then $$$k$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, \, y_i \le 2n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th chord. It is guaranteed that the $$$2k$$$ numbers $$$x_1, \, y_1, \, x_2, \, y_2, \, \dots, \, x_k, \, y_k$$$ are all distinct.

## Output Format
For each test case, output the maximum number of intersections that can be obtained by drawing $$$n - k$$$ additional chords.

## Examples
```input
4
4 2
8 2
1 5
1 1
2 1
2 0
10 6
14 6
2 20
9 10
13 18
15 12
11 7
```
```output
4
0
1
14
```

## Note
In the first test case, there are three ways to draw the $$$2$$$ additional chords, shown below (black chords are the ones initially drawn, while red chords are the new ones):

We see that the third way gives the maximum number of intersections, namely $$$4$$$.

In the second test case, there are no more chords to draw. Of course, with only one chord present there are no intersections.

In the third test case, we can make at most one intersection by drawing chords $$$1-3$$$ and $$$2-4$$$, as shown below:

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 sequence of $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$.

Does there exist a sequence of $$$n$$$ integers $$$b_1, \, b_2, \, \dots, \, b_n$$$ such that the following property holds?

- For each $$$1 \le i \le n$$$, there exist two (not necessarily distinct) indices $$$j$$$ and $$$k$$$ ($$$1 \le j, \, k \le n$$$) such that $$$a_i = b_j - b_k$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10$$$).

The second line of each test case contains the $$$n$$$ integers $$$a_1, \, \dots, \, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$).

## Output Format
For each test case, output a line containing YES if a sequence $$$b_1, \, \dots, \, b_n$$$ satisfying the required property exists, and NO otherwise.

## Examples
```input
5
5
4 -7 -1 5 10
1
0
3
1 10 100
4
-3 2 10 2
9
25 -171 250 174 152 242 100 -205 -258
```
```output
YES
YES
NO
YES
YES
```

## Note
In the first test case, the sequence $$$b = [-9, \, 2, \, 1, \, 3, \, -2]$$$ satisfies the property. Indeed, the following holds:

- $$$a_1 = 4 = 2 - (-2) = b_2 - b_5$$$;
- $$$a_2 = -7 = -9 - (-2) = b_1 - b_5$$$;
- $$$a_3 = -1 = 1 - 2 = b_3 - b_2$$$;
- $$$a_4 = 5 = 3 - (-2) = b_4 - b_5$$$;
- $$$a_5 = 10 = 1 - (-9) = b_3 - b_1$$$.

In the second test case, it is sufficient to choose $$$b = [0]$$$, since $$$a_1 = 0 = 0 - 0 = b_1 - b_1$$$.

In the third test case, it is possible to show that no sequence $$$b$$$ of length $$$3$$$ satisfies the property.

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 numbers $$$1, \, 2, \, \dots, \, n \cdot k$$$ are colored with $$$n$$$ colors. These colors are indexed by $$$1, \, 2, \, \dots, \, n$$$. For each $$$1 \le i \le n$$$, there are exactly $$$k$$$ numbers colored with color $$$i$$$.

Let $$$[a, \, b]$$$ denote the interval of integers between $$$a$$$ and $$$b$$$ inclusive, that is, the set $$$\{a, \, a + 1, \, \dots, \, b\}$$$. You must choose $$$n$$$ intervals $$$[a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]$$$ such that:

- for each $$$1 \le i \le n$$$, it holds $$$1 \le a_i < b_i \le n \cdot k$$$;
- for each $$$1 \le i \le n$$$, the numbers $$$a_i$$$ and $$$b_i$$$ are colored with color $$$i$$$;
- each number $$$1 \le x \le n \cdot k$$$ belongs to at most $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals.

One can show that such a family of intervals always exists under the given constraints.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — the number of colors and the number of occurrences of each color.

The second line contains $$$n \cdot k$$$ integers $$$c_1, \, c_2, \, \dots, \, c_{nk}$$$ ($$$1 \le c_j \le n$$$), where $$$c_j$$$ is the color of number $$$j$$$. It is guaranteed that, for each $$$1 \le i \le n$$$, it holds $$$c_j = i$$$ for exactly $$$k$$$ distinct indices $$$j$$$.

## Output Format
Output $$$n$$$ lines. The $$$i$$$-th line should contain the two integers $$$a_i$$$ and $$$b_i$$$.

If there are multiple valid choices of the intervals, output any.

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

## Note
In the first sample, each number can be contained in at most $$$\left\lceil \frac{4}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:

In the second sample, the only interval to be chosen is forced to be $$$[1, \, 2]$$$, and each number is indeed contained in at most $$$\left\lceil \frac{1}{2 - 1} \right\rceil = 1$$$ interval.

In the third sample, each number can be contained in at most $$$\left\lceil \frac{3}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:

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 the organizer of the famous "Zurich Music Festival". There will be $$$n$$$ singers who will perform at the festival, identified by the integers $$$1$$$, $$$2$$$, $$$\dots$$$, $$$n$$$. You must choose in which order they are going to perform on stage.

You have $$$m$$$ friends and each of them has a set of favourite singers. More precisely, for each $$$1\le i\le m$$$, the $$$i$$$-th friend likes singers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$.

A friend of yours is happy if the singers he likes perform consecutively (in an arbitrary order). An ordering of the singers is valid if it makes all your friends happy.

Compute the number of valid orderings modulo $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,\,m\le 100$$$) — the number of singers and the number of friends correspondingly.

The $$$i$$$-th of the next $$$m$$$ lines contains the integer $$$q_i$$$ ($$$1\le q_i\le n$$$) — the number of favorite singers of the $$$i$$$-th friend – followed by the $$$q_i$$$ integers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$ ($$$1\le s_{i,1}<s_{i,2}<\cdots<s_{i,q_i}\le n$$$) — the indexes of his favorite singers.

## Output Format
Print the number of valid orderings of the singers modulo $$$998\,244\,353$$$.

## Examples
```input
3 1
2 1 3
```
```output
4
```
-----
```input
5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5
```
```output
0
```
-----
```input
100 1
1 50
```
```output
35305197
```
-----
```input
5 1
5 1 2 3 4 5
```
```output
120
```
-----
```input
2 5
1 2
1 2
1 2
1 1
1 1
```
```output
2
```
-----
```input
11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11
```
```output
384
```

## Note
Explanation of the first sample: There are $$$3$$$ singers and only $$$1$$$ friend. The friend likes the two singers $$$1$$$ and $$$3$$$. Thus, the $$$4$$$ valid orderings are:

- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2

Explanation of the second sample: There are $$$5$$$ singers and $$$5$$$ friends. One can show that no ordering is valid.

Explanation of the third sample: There are $$$100$$$ singers and only $$$1$$$ friend. The friend likes only singer $$$50$$$, hence all the $$$100!$$$ possible orderings are valid.

Explanation of the fourth sample: There are $$$5$$$ singers and only $$$1$$$ friend. The friend likes all the singers, hence all the $$$5!=120$$$ possible orderings are valid.

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
Moamen has an array of $$$n$$$ distinct integers. He wants to sort that array in non-decreasing order by doing the following operations in order exactly once:

1. Split the array into exactly $$$k$$$ non-empty subarrays such that each element belongs to exactly one subarray.
2. Reorder these subarrays arbitrary.
3. Merge the subarrays in their new order.

A sequence $$$a$$$ is a subarray of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Can you tell Moamen if there is a way to sort the array in non-decreasing order using the operations written above?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le |a_i| \le 10^9$$$). It is guaranteed that all numbers are distinct.

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

## Output Format
For each test case, you should output a single string.

If Moamen can sort the array in non-decreasing order, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

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

## Note
In the first test case, $$$a = [6, 3, 4, 2, 1]$$$, and $$$k = 4$$$, so we can do the operations as follows:

1. Split $$$a$$$ into $$$\{ [6], [3, 4], [2], [1] \}$$$.
2. Reorder them: $$$\{ [1], [2], [3,4], [6] \}$$$.
3. Merge them: $$$[1, 2, 3, 4, 6]$$$, so now the array is sorted.

In the second test case, there is no way to sort the array by splitting it into only $$$2$$$ subarrays.

As an example, if we split it into $$$\{ [1, -4], [0, -2] \}$$$, we can reorder them into $$$\{ [1, -4], [0, -2] \}$$$ or $$$\{ [0, -2], [1, -4] \}$$$. However, after merging the subarrays, it is impossible to get a sorted array.

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
Moamen and Ezzat are playing a game. They create an array $$$a$$$ of $$$n$$$ non-negative integers where every element is less than $$$2^k$$$.

Moamen wins if $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$.

Here $$$\&$$$ denotes the bitwise AND operation, and $$$\oplus$$$ denotes the bitwise XOR operation.

Please calculate the number of winning for Moamen arrays $$$a$$$.

As the result may be very large, print the value modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n\le 2\cdot 10^5$$$, $$$0 \le k \le 2\cdot 10^5$$$).

## Output Format
For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

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

## Note
In the first example, $$$n = 3$$$, $$$k = 1$$$. As a result, all the possible arrays are $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,1,1]$$$.

Moamen wins in only $$$5$$$ of them: $$$[0,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,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 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 positive integers $$$n$$$ and $$$s$$$. Find the maximum possible median of an array of $$$n$$$ non-negative integers (not necessarily distinct), such that the sum of its elements is equal to $$$s$$$.

A median of an array of integers of length $$$m$$$ is the number standing on the $$$\lceil {\frac{m}{2}} \rceil$$$-th (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting from $$$1$$$. For example, a median of the array $$$[20,40,20,50,50,30]$$$ is the $$$\lceil \frac{m}{2} \rceil$$$-th element of $$$[20,20,30,40,50,50]$$$, so it is $$$30$$$. There exist other definitions of the median, but in this problem we use the described definition.

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

Each test case contains a single line with two integers $$$n$$$ and $$$s$$$ ($$$1 \le n, s \le 10^9$$$) — the length of the array and the required sum of the elements.

## Output Format
For each test case print a single integer — the maximum possible median.

## Examples
```input
8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1
```
```output
5
2
2
0
4
4
1000000000
0
```

## Note
Possible arrays for the first three test cases (in each array the median is underlined):

- In the first test case $$$[\underline{5}]$$$
- In the second test case $$$[\underline{2}, 3]$$$
- In the third test case $$$[1, \underline{2}, 2]$$$

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
A binary string is a string that consists of characters $$$0$$$ and $$$1$$$.

Let $$$\operatorname{MEX}$$$ of a binary string be the smallest digit among $$$0$$$, $$$1$$$, or $$$2$$$ that does not occur in the string. For example, $$$\operatorname{MEX}$$$ of $$$001011$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ occur in the string at least once, $$$\operatorname{MEX}$$$ of $$$1111$$$ is $$$0$$$, because $$$0$$$ and $$$2$$$ do not occur in the string and $$$0 < 2$$$.

A binary string $$$s$$$ is given. You should cut it into any number of substrings such that each character is in exactly one substring. It is possible to cut the string into a single substring — the whole string.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

What is the minimal sum of $$$\operatorname{MEX}$$$ of all substrings pieces can be?

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

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

It's guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print a single integer — the minimal sum of $$$\operatorname{MEX}$$$ of all substrings that it is possible to get by cutting $$$s$$$ optimally.

## Examples
```input
6
01
1111
01100
101
0000
01010
```
```output
1
0
2
1
1
2
```

## Note
In the first test case the minimal sum is $$$\operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1$$$.

In the second test case the minimal sum is $$$\operatorname{MEX}(1111) = 0$$$.

In the third test case the minimal sum is $$$\operatorname{MEX}(01100) = 2$$$.

Now solve the problem and return the code.