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

# Problem
You are given a binary string $$$s$$$ of length $$$n$$$.

Let's define $$$d_i$$$ as the number whose decimal representation is $$$s_i s_{i+1}$$$ (possibly, with a leading zero). We define $$$f(s)$$$ to be the sum of all the valid $$$d_i$$$. In other words, $$$f(s) = \sum\limits_{i=1}^{n-1} d_i$$$.

For example, for the string $$$s = 1011$$$:

- $$$d_1 = 10$$$ (ten);
- $$$d_2 = 01$$$ (one)
- $$$d_3 = 11$$$ (eleven);
- $$$f(s) = 10 + 01 + 11 = 22$$$.

In one operation you can swap any two adjacent elements of the string. Find the minimum value of $$$f(s)$$$ that can be achieved if at most $$$k$$$ operations are allowed.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

First line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — the length of the string and the maximum number of operations allowed.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$, consisting of only zeros and ones.

It is also given that sum of $$$n$$$ over all the test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print the minimum value of $$$f(s)$$$ you can obtain with at most $$$k$$$ operations.

## Examples
```input
3
4 0
1010
7 1
0010100
5 2
00110
```
```output
21
22
12
```

## Note
- For the first example, you can't do any operation so the optimal string is $$$s$$$ itself. $$$f(s) = f(1010) = 10 + 01 + 10 = 21$$$.
- For the second example, one of the optimal strings you can obtain is "0011000". The string has an $$$f$$$ value of $$$22$$$.
- For the third example, one of the optimal strings you can obtain is "00011". The string has an $$$f$$$ value of $$$12$$$.

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

# Problem
You are given an array $$$a$$$ of $$$n$$$ integers. You are asked to find out if the inequality $$$$$$\max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$$$$$$ holds for all pairs of indices $$$(i, j)$$$, where $$$1 \leq i \leq j \leq n$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the size of the array.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

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, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower).

## Examples
```input
3
4
-1 1 -1 2
5
-1 2 -3 2 -1
3
2 3 -1
```
```output
YES
YES
NO
```

## Note
In test cases $$$1$$$ and $$$2$$$, the given condition is satisfied for all $$$(i, j)$$$ pairs.

In test case $$$3$$$, the condition isn't satisfied for the pair $$$(1, 2)$$$ as $$$\max(2, 3) < 2 + 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ colored segments on the number line. Each segment is either colored red or blue. The $$$i$$$-th segment can be represented by a tuple $$$(c_i, l_i, r_i)$$$. The segment contains all the points in the range $$$[l_i, r_i]$$$, inclusive, and its color denoted by $$$c_i$$$:

- if $$$c_i = 0$$$, it is a red segment;
- if $$$c_i = 1$$$, it is a blue segment.

We say that two segments of different colors are connected, if they share at least one common point. Two segments belong to the same group, if they are either connected directly, or through a sequence of directly connected segments. Find the number of groups of segments.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of segments.

Each of the next $$$n$$$ lines contains three integers $$$c_i, l_i, r_i$$$ ($$$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$$$), describing the $$$i$$$-th segment.

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

## Output Format
For each test case, print a single integer $$$k$$$, the number of groups of segments.

## Examples
```input
2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4
```
```output
2
3
```

## Note
In the first example there are $$$5$$$ segments. The segments $$$1$$$ and $$$2$$$ are connected, because they are of different colors and share a point. Also, the segments $$$2$$$ and $$$3$$$ are connected, and so are segments $$$4$$$ and $$$5$$$. Thus, there are two groups: one containing segments $$$\{1, 2, 3\}$$$, and the other one containing segments $$$\{4, 5\}$$$.

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 tree $$$G$$$ with $$$n$$$ vertices and an integer $$$k$$$. The vertices of the tree are numbered from $$$1$$$ to $$$n$$$.

For a vertex $$$r$$$ and a subset $$$S$$$ of vertices of $$$G$$$, such that $$$|S| = k$$$, we define $$$f(r, S)$$$ as the size of the smallest rooted subtree containing all vertices in $$$S$$$ when the tree is rooted at $$$r$$$. A set of vertices $$$T$$$ is called a rooted subtree, if all the vertices in $$$T$$$ are connected, and for each vertex in $$$T$$$, all its descendants belong to $$$T$$$.

You need to calculate the sum of $$$f(r, S)$$$ over all possible distinct combinations of vertices $$$r$$$ and subsets $$$S$$$, where $$$|S| = k$$$. Formally, compute the following: $$$$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),$$$$$$ where $$$V$$$ is the set of vertices in $$$G$$$.

Output the answer modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), denoting an edge between vertex $$$x$$$ and $$$y$$$.

