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
Alice and Bob are playing a game. They have an array of positive integers $$$a$$$ of size $$$n$$$.

Before starting the game, Alice chooses an integer $$$k \ge 0$$$. The game lasts for $$$k$$$ stages, the stages are numbered from $$$1$$$ to $$$k$$$. During the $$$i$$$-th stage, Alice must remove an element from the array that is less than or equal to $$$k - i + 1$$$. After that, if the array is not empty, Bob must add $$$k - i + 1$$$ to an arbitrary element of the array. Note that both Alice's move and Bob's move are two parts of the same stage of the game. If Alice can't delete an element during some stage, she loses. If the $$$k$$$-th stage ends and Alice hasn't lost yet, she wins.

Your task is to determine the maximum value of $$$k$$$ such that Alice can win if both players play optimally. Bob plays against Alice, so he tries to make her lose the game, if it's possible.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

## Output Format
For each test case, print one integer — the maximum value of $$$k$$$ such that Alice can win if both players play optimally.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Monocarp is playing Minecraft and wants to build a wall of cacti. He wants to build it on a field of sand of the size of $$$n \times m$$$ cells. Initially, there are cacti in some cells of the field. Note that, in Minecraft, cacti cannot grow on cells adjacent to each other by side — and the initial field meets this restriction. Monocarp can plant new cacti (they must also fulfil the aforementioned condition). He can't chop down any of the cacti that are already growing on the field — he doesn't have an axe, and the cacti are too prickly for his hands.

Monocarp believes that the wall is complete if there is no path from the top row of the field to the bottom row, such that:

- each two consecutive cells in the path are adjacent by side;
- no cell belonging to the path contains a cactus.

Your task is to plant the minimum number of cacti to build a wall (or to report that this is impossible).

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$n \times m \le 4 \cdot 10^5$$$) — the number of rows and columns, respectively.

Then $$$n$$$ rows follow, $$$i$$$-th row contains a string $$$s_i$$$ of length $$$m$$$, where $$$s_{i, j}$$$ is '#', if a cactus grows at the intersection of the $$$i$$$-th row and the $$$j$$$-th column. Otherwise, $$$s_{i, j}$$$ is '.'.

The sum of $$$n \times m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

## Output Format
For each test case, print NO in the first line if it is impossible to build a cactus wall without breaking the rules. Otherwise, print YES in the first line, then print $$$n$$$ lines of $$$m$$$ characters each — the field itself, where the $$$j$$$-th character of the $$$i$$$-th line is equal to '#', if there is a cactus on the intersection of the $$$i$$$-th row and the $$$j$$$-th column, otherwise it is '.'. If there are multiple optimal answers, print any of them.

## Examples
```input
4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...
```
```output
YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...
```

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree consisting of $$$n$$$ vertices. Initially, each vertex has a value $$$0$$$.

You need to perform $$$m$$$ queries of two types:

1. You are given a vertex index $$$v$$$. Print the value of the vertex $$$v$$$.
2. You are given two vertex indices $$$u$$$ and $$$v$$$ and values $$$k$$$ and $$$d$$$ ($$$d \le 20$$$). You need to add $$$k$$$ to the value of each vertex such that the distance from that vertex to the path from $$$u$$$ to $$$v$$$ is less than or equal to $$$d$$$.

The distance between two vertices $$$x$$$ and $$$y$$$ is equal to the number of edges on the path from $$$x$$$ to $$$y$$$. For example, the distance from $$$x$$$ to $$$x$$$ itself is equal to $$$0$$$.

The distance from the vertex $$$v$$$ to some path from $$$x$$$ to $$$y$$$ is equal to the minimum among distances from $$$v$$$ to any vertex on the path from $$$x$$$ to $$$y$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n - 1$$$ lines contain the edges of the tree — one per line. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$) representing one edge of the tree. It's guaranteed that the given edges form a tree.

The next line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of queries.

Next $$$m$$$ lines contain the queries — one per line. Each query has one of the following two types:

- $$$1$$$ $$$v$$$ ($$$1 \le v \le n$$$) — the query of the first type;
- $$$2$$$ $$$u$$$ $$$v$$$ $$$k$$$ $$$d$$$ ($$$1 \le u, v \le n$$$; $$$1 \le k \le 1000$$$; $$$0 \le d \le 20$$$) — the query of the second type.

Additional constraint on the input: there is at least one query of the first type.

## Output Format
For each query of the first type, print the value of the corresponding vertex.

