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
Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across $$$n$$$ sessions follow the identity permutation (ie. in the first game he scores $$$1$$$ point, in the second game he scores $$$2$$$ points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on $$$[1,2,3]$$$ can yield $$$[3,1,2]$$$ but it cannot yield $$$[3,2,1]$$$ since the $$$2$$$ is in the same position.

Given a permutation of $$$n$$$ integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed $$$10^{18}$$$.

An array $$$a$$$ is a subarray of an array $$$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.

## 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 integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the length of the given permutation.

The second line of each test case contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}$$$ ($$$1 \leq a_{i} \leq n$$$)  — the initial permutation.

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

## Output Format
For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.

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

## Note
In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least $$$2$$$ exchanges to sort the second permutation.

$$$[3, 2, 4, 5, 1, 6, 7]$$$

Perform special exchange on range ($$$1, 5$$$)

$$$[4, 1, 2, 3, 5, 6, 7]$$$

Perform special exchange on range ($$$1, 4$$$)

$$$[1, 2, 3, 4, 5, 6, 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 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
Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem!

You are given $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$ arranged in a circle, where $$$n$$$ must be odd (ie. $$$n-1$$$ is divisible by $$$2$$$). Formally, for all $$$i$$$ such that $$$2 \leq i \leq n$$$, the elements $$$a_{i - 1}$$$ and $$$a_i$$$ are considered to be adjacent, and $$$a_n$$$ and $$$a_1$$$ are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value.

Help Danny find the maximum possible circular value after some sequences of operations.

## Input Format
The first line contains one odd integer $$$n$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$n$$$ is odd)  — the initial size of the circle.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$0 \leq a_{i} \leq 10^9$$$)  — the initial numbers in the circle.

## Output Format
Output the maximum possible circular value after applying some sequence of operations to the given circle.

## Examples
```input
3
7 10 2
```
```output
17
```
-----
```input
1
4
```
```output
4
```

## Note
For the first test case, here's how a circular value of $$$17$$$ is obtained:

Pick the number at index $$$3$$$. The sum of adjacent elements equals $$$17$$$. Delete $$$7$$$ and $$$10$$$ from the circle and replace $$$2$$$ with $$$17$$$.

Note that the answer may not fit in a $$$32$$$-bit integer.

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
Omkar is building a house. He wants to decide how to make the floor plan for the last floor.

Omkar's floor starts out as $$$n$$$ rows of $$$m$$$ zeros ($$$1 \le n,m \le 100$$$). Every row is divided into intervals such that every $$$0$$$ in the row is in exactly $$$1$$$ interval. For every interval for every row, Omkar can change exactly one of the $$$0$$$s contained in that interval to a $$$1$$$. Omkar defines the quality of a floor as the sum of the squares of the sums of the values in each column, i. e. if the sum of the values in the $$$i$$$-th column is $$$q_i$$$, then the quality of the floor is $$$\sum_{i = 1}^m q_i^2$$$.

Help Omkar find the maximum quality that the floor can have.

## Input Format
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 100$$$), which are the number of rows and number of columns, respectively.

You will then receive a description of the intervals in each row. For every row $$$i$$$ from $$$1$$$ to $$$n$$$: The first row contains a single integer $$$k_i$$$ ($$$1 \le k_i \le m$$$), which is the number of intervals on row $$$i$$$. The $$$j$$$-th of the next $$$k_i$$$ lines contains two integers $$$l_{i,j}$$$ and $$$r_{i,j}$$$, which are the left and right bound (both inclusive), respectively, of the $$$j$$$-th interval of the $$$i$$$-th row. It is guaranteed that all intervals other than the first interval will be directly after the interval before it. Formally, $$$l_{i,1} = 1$$$, $$$l_{i,j} \leq r_{i,j}$$$ for all $$$1 \le j \le k_i$$$, $$$r_{i,j-1} + 1 = l_{i,j}$$$ for all $$$2 \le j \le k_i$$$, and $$$r_{i,k_i} = m$$$.

## Output Format
Output one integer, which is the maximum possible quality of an eligible floor plan.

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

