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

# Problem
During your journey through computer universes, you stumbled upon a very interesting world. It is a path with $$$n$$$ consecutive cells, each of which can either be empty, contain thorns, or a coin. In one move, you can move one or two cells along the path, provided that the destination cell does not contain thorns (and belongs to the path). If you move to the cell with a coin, you pick it up.

Here, green arrows correspond to legal moves, and the red arrow corresponds to an illegal move.

You want to collect as many coins as possible. Find the maximum number of coins you can collect in the discovered world if you start in the leftmost cell of the path.

## Input Format
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then 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 length of the path.

The second line of each test case contains a string of $$$n$$$ characters, the description of the path. The character '.' denotes an empty cell, '@' denotes a cell with a coin, and '*' denotes a cell with thorns. It is guaranteed that the first cell is empty.

## Output Format
For each test case, output a single integer, the maximum number of coins you can collect.

## Examples
```input
3
10
.@@*@.**@@
5
.@@@@
15
.@@..@***..@@@*
```
```output
3
4
3
```

## Note
The picture for the first example is in the problem statement.

Here is the picture for the second example:

And here is the picture for the third example:

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
The Chaya tribe believes that there are $$$n$$$ signs of the apocalypse. Over time, it has been found out that the $$$i$$$-th sign occurs every $$$a_i$$$ years (in years $$$a_i$$$, $$$2 \cdot a_i$$$, $$$3 \cdot a_i$$$, $$$\dots$$$).

According to the legends, for the apocalypse to happen, the signs must occur sequentially. That is, first they wait for the first sign to occur, then strictly after it, the second sign will occur, and so on. That is, if the $$$i$$$-th sign occurred in the year $$$x$$$, the tribe starts waiting for the occurrence of the $$$(i+1)$$$-th sign, starting from the year $$$x+1$$$.

In which year will the $$$n$$$-th sign occur and the apocalypse will happen?

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the periodicities of the signs.

## Output Format
For each test case, output a single integer — the year in which all $$$n$$$ signs will occur.

## Examples
```input
4
6
3 2 4 5 9 18
5
1 2 3 4 5
5
1 1 1 1 1
6
50 30 711 200 503 1006
```
```output
36
5
5
2012
```

## Note
In the first set of input data of the example:

- The tribe will wait for the first sign in the $$$3$$$-rd year;
- the tribe will wait for the second sign in the $$$4$$$-th year (since year $$$2$$$ have already passed);
- the tribe will wait for the third sign in the $$$8$$$-th year (since the second sign has already occurred in the $$$4$$$-th year);
- the tribe will wait for the fourth sign in the $$$10$$$-th year (since year $$$5$$$ have already passed);
- the tribe will wait for the fifth sign in the $$$18$$$-th year (since year $$$9$$$ have already passed);
- the tribe will wait for the sixth sign in the $$$36$$$-th year (since the fifth sign has already occurred in the $$$18$$$-th year).

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

# Problem
You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero.

The countdown consists of $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $$$x$$$ to $$$x-1$$$, it doesn't happen in one move. Instead, each change of a single digit takes one second.

So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.

Find out how much time is left before the countdown reaches zero.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 4\cdot 10^5$$$).

The second line contains a string of $$$n$$$ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.

The sum of $$$n$$$ for all tests does not exceed $$$4\cdot 10^5$$$.

## Output Format
For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.

## Examples
```input
5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002
```
```output
46
13715
108
5
507200774732968121125145546
```

## Note
In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $$$2\cdot 4 + 1\cdot(42-4) = 46$$$.

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
There is a fun game where you need to feed cats that come and go. The level of the game consists of $$$n$$$ steps. There are $$$m$$$ cats; the cat $$$i$$$ is present in steps from $$$l_i$$$ to $$$r_i$$$, inclusive. In each step, you can feed all the cats that are currently present or do nothing.

If you feed the same cat more than once, it will overeat, and you will immediately lose the game. Your goal is to feed as many cats as possible without causing any cat to overeat.

Find the maximum number of cats you can feed.

Formally, you need to select several integer points from the segment from $$$1$$$ to $$$n$$$ in such a way that among given segments, none covers two or more of the selected points, and as many segments as possible cover one of the selected points.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m\le 2\cdot 10^5$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains a pair of integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

The sum of $$$n$$$ for all tests does not exceed $$$10^6$$$, the sum of $$$m$$$ for all tests does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, print a single integer, the maximum number of cats you can feed.

## Examples
```input
3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4
```
```output
5
1
10
```

## Note
In the first example, one of the ways to feed five cats is to feed at steps $$$4$$$ and $$$11$$$.

- At step $$$4$$$, cats $$$1$$$, $$$2$$$, and $$$3$$$ will be fed.
- At step $$$11$$$, cats $$$5$$$ and $$$6$$$ will be fed.

Now solve the problem and return the code.