## Examples
```input
6
1 2
1 3
4 2
5 2
3 6
14
2 4 5 10 2
1 3
1 6
2 1 1 10 20
2 6 6 10 20
1 3
2 3 2 10 0
2 5 2 10 1
1 1
1 2
1 3
1 4
1 5
1 6
```
```output
10
0
30
50
50
40
40
40
20
```

## Note
The tree from the first example:

- "$$$2$$$ $$$4$$$ $$$5$$$ $$$10$$$ $$$2$$$": affected vertices are $$$\{4, 2, 5, 1, 3\}$$$;
- "$$$2$$$ $$$1$$$ $$$1$$$ $$$10$$$ $$$20$$$" and "$$$2$$$ $$$6$$$ $$$6$$$ $$$10$$$ $$$20$$$": all vertices are affected, since distance to $$$1$$$ ($$$6$$$) is less that $$$20$$$ for any vertex;
- "$$$2$$$ $$$3$$$ $$$2$$$ $$$10$$$ $$$0$$$": affected vertices are $$$\{3, 1, 2\}$$$;
- "$$$2$$$ $$$5$$$ $$$2$$$ $$$10$$$ $$$1$$$": affected vertices are $$$\{5, 2, 4, 1\}$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya plays Robot Bicorn Attack.

The game consists of three rounds. For each one a non-negative integer amount of points is given. The result of the game is the sum of obtained points. Vasya has already played three rounds and wrote obtained points one by one (without leading zeros) into the string s. Vasya decided to brag about his achievement to the friends. However, he has forgotten how many points he got for each round. The only thing he remembers is the string s.

Help Vasya to find out what is the maximum amount of points he could get. Take into account that Vasya played Robot Bicorn Attack for the first time, so he could not get more than 1000000 (106) points for one round.

## Input Format
The only line of input contains non-empty string s obtained by Vasya. The string consists of digits only. The string length does not exceed 30 characters.

## Output Format
Print the only number — the maximum amount of points Vasya could get. If Vasya is wrong and the string could not be obtained according to the rules then output number -1.

## Examples
```input
1234
```
```output
37
```
-----
```input
9000
```
```output
90
```
-----
```input
0009
```
```output
-1
```

## Note
In the first example the string must be split into numbers 1, 2 and 34.

In the second example the string must be split into numbers 90, 0 and 0.

In the third example the string is incorrect, because after splitting the string into 3 numbers number 00 or 09 will be obtained, but numbers cannot have leading zeroes.

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
Vasya plays the Geometry Horse.

The game goal is to destroy geometric figures of the game world. A certain number of points is given for destroying each figure depending on the figure type and the current factor value.

There are n types of geometric figures. The number of figures of type ki and figure cost ci is known for each figure type. A player gets ci·f  points for destroying one figure of type i, where f is the current factor. The factor value can be an integer number from 1 to t + 1, inclusive. At the beginning of the game the factor value is equal to 1. The factor is set to i + 1 after destruction of pi (1 ≤ i ≤ t) figures, so the (pi + 1)-th figure to be destroyed is considered with factor equal to i + 1.

Your task is to determine the maximum number of points Vasya can get after he destroys all figures. Take into account that Vasya is so tough that he can destroy figures in any order chosen by him.

## Input Format
The first line contains the only integer number n (1 ≤ n ≤ 100) — the number of figure types.

Each of the following n lines contains two integer numbers ki and ci (1 ≤ ki ≤ 109, 0 ≤ ci ≤ 1000), separated with space — the number of figures of the i-th type and the cost of one i-type figure, correspondingly.

The next line contains the only integer number t (1 ≤ t ≤ 100) — the number that describe the factor's changes.

The next line contains t integer numbers pi (1 ≤ p1 < p2 < ... < pt ≤ 1012), separated with spaces.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

## Output Format
Print the only number — the maximum number of points Vasya can get.

## Examples
```input
1
5 10
2
3 6
```
```output
70
```
-----
```input
2
3 8
5 10
1
20
```
```output
74
```

## Note
In the first example Vasya destroys three figures first and gets 3·1·10 = 30 points. Then the factor will become equal to 2 and after destroying the last two figures Vasya will get 2·2·10 = 40 points. As a result Vasya will get 70 points.

In the second example all 8 figures will be destroyed with factor 1, so Vasya will get (3·8 + 5·10)·1 = 74 points.

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
Given three distinct integers $$$a$$$, $$$b$$$, and $$$c$$$, find the medium number between all of them.

