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
Vladislav has a binary square grid of $$$n \times n$$$ cells. A triangle or a square is drawn on the grid with symbols $$$\texttt{1}$$$. As he is too busy being cool, he asks you to tell him which shape is drawn on the grid.

- A triangle is a shape consisting of $$$k$$$ ($$$k>1$$$) consecutive rows, where the $$$i$$$-th row has $$$2 \cdot i-1$$$ consecutive characters $$$\texttt{1}$$$, and the central 1s are located in one column. An upside down triangle is also considered a valid triangle (but not rotated by 90 degrees).

Two left pictures contain examples of triangles: $$$k=4$$$, $$$k=3$$$. The two right pictures don't contain triangles.

- A square is a shape consisting of $$$k$$$ ($$$k>1$$$) consecutive rows, where the $$$i$$$-th row has $$$k$$$ consecutive characters $$$\texttt{1}$$$, which are positioned at an equal distance from the left edge of the grid.

Examples of two squares: $$$k=2$$$, $$$k=4$$$.

For the given grid, determine the type of shape that is drawn on it.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10$$$) — the size of the grid.

The next $$$n$$$ lines each contain $$$n$$$ characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$.

The grid contains exactly one triangle or exactly one square that contains all the $$$\texttt{1}$$$s in the grid. It is guaranteed that the size of the triangle or square is greater than $$$1$$$ (i.e., the shape cannot consist of exactly one 1).

## Output Format
For each test case, output "SQUARE" if all the $$$\texttt{1}$$$s in the grid form a square, and "TRIANGLE" otherwise (without quotes).

## Examples
```input
6
3
000
011
011
4
0000
0000
0100
1110
2
11
11
5
00111
00010
00000
00000
00000
10
0000000000
0000000000
0000000000
0000000000
0000000000
1111111110
0111111100
0011111000
0001110000
0000100000
3
111
111
111
```
```output
SQUARE
TRIANGLE
SQUARE
TRIANGLE
TRIANGLE
SQUARE
```

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

# Problem
Please note that the time limit for this problem is only 0.5 seconds per test.

Vladislav wrote the integers from $$$1$$$ to $$$n$$$, inclusive, on the board. Then he replaced each integer with the sum of its digits.

What is the sum of the numbers on the board now?

For example, if $$$n=12$$$ then initially the numbers on the board are: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.$$$$$$ Then after the replacement, the numbers become: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3.$$$$$$ The sum of these numbers is $$$1+2+3+4+5+6+7+8+9+1+2+3=51$$$. Thus, for $$$n=12$$$ the answer is $$$51$$$.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the largest number Vladislav writes.

## Output Format
For each test case, output a single integer — the sum of the numbers at the end of the process.

## Examples
```input
7
12
1
2
3
1434
2024
200000
```
```output
51
1
3
6
18465
28170
4600002
```

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
Vladislav has $$$n$$$ cards numbered $$$1, 2, \dots, n$$$. He wants to lay them down in a row as follows:

- First, he lays down all the odd-numbered cards from smallest to largest.
- Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $$$2$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$3$$$ times an odd number from smallest to largest (i.e. $$$3$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$4$$$ times an odd number from smallest to largest (i.e. $$$4$$$ multiplied by an odd number).
- And so on, until all cards are laid down.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$) — the number of cards Vlad has, and the position of the card you need to output.

## Output Format
For each test case, output a single integer — the $$$k$$$-th card Vladislav lays down.

## Examples
```input
11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000
```
```output
1
3
5
7
2
6
4
1
27
37
536870912
```

## Note
In the first seven test cases, $$$n=7$$$. Vladislav lays down the cards as follows:

- First — all the odd-numbered cards in the order $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.
- Next — all cards that are twice an odd number in the order $$$2$$$, $$$6$$$.
- Next, there are no remaining cards that are $$$3$$$ times an odd number. (Vladislav has only one of each card.)
- Next — all cards that are $$$4$$$ times an odd number, and there is only one such card: $$$4$$$.
- There are no more cards left, so Vladislav stops.

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

# Problem
Vladislav has a grid of size $$$7 \times 7$$$, where each cell is colored black or white. In one operation, he can choose any cell and change its color (black $$$\leftrightarrow$$$ white).

Find the minimum number of operations required to ensure that there are no black cells with four diagonal neighbors also being black.

The left image shows that initially there are two black cells violating the condition. By flipping one cell, the grid will work.

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

Each test case consists of $$$7$$$ lines, each containing $$$7$$$ characters. Each of these characters is either $$$\texttt{W}$$$ or $$$\texttt{B}$$$, denoting a white or black cell, respectively.

## Output Format
For each test case, output a single integer — the minimum number of operations required to ensure that there are no black cells with all four diagonal neighbors also being black.

## Examples
```input
4
WWWWWWW
WWWWBBB
WWWWWBW
WWBBBBB
WWWBWWW
WWBBBWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
WBBBBBW
WBBBBBW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
BBBBBBB
BBBBBBB
WWWWWWW
BBBBBBB
BBBBBBB
BBBBBBB
```
```output
1
2
0
5
```

## Note
The first test case is illustrated in the statement.

The second test case is illustrated below:

In the third test case, the grid already satisfies the condition.

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
Vladislav has a son who really wanted to go to MIT. The college dormitory at MIT (Moldova Institute of Technology) can be represented as a tree with $$$n$$$ vertices, each vertex being a room with exactly one student. A tree is a connected undirected graph with $$$n$$$ vertices and $$$n-1$$$ edges.

Tonight, there are three types of students:

- students who want to party and play music (marked with $$$\texttt{P}$$$),
- students who wish to sleep and enjoy silence (marked with $$$\texttt{S}$$$), and
- students who don't care (marked with $$$\texttt{C}$$$).

Initially, all the edges are thin walls which allow music to pass through, so when a partying student puts music on, it will be heard in every room. However, we can place some thick walls on any edges — thick walls don't allow music to pass through them.

The university wants to install some thick walls so that every partying student can play music, and no sleepy student can hear it.

Because the university lost a lot of money in a naming rights lawsuit, they ask you to find the minimum number of thick walls they will need to use.

## 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 an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The second line of each test case contains $$$n-1$$$ integers $$$a_2, \dots , a_n$$$ ($$$1 \leq a_i < i$$$) — it means there is an edge between $$$i$$$ and $$$a_i$$$ in the tree.

The third line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{C}$$$, denoting that student $$$i$$$ is of type $$$s_i$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output a single integer — the minimum number of thick walls needed.

## Examples
```input
3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS
```
```output
1
1
2
```

## Note
In the first case, we can install one thick wall between rooms $$$1$$$ and $$$2$$$, as shown below. We cannot install $$$0$$$ walls, since then the music from room 3 will reach room 2 where a student wants to sleep, so the answer is $$$1$$$. There are other valid solutions.

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