It is guaranteed that the given edges form a tree.

## Output Format
Print the answer modulo $$$10^9 + 7$$$.

## Examples
```input
3 2
1 2
1 3
```
```output
25
```
-----
```input
7 2
1 2
2 3
2 4
1 5
4 6
4 7
```
```output
849
```

## Note
The tree in the second example is given below:

We have $$$21$$$ subsets of size $$$2$$$ in the given tree. Hence, $$$$$$S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}.$$$$$$ And since we have $$$7$$$ vertices, $$$1 \le r \le 7$$$. We need to find the sum of $$$f(r, S)$$$ over all possible pairs of $$$r$$$ and $$$S$$$.

Below we have listed the value of $$$f(r, S)$$$ for some combinations of $$$r$$$ and $$$S$$$.

- $$$r = 1$$$, $$$S = \{3, 7\}$$$. The value of $$$f(r, S)$$$ is $$$5$$$ and the corresponding subtree is $$$\{2, 3, 4, 6, 7\}$$$.
- $$$r = 1$$$, $$$S = \{5, 4\}$$$. The value of $$$f(r, S)$$$ is $$$7$$$ and the corresponding subtree is $$$\{1, 2, 3, 4, 5, 6, 7\}$$$.
- $$$r = 1$$$, $$$S = \{4, 6\}$$$. The value of $$$f(r, S)$$$ is $$$3$$$ and the corresponding subtree is $$$\{4, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Michael and Joe are playing a game. The game is played on a grid with $$$n$$$ rows and $$$m$$$ columns, filled with distinct integers. We denote the square on the $$$i$$$-th ($$$1\le i\le n$$$) row and $$$j$$$-th ($$$1\le j\le m$$$) column by $$$(i, j)$$$ and the number there by $$$a_{ij}$$$.

Michael starts by saying two numbers $$$h$$$ ($$$1\le h \le n$$$) and $$$w$$$ ($$$1\le w \le m$$$). Then Joe picks any $$$h\times w$$$ subrectangle of the board (without Michael seeing).

Formally, an $$$h\times w$$$ subrectangle starts at some square $$$(a,b)$$$ where $$$1 \le a \le n-h+1$$$ and $$$1 \le b \le m-w+1$$$. It contains all squares $$$(i,j)$$$ for $$$a \le i \le a+h-1$$$ and $$$b \le j \le b+w-1$$$.

Possible move by Joe if Michael says $$$3\times 2$$$ (with maximum of $$$15$$$).

Finally, Michael has to guess the maximum number in the subrectangle. He wins if he gets it right.

Because Michael doesn't like big numbers, he wants the area of the chosen subrectangle (that is, $$$h \cdot w$$$), to be as small as possible, while still ensuring that he wins, not depending on Joe's choice. Help Michael out by finding this minimum possible area.

It can be shown that Michael can always choose $$$h, w$$$ for which he can ensure that he wins.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 40$$$)  — the size of the grid.

Each of the following $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{ij}$$$ ($$$-10^9 \le a_{ij} \le 10^9$$$)  — the element in the cell $$$(i, j)$$$.

It is guaranteed that all the numbers are distinct (that is, if $$$a_{i_1j_1} = a_{i_2j_2}$$$, then $$$i_1 = i_2, j_1 = j_2$$$).

## Output Format
For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

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

## Note
In the first test case, the grid is $$$1\times 1$$$, so the only possible choice for $$$h, w$$$ is $$$h = 1, w = 1$$$, giving an area of $$$h\cdot w = 1$$$.

The grid from the second test case is drawn in the statement. It can be shown that with $$$h = 3, w = 3$$$ Michael can guarantee the victory and that any choice with $$$h\cdot w \le 8$$$ doesn't.

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
During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome.

Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers $$$121, 66, 98989$$$ are palindromes, and $$$103, 239, 1241$$$ are not palindromes.

Alina understands that a valid number always exist. Help her find one!

## Input Format
The first line of input data contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Next, descriptions of $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the number that is written on the ground.

The second line of contains the positive $$$n$$$-digit integer without leading zeroes — the number itself.

It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

## Output Format
For each of $$$t$$$ test cases print an answer — a positive $$$n$$$-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome.

We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.

## Examples
```input
3
2
99
4
1023
3
385
```
```output
32
8646
604
```

## Note
In the first test case $$$99 + 32 = 131$$$ is a palindrome. Note that another answer is $$$12$$$, because $$$99 + 12 = 111$$$ is also a palindrome.

In the second test case $$$1023 + 8646 = 9669$$$.

In the third test case $$$385 + 604 = 989$$$.

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
Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees.

