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
Polycarp has a problem — his laptop keyboard is broken.

Now, when he presses the 'b' key, it acts like an unusual backspace: it deletes the last (rightmost) lowercase letter in the typed string. If there are no lowercase letters in the typed string, then the press is completely ignored.

Similarly, when he presses the 'B' key, it deletes the last (rightmost) uppercase letter in the typed string. If there are no uppercase letters in the typed string, then the press is completely ignored.

In both cases, the letters 'b' and 'B' are not added to the typed string when these keys are pressed.

Consider an example where the sequence of key presses was "ARaBbbitBaby". In this case, the typed string will change as follows: "" $$$\xrightarrow{\texttt{A}}$$$ "A" $$$\xrightarrow{\texttt{R}}$$$ "AR" $$$\xrightarrow{\texttt{a}}$$$ "ARa" $$$\xrightarrow{\texttt{B}}$$$ "Aa" $$$\xrightarrow{\texttt{b}}$$$ "A" $$$\xrightarrow{\texttt{b}}$$$ "A" $$$\xrightarrow{\texttt{i}}$$$ "Ai" $$$\xrightarrow{\texttt{t}}$$$ "Ait" $$$\xrightarrow{\texttt{B}}$$$ "it" $$$\xrightarrow{\texttt{a}}$$$ "ita" $$$\xrightarrow{\texttt{b}}$$$ "it" $$$\xrightarrow{\texttt{y}}$$$ "ity".

Given a sequence of pressed keys, output the typed string after processing all key presses.

## Input Format
The first line of the input data contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the test.

The following contains $$$t$$$ non-empty lines, which consist of lowercase and uppercase letters of the Latin alphabet.

It is guaranteed that each line contains at least one letter and the sum of the lengths of the lines does not exceed $$$10^6$$$.

## Output Format
For each test case, output the result of processing the key presses on a separate line. If the typed string is empty, then output an empty line.

## Examples
```input
12
ARaBbbitBaby
YetAnotherBrokenKeyboard
Bubble
Improbable
abbreviable
BbBB
BusyasaBeeinaBedofBloomingBlossoms
CoDEBARbIES
codeforces
bobebobbes
b
TheBBlackbboard
```
```output
ity
YetnotherrokenKeoard
le
Imprle
revile

usyasaeeinaedofloominglossoms
CDARIES
codeforces
es

helaoard
```

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
Vlad found a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters, and he wants to make it as short as possible.

To do this, he can remove any pair of adjacent characters from $$$s$$$ any number of times, provided they are different. For example, if $$$s$$$=racoon, then by removing one pair of characters he can obtain the strings coon, roon, raon, and raco, but he cannot obtain racn (because the removed letters were the same) or rcon (because the removed letters were not adjacent).

What is the minimum length Vlad can achieve by applying any number of deletions?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

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

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 a single number—the minimum length of the string $$$s$$$, after removing pairs of adjacent characters with different values.

## Examples
```input
10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc
```
```output
0
1
2
1
1
0
1
0
0
1
```

## Note
In the first test case of the example, you need to act as follows: "aabc" $$$\rightarrow$$$ "ac" $$$\rightarrow$$$ "". Note that with a different order of deletions, the string will not become empty.

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
Given a non-negative integer number $$$n$$$ ($$$n \ge 0$$$). Let's say a triple of non-negative integers $$$(a, b, c)$$$ is good if $$$a + b + c = n$$$, and $$$digsum(a) + digsum(b) + digsum(c) = digsum(n)$$$, where $$$digsum(x)$$$ is the sum of digits of number $$$x$$$.

For example, if $$$n = 26$$$, then the pair $$$(4, 12, 10)$$$ is good, because $$$4 + 12 + 10 = 26$$$, and $$$(4) + (1 + 2) + (1 + 0) = (2 + 6)$$$.

Your task is to find the number of good triples for the given number $$$n$$$. The order of the numbers in a triple matters. For example, the triples $$$(4, 12, 10)$$$ and $$$(10, 12, 4)$$$ are two different triples.

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

The first and only line of the test case contains one integer $$$n$$$ ($$$0 \le n \le 10^7$$$).

## Output Format
For each test case output one integer, the number of good triples for the given integer $$$n$$$. Order of integers in a triple matters.

## Examples
```input
12
11
0
1
2
3
4
5
3141
999
2718
9999999
10000000
```
```output
9
1
3
6
10
15
21
1350
166375
29160
1522435234375
3
```

## Note
In the first example, the good triples are $$$(0, 0, 11)$$$, $$$(0, 1, 10)$$$, $$$(0, 10, 1)$$$, $$$(0, 11, 0)$$$, $$$(1, 0, 10)$$$, $$$(1, 10, 0)$$$, $$$(10, 0, 1)$$$, $$$(10, 1, 0)$$$, $$$(11, 0, 0)$$$.