## Note
The given test case corresponds to the following diagram. Cells in the same row and have the same number are a part of the same interval.

The most optimal assignment is:

The sum of the $$$1$$$st column is $$$4$$$, the sum of the $$$2$$$nd column is $$$2$$$, the sum of the $$$3$$$rd and $$$4$$$th columns are $$$0$$$, and the sum of the $$$5$$$th column is $$$4$$$.

The quality of this floor plan is $$$4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$$$. You can show that there is no floor plan with a higher quality.

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

# Problem
Koa the Koala has a binary string $$$s$$$ of length $$$n$$$. Koa can perform no more than $$$n-1$$$ (possibly zero) operations of the following form:

In one operation Koa selects positions $$$i$$$ and $$$i+1$$$ for some $$$i$$$ with $$$1 \le i < |s|$$$ and sets $$$s_i$$$ to $$$max(s_i, s_{i+1})$$$. Then Koa deletes position $$$i+1$$$ from $$$s$$$ (after the removal, the remaining parts are concatenated).

Note that after every operation the length of $$$s$$$ decreases by $$$1$$$.

How many different binary strings can Koa obtain by doing no more than $$$n-1$$$ (possibly zero) operations modulo $$$10^9+7$$$ ($$$1000000007$$$)?

## Input Format
The only line of input contains binary string $$$s$$$ ($$$1 \le |s| \le 10^6$$$). For all $$$i$$$ ($$$1 \le i \le |s|$$$) $$$s_i = 0$$$ or $$$s_i = 1$$$.

## Output Format
On a single line print the answer to the problem modulo $$$10^9+7$$$ ($$$1000000007$$$).

## Examples
```input
000
```
```output
3
```
-----
```input
0101
```
```output
6
```
-----
```input
0001111
```
```output
16
```
-----
```input
00101100011100
```
```output
477
```

## Note
In the first sample Koa can obtain binary strings: $$$0$$$, $$$00$$$ and $$$000$$$.

In the second sample Koa can obtain binary strings: $$$1$$$, $$$01$$$, $$$11$$$, $$$011$$$, $$$101$$$ and $$$0101$$$. For example:

- to obtain $$$01$$$ from $$$0101$$$ Koa can operate as follows: $$$0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$$$.
- to obtain $$$11$$$ from $$$0101$$$ Koa can operate as follows: $$$0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$$$.

Parentheses denote the two positions Koa selected in each 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 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
BThero is a powerful magician. He has got $$$n$$$ piles of candies, the $$$i$$$-th pile initially contains $$$a_i$$$ candies. BThero can cast a copy-paste spell as follows:

1. He chooses two piles $$$(i, j)$$$ such that $$$1 \le i, j \le n$$$ and $$$i \ne j$$$.
2. All candies from pile $$$i$$$ are copied into pile $$$j$$$. Formally, the operation $$$a_j := a_j + a_i$$$ is performed.

BThero can cast this spell any number of times he wants to — but unfortunately, if some pile contains strictly more than $$$k$$$ candies, he loses his magic power. What is the maximum number of times BThero can cast the spell without losing his power?

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

Each test case consists of two lines:

- the first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$2 \le k \le 10^4$$$);
- the second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le k$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the sum of $$$k$$$ over all test cases does not exceed $$$10^4$$$.

## Output Format
For each test case, print one integer — the maximum number of times BThero can cast the spell without losing his magic power.

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

## Note
In the first test case we get either $$$a = [1, 2]$$$ or $$$a = [2, 1]$$$ after casting the spell for the first time, and it is impossible to cast it again.

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

# Problem
RedDreamer has an array $$$a$$$ consisting of $$$n$$$ non-negative integers, and an unlucky integer $$$T$$$.

Let's denote the misfortune of array $$$b$$$ having length $$$m$$$ as $$$f(b)$$$ — the number of pairs of integers $$$(i, j)$$$ such that $$$1 \le i < j \le m$$$ and $$$b_i + b_j = T$$$. RedDreamer has to paint each element of $$$a$$$ into one of two colors, white and black (for each element, the color is chosen independently), and then create two arrays $$$c$$$ and $$$d$$$ so that all white elements belong to $$$c$$$, and all black elements belong to $$$d$$$ (it is possible that one of these two arrays becomes empty). RedDreamer wants to paint the elements in such a way that $$$f(c) + f(d)$$$ is minimum possible.

