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.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 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
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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a 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 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
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 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
Mike and Joe are playing a game with some stones. Specifically, they have $$$n$$$ piles of stones of sizes $$$a_1, a_2, \ldots, a_n$$$. These piles are arranged in a circle.

The game goes as follows. Players take turns removing some positive number of stones from a pile in clockwise order starting from pile $$$1$$$. Formally, if a player removed stones from pile $$$i$$$ on a turn, the other player removes stones from pile $$$((i\bmod n) + 1)$$$ on the next turn.

If a player cannot remove any stones on their turn (because the pile is empty), they lose. Mike goes first.

If Mike and Joe play optimally, who will win?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$)  — the number of piles.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — the size of the piles.

## Output Format
For each test case print the winner of the game, either "Mike" or "Joe" on its own line (without quotes).

## Examples
```input
2
1
37
2
100 100
```
```output
Mike
Joe
```

## Note
In the first test case, Mike just takes all $$$37$$$ stones on his first turn.

In the second test case, Joe can just copy Mike's moves every time. Since Mike went first, he will hit $$$0$$$ on the first pile one move before Joe does so on the second pile.

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
You are given a grid with $$$n$$$ rows and $$$m$$$ columns. 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}$$$. All numbers are equal to $$$1$$$ or to $$$-1$$$.

You start from the square $$$(1, 1)$$$ and can move one square down or one square to the right at a time. In the end, you want to end up at the square $$$(n, m)$$$.

Is it possible to move in such a way so that the sum of the values written in all the visited cells (including $$$a_{11}$$$ and $$$a_{nm}$$$) is $$$0$$$?

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$)  — 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}$$$ ($$$a_{ij} = 1$$$ or $$$-1$$$)  — the element in the cell $$$(i, j)$$$.

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

## Output Format
For each test case, print "YES" if there exists a path from the top left to the bottom right that adds up to $$$0$$$, and "NO" otherwise. You can output each letter in any case.

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

## Note
One possible path for the fourth test case is given in the picture in the statement.

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