In the second example, there is only one good triple $$$(0, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
In the end of the day, Anna needs to turn off the lights in the office. There are $$$n$$$ lights and $$$n$$$ light switches, but their operation scheme is really strange. The switch $$$i$$$ changes the state of light $$$i$$$, but it also changes the state of some other light $$$a_i$$$ (change the state means that if the light was on, it goes off and vice versa).

Help Anna to turn all the lights off using minimal number of switches, or say it is impossible.

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

The first line of each test case contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of lights.

The second line of each test case contains the string of $$$n$$$ characters, the initial state of the lights. Character "0" means that the corresponding light is off, and "1" means that it is on.

The third line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) — the switch $$$i$$$ changes the states of light $$$i$$$ and light $$$a_i$$$.

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

## Output Format
For each test case output the integer $$$k$$$, the minimal number of switches to use, then in the separate line output the list of $$$k$$$ switches.

If it is impossible to turn off all the lights, output single integer $$$-1$$$.

## Examples
```input
8
5
11101
4 3 4 2 2
2
10
2 1
10
0000000011
9 10 10 7 10 9 9 9 10 2
10
1000111101
9 3 8 9 2 1 3 7 2 7
10
0001101010
5 7 6 10 8 3 6 6 2 2
10
0101100010
8 7 7 9 9 4 1 4 2 7
10
1010111010
7 9 10 7 7 2 8 6 10 4
10
1110000001
3 10 10 1 10 8 6 3 2 1
```
```output
3
1 5 3 
-1
1
9 
5
5 6 10 2 3 
6
4 9 5 10 8 7 
3
5 4 9 
6
1 3 5 9 7 8 
2
2 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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Nick has some permutation consisting of p integers from 1 to n. A segment [l, r] (l ≤ r) is a set of elements pi satisfying l ≤ i ≤ r.

Nick calls a pair of segments [a0, a1] and [b0, b1] (1 ≤ a0 ≤ a1 < b0 ≤ b1 ≤ n) good if all their (a1 - a0 + b1 - b0 + 2) elements, when sorted in ascending order, form an arithmetic progression with a difference of 1. That is, when they sorted in ascending order, the elements are in the form {x, x + 1, x + 2, ..., x + m - 1}, for some x and m.

Your task is to find the number of distinct pairs of good segments in the given permutation. Two pairs of segments are considered distinct if the sets of elements contained in these pairs of segments are distinct. For example, any segment [l, r] (l < r) can be represented as a pair of segments, as [l, i] and [i + 1, r] (l ≤ i ≤ r). As all these pairs consist of the same set of elements, they are considered identical.

See the notes accompanying the sample tests for clarification.

## Input Format
The first line contains integer n (1 ≤ n ≤ 3·105) — the permutation size. The second line contains n space-separated distinct integers pi, (1 ≤ pi ≤ n).

## Output Format
Print a single integer — the number of good pairs of segments of permutation p.

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

## Examples
```input
3
1 2 3
```
```output
3
```
-----
```input
5
1 4 5 3 2
```
```output
10
```
-----
```input
5
5 4 3 1 2
```
```output
10
```

## Note
In the first sample the following pairs of segments are good: ([1, 1], [2, 2]); ([2, 2], [3, 3]); ([1, 2], [3, 3]). Pair of segments ([1, 1], [2, 3]) is by definition equivalent to pair ([1, 2], [3, 3]), since both of them covers the same set of elements, namely {1, 2, 3}.

In the third sample the following pairs of segments are good: ([4, 4], [5, 5]); ([3, 3],[4, 5]); ([2, 2],[3, 5]); ([1, 1],[2, 5]); ([3, 3],[5, 5]); ([2, 3],[5, 5]); ([1, 3],[5, 5]); ([2, 2],[3, 3]); ([1, 1],[2, 3]); ([1, 1],[2, 2]).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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$$$ of $$$n$$$ integers. You must perform the following two operations on the array (the first, then the second):

1. Arbitrarily rearrange the elements of the array or leave the order of its elements unchanged.
2. Choose at most one contiguous segment of elements and replace the signs of all elements in this segment with their opposites. Formally, you can choose a pair of indices $$$l, r$$$ such that $$$1 \le l \le r \le n$$$ and assign $$$a_i = -a_i$$$ for all $$$l \le i \le r$$$ (negate elements). Note that you may choose not to select a pair of indices and leave all the signs of the elements unchanged.

What is the maximum sum of the array elements after performing these two operations (the first, then the second)?

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — elements of the array.

## Output Format
For each test case, output the maximum sum of the array elements after sequentially performing the two given operations.

## Examples
```input
8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12
```
```output
8
0
1
99
22
15
270
78
```

## Note
In the first test case, you can first rearrange the array to get $$$[3,-2,-3]$$$ (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$3 + -((-2) + (-3)) = 8$$$ (operation 2).

In the second test case, you can do nothing in both operations and get the sum $$$0$$$.

In the third test case, you can do nothing in both operations and get the sum $$$0 + 1 = 1$$$.

In the fourth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 1$$$ and get the sum $$$-(-99) = 99$$$ (operation 2).

In the fifth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$10 + -((-2) + (-3)) + 7 = 22$$$ (operation 2).

In the sixth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 5$$$ and get the sum $$$-((-1)+(-2)+(-3)+(-4)+(-5))=15$$$ (operation 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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three positive integers $$$a$$$, $$$b$$$ and $$$l$$$ ($$$a,b,l>0$$$).

It can be shown that there always exists a way to choose non-negative (i.e. $$$\ge 0$$$) integers $$$k$$$, $$$x$$$, and $$$y$$$ such that $$$l = k \cdot a^x \cdot b^y$$$.

Your task is to find the number of distinct possible values of $$$k$$$ across all such ways.

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

The following $$$t$$$ lines contain three integers, $$$a$$$, $$$b$$$ and $$$l$$$ ($$$2 \le a, b \le 100$$$, $$$1 \le l \le 10^6$$$) — description of a test case.

## Output Format
Output $$$t$$$ lines, with the $$$i$$$-th ($$$1 \le i \le t$$$) line containing an integer, the answer to the $$$i$$$-th test case.

## Examples
```input
11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043
```
```output
6
1
5
12
6
11
24
4
1
3
24
```

## Note
In the first test case, $$$a=2, b=5, l=20$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 1, x = 2, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 4, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 5, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 10, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 20, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$$$.

In the second test case, $$$a=2, b=5, l=21$$$. Note that $$$l = 21$$$ is not divisible by either $$$a = 2$$$ or $$$b = 5$$$. Therefore, we can only set $$$x = 0, y = 0$$$, which corresponds to $$$k = 21$$$.

In the third test case, $$$a=4, b=6, l=48$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 3, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 8, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 12, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 48, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$$$.

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: 512.0 MB

# Problem
You are given $$$n$$$ circles on the plane. The $$$i$$$-th of these circles is given by a tuple of integers $$$(x_i, y_i, r_i)$$$, where $$$(x_i, y_i)$$$ are the coordinates of its center, and $$$r_i$$$ is the radius of the circle.

Please find a circle $$$C$$$ which meets the following conditions:

- $$$C$$$ is contained inside all $$$n$$$ circles given in the input.
- Among all circles $$$C$$$ that meet the first condition, the radius of the circle is maximum.

Let the largest suitable circle have the radius of $$$a$$$.

Your output $$$C$$$, described as $$$(x,y,r)$$$, will be accepted if it meets the following conditions:

- For each $$$i$$$, $$$\sqrt{(x_i-x)^2+(y_i-y)^2}+ r \le r_i+\max(a,1)\cdot 10^{-7}$$$.
- The absolute or relative error of $$$r$$$ does not exceed $$$10^{-7}$$$. Formally, your answer is accepted if and only if $$$\frac{\left|r - a\right|}{\max(1, a)} \le 10^{-7}$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of circles.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$r_i$$$ ($$$-10^6 \le x_i,y_i \le 10^6$$$, $$$1 \le r_i \le 2 \cdot 10^6$$$).

It is guaranteed that there is a circle with a radius of at least $$$10^{-6}$$$ which is contained inside all $$$n$$$ circles.

## Output Format
Output three real values, $$$x$$$, $$$y$$$, and $$$r$$$ — the coordinates of the center and the radius of the circle.

## Examples
```input
4
1 1 3
-1 1 3
1 -1 2
-1 -1 2
```
```output
0.0000000000000000 -0.7637626158259733 0.9724747683480533
```
-----
```input
4
41580 -23621 95642
-41580 -23621 95642
0 47821 95642
0 0 109750
```
```output
0.0000000000000000 0.0000000000000000 47821.0000000000000000
```

## Note
A two-dimensional plot depicting the first test case is given below. The output circle $$$C$$$ is dashed with blue lines.

A two-dimensional plot depicting the second test case is given below. The output circle $$$C$$$ is dashed with blue lines.

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 three digits $$$a$$$, $$$b$$$, and $$$c$$$. Determine whether they form a stair, a peak, or neither.

- A stair satisfies the condition $$$a<b<c$$$.
- A peak satisfies the condition $$$a<b>c$$$.

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

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a$$$, $$$b$$$, $$$c \leq 9$$$).

## Output Format
For each test case, output "STAIR" if the digits form a stair, "PEAK" if the digits form a peak, and "NONE" otherwise (output the strings without quotes).

## Examples
```input
7
1 2 3
3 2 1
1 5 3
3 4 1
0 0 0
4 1 7
4 5 7
```
```output
STAIR
NONE
PEAK
PEAK
NONE
NONE
STAIR
```

Now solve the problem and return the code.