For example:

- if $$$n = 6$$$, $$$T = 7$$$ and $$$a = [1, 2, 3, 4, 5, 6]$$$, it is possible to paint the $$$1$$$-st, the $$$4$$$-th and the $$$5$$$-th elements white, and all other elements black. So $$$c = [1, 4, 5]$$$, $$$d = [2, 3, 6]$$$, and $$$f(c) + f(d) = 0 + 0 = 0$$$;
- if $$$n = 3$$$, $$$T = 6$$$ and $$$a = [3, 3, 3]$$$, it is possible to paint the $$$1$$$-st element white, and all other elements black. So $$$c = [3]$$$, $$$d = [3, 3]$$$, and $$$f(c) + f(d) = 0 + 1 = 1$$$.

Help RedDreamer to paint the array optimally!

## Input Format
The first line contains one 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 two integers $$$n$$$ and $$$T$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le T \le 10^9$$$) — the number of elements in the array and the unlucky integer, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print $$$n$$$ integers: $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ (each $$$p_i$$$ is either $$$0$$$ or $$$1$$$) denoting the colors. If $$$p_i$$$ is $$$0$$$, then $$$a_i$$$ is white and belongs to the array $$$c$$$, otherwise it is black and belongs to the array $$$d$$$.

If there are multiple answers that minimize the value of $$$f(c) + f(d)$$$, print any of them.

## Examples
```input
2
6 7
1 2 3 4 5 6
3 6
3 3 3
```
```output
1 0 0 1 1 0 
1 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 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: 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.
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
Kolya got an integer array $$$a_1, a_2, \dots, a_n$$$. The array can contain both positive and negative integers, but Kolya doesn't like $$$0$$$, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be $$$0$$$. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $$$0$$$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $$$0$$$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $$$0$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of elements in Kolya's array.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}, a_i \neq 0$$$) — the description of Kolya's array.

## Output Format
Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $$$0$$$.

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

## Note
Consider the first example. There is only one subsegment with the sum $$$0$$$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $$$1$$$ between second and third elements of the array.

There are no subsegments having sum $$$0$$$ in the second example so you don't need to do anything.

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

# Problem
You are given a string $$$s$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $$$s$$$ be $$$k$$$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $$$3^{k}$$$ possible strings consisting only of letters "a", "b" and "c". For example, if $$$s = $$$"ac?b?c" then we can obtain the following strings: $$$[$$$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$$$]$$$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $$$10^{9} + 7$$$.

A subsequence of the string $$$t$$$ is such a sequence that can be derived from the string $$$t$$$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $$$(2, 5, 6)$$$ and a subsequence consisting of letters at positions $$$(3, 5, 6)$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ $$$(3 \le n \le 200\,000)$$$ — the length of $$$s$$$.

The second line of the input contains the string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".

## Output Format
Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $$$10^{9} + 7$$$.

## Examples
```input
6
ac?b?c
```
```output
24
```
-----
```input
7
???????
```
```output
2835
```
-----
```input
9
cccbbbaaa
```
```output
0
```
-----
```input
5
a???c
```
```output
46
```

## Note
In the first example, we can obtain $$$9$$$ strings:

- "acabac" — there are $$$2$$$ subsequences "abc",
- "acabbc" — there are $$$4$$$ subsequences "abc",
- "acabcc" — there are $$$4$$$ subsequences "abc",
- "acbbac" — there are $$$2$$$ subsequences "abc",
- "acbbbc" — there are $$$3$$$ subsequences "abc",
- "acbbcc" — there are $$$4$$$ subsequences "abc",
- "accbac" — there is $$$1$$$ subsequence "abc",
- "accbbc" — there are $$$2$$$ subsequences "abc",
- "accbcc" — there are $$$2$$$ subsequences "abc".

So, there are $$$2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$$$ subsequences "abc" in total.

Now solve the problem and return the code.