There are $$$n$$$ trees growing near the path, the current levels of moisture of each tree are denoted by the array $$$a_1, a_2, \dots, a_n$$$. Leon has learned three abilities which will help him to dry and water the soil.

- Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$1, 2, \dots, i$$$ by $$$1$$$.
- Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$i, i + 1, \dots, n$$$ by $$$1$$$.
- Increase the level of moisture of all trees by $$$1$$$.

Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to $$$0$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the initial levels of trees moisture.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$200\,000$$$.

## Output Format
For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.

## Examples
```input
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5
```
```output
2
13
36
33
```

## Note
In the first test case it's enough to apply the operation of adding $$$1$$$ to the whole array $$$2$$$ times.

In the second test case you can apply the operation of decreasing $$$4$$$ times on the prefix of length $$$3$$$ and get an array $$$6, 0, 3$$$.

After that apply the operation of decreasing $$$6$$$ times on the prefix of length $$$1$$$ and $$$3$$$ times on the suffix of length $$$1$$$. In total, the number of actions will be $$$4 + 6 + 3 = 13$$$. It can be shown that it's impossible to perform less actions to get the required array, so the answer is $$$13$$$.

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
Little pirate Serega robbed a ship with puzzles of different kinds. Among all kinds, he liked only one, the hardest.

A puzzle is a table of $$$n$$$ rows and $$$m$$$ columns, whose cells contain each number from $$$1$$$ to $$$n \cdot m$$$ exactly once.

To solve a puzzle, you have to find a sequence of cells in the table, such that any two consecutive cells are adjacent by the side in the table. The sequence can have arbitrary length and should visit each cell one or more times. For a cell containing the number $$$i$$$, denote the position of the first occurrence of this cell in the sequence as $$$t_i$$$. The sequence solves the puzzle, if $$$t_1 < t_2 < \dots < t_{nm}$$$. In other words, the cell with number $$$x$$$ should be first visited before the cell with number $$$x + 1$$$ for each $$$x$$$.

Let's call a puzzle solvable, if there exists at least one suitable sequence.

In one move Serega can choose two arbitrary cells in the table (not necessarily adjacent by the side) and swap their numbers. He would like to know the minimum number of moves to make his puzzle solvable, but he is too impatient. Thus, please tell if the minimum number of moves is $$$0$$$, $$$1$$$, or at least $$$2$$$. In the case, where $$$1$$$ move is required, please also find the number of suitable cell pairs to swap.

## Input Format
In the first line there are two whole positive numbers $$$n, m$$$ ($$$1 \leq n\cdot m \leq 400\,000$$$) — table dimensions.

In the next $$$n$$$ lines there are $$$m$$$ integer numbers $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le nm$$$).

It is guaranteed that every number from $$$1$$$ to $$$nm$$$ occurs exactly once in the table.

## Output Format
Let $$$a$$$ be the minimum number of moves to make the puzzle solvable.

If $$$a = 0$$$, print $$$0$$$.

If $$$a = 1$$$, print $$$1$$$ and the number of valid swaps.

If $$$a \ge 2$$$, print $$$2$$$.

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

## Note
In the first example the sequence $$$(1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)$$$, $$$(2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)$$$ solves the puzzle, so the answer is $$$0$$$.

The puzzle in the second example can't be solved, but it's solvable after any of three swaps of cells with values $$$(1, 5), (1, 6), (2, 6)$$$.

The puzzle from the third example requires at least two swaps, so the answer is $$$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 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
Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with $$$2$$$ rows and $$$n$$$ columns, every element of which is either $$$0$$$ or $$$1$$$. In one move you can swap two values in neighboring cells.

More formally, let's number rows $$$1$$$ to $$$2$$$ from top to bottom, and columns $$$1$$$ to $$$n$$$ from left to right. Also, let's denote a cell in row $$$x$$$ and column $$$y$$$ as $$$(x, y)$$$. We consider cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ neighboring if $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.

Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains $$$n$$$ integers, every one of which is either $$$0$$$ or $$$1$$$.

The last two lines describe Alice's desired arrangement in the same format.

## Output Format
If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print $$$-1$$$.

## Examples
```input
5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0
```
```output
5
```
-----
```input
3
1 0 0
0 0 0
0 0 0
0 0 0
```
```output
-1
```

## Note
In the first example the following sequence of swaps will suffice:

- $$$(2, 1), (1, 1)$$$,
- $$$(1, 2), (1, 3)$$$,
- $$$(2, 2), (2, 3)$$$,
- $$$(1, 4), (1, 5)$$$,
- $$$(2, 5), (2, 4)$$$.

It can be shown that $$$5$$$ is the minimal possible answer in this case.

In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is $$$-1$$$.

Now solve the problem and return the code.