The medium number is the number that is neither the minimum nor the maximum of the given three numbers.

For example, the median of $$$5,2,6$$$ is $$$5$$$, since the minimum is $$$2$$$ and the maximum is $$$6$$$.

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

The description of each test case consists of three distinct integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq a, b, c \leq 20$$$).

## Output Format
For each test case, output a single integer — the medium number of the three numbers.

## Examples
```input
9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4
```
```output
5
4
2
2
12
10
6
3
8
```

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
In order to write a string, Atilla needs to first learn all letters that are contained in the string.

Atilla needs to write a message which can be represented as a string $$$s$$$. He asks you what is the minimum alphabet size required so that one can write this message.

The alphabet of size $$$x$$$ ($$$1 \leq x \leq 26$$$) contains only the first $$$x$$$ Latin letters. For example an alphabet of size $$$4$$$ contains only the characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$ and $$$\texttt{d}$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

## Output Format
For each test case, output a single integer — the minimum alphabet size required to so that Atilla can write his message $$$s$$$.

## Examples
```input
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
```
```output
1
23
19
6
26
```

## Note
For the first test case, Atilla needs to know only the character $$$\texttt{a}$$$, so the alphabet of size $$$1$$$ which only contains $$$\texttt{a}$$$ is enough.

For the second test case, Atilla needs to know the characters $$$\texttt{d}$$$, $$$\texttt{o}$$$, $$$\texttt{w}$$$, $$$\texttt{n}$$$. The smallest alphabet size that contains all of them is $$$23$$$ (such alphabet can be represented as the string $$$\texttt{abcdefghijklmnopqrstuvw}$$$).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ participants in a competition, participant $$$i$$$ having a strength of $$$s_i$$$.

Every participant wonders how much of an advantage they have over the other best participant. In other words, each participant $$$i$$$ wants to know the difference between $$$s_i$$$ and $$$s_j$$$, where $$$j$$$ is the strongest participant in the competition, not counting $$$i$$$ (a difference can be negative).

So, they ask you for your help! For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any participant other than participant $$$i$$$.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The following line contains $$$n$$$ space-separated positive integers $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$ ($$$1 \leq s_i \leq 10^9$$$) — the strengths of the participants.

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

## Output Format
For each test case, output $$$n$$$ space-separated integers. For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any other participant.

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

## Note
For the first test case:

- The first participant has a strength of $$$4$$$ and the largest strength of a participant different from the first one is $$$7$$$, so the answer for the first participant is $$$4 - 7 = -3$$$.
- The second participant has a strength of $$$7$$$ and the largest strength of a participant different from the second one is $$$5$$$, so the answer for the second participant is $$$7 - 5 = 2$$$.
- The third participant has a strength of $$$3$$$ and the largest strength of a participant different from the third one is $$$7$$$, so the answer for the third participant is $$$3 - 7 = -4$$$.
- The fourth participant has a strength of $$$5$$$ and the largest strength of a participant different from the fourth one is $$$7$$$, so the answer for the fourth participant is $$$5 - 7 = -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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a[0 \dots n-1]$$$ of $$$n$$$ integers. This array is called a "valley" if there exists exactly one subarray $$$a[l \dots r]$$$ such that:

- $$$0 \le l \le r \le n-1$$$,
- $$$a_l = a_{l+1} = a_{l+2} = \dots = a_r$$$,
- $$$l = 0$$$ or $$$a_{l-1} > a_{l}$$$,
- $$$r = n-1$$$ or $$$a_r < a_{r+1}$$$.

Here are three examples:

The first image shows the array [$$$3, 2, 2, 1, 2, 2, 3$$$], it is a valley because only subarray with indices $$$l=r=3$$$ satisfies the condition.

The second image shows the array [$$$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$$$], it is a valley because only subarray with indices $$$l=0, r=2$$$ satisfies the codition.

The third image shows the array [$$$1, 2, 3, 4, 3, 2, 1$$$], it is not a valley because two subarrays $$$l=r=0$$$ and $$$l=r=6$$$ that satisfy the condition.

You are asked whether the given array is a valley or not.

Note that we consider the array to be indexed from $$$0$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases is smaller than $$$2\cdot10^5$$$.

## Output Format
For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
```
```output
YES
YES
NO
YES
YES
NO
```

## Note
The first three test cases are explained in the statement.

Now solve the problem and return the code.