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

# Problem
You have $$$n$$$ chains, the $$$i$$$-th chain consists of $$$c_i$$$ vertices. Vertices in each chain are numbered independently from $$$1$$$ to $$$c_i$$$ along the chain. In other words, the $$$i$$$-th chain is the undirected graph with $$$c_i$$$ vertices and $$$(c_i - 1)$$$ edges connecting the $$$j$$$-th and the $$$(j + 1)$$$-th vertices for each $$$1 \le j < c_i$$$.

Now you decided to unite chains in one graph in the following way:

1. the first chain is skipped;
2. the $$$1$$$-st vertex of the $$$i$$$-th chain is connected by an edge with the $$$a_i$$$-th vertex of the $$$(i - 1)$$$-th chain;
3. the last ($$$c_i$$$-th) vertex of the $$$i$$$-th chain is connected by an edge with the $$$b_i$$$-th vertex of the $$$(i - 1)$$$-th chain.

Picture of the first test case. Dotted lines are the edges added during uniting process

Calculate the length of the longest simple cycle in the resulting graph.

A simple cycle is a chain where the first and last vertices are connected as well. If you travel along the simple cycle, each vertex of this cycle will be visited exactly once.

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

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

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$2 \le c_i \le 10^9$$$) — the number of vertices in the corresponding chains.

The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_1 = -1$$$; $$$1 \le a_i \le c_{i - 1}$$$).

The fourth line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$b_1 = -1$$$; $$$1 \le b_i \le c_{i - 1}$$$).

Both $$$a_1$$$ and $$$b_1$$$ are equal to $$$-1$$$, they aren't used in graph building and given just for index consistency. It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print the length of the longest simple cycle.

## Examples
```input
3
4
3 4 3 3
-1 1 2 2
-1 2 2 3
2
5 6
-1 5
-1 1
3
3 5 2
-1 1 1
-1 3 5
```
```output
7
11
8
```

## Note
In the first test case, the longest simple cycle is shown below:

We can't increase it with the first chain, since in such case it won't be simple — the vertex $$$2$$$ on the second chain will break simplicity.

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
There are $$$n + 1$$$ cities, numbered from $$$0$$$ to $$$n$$$. $$$n$$$ roads connect these cities, the $$$i$$$-th road connects cities $$$i - 1$$$ and $$$i$$$ ($$$i \in [1, n]$$$).

Each road has a direction. The directions are given by a string of $$$n$$$ characters such that each character is either L or R. If the $$$i$$$-th character is L, it means that the $$$i$$$-th road initially goes from the city $$$i$$$ to the city $$$i - 1$$$; otherwise it goes from the city $$$i - 1$$$ to the city $$$i$$$.

A traveler would like to visit as many cities of this country as possible. Initially, they will choose some city to start their journey from. Each day, the traveler must go from the city where they currently are to a neighboring city using one of the roads, and they can go along a road only if it is directed in the same direction they are going; i. e., if a road is directed from city $$$i$$$ to the city $$$i + 1$$$, it is possible to travel from $$$i$$$ to $$$i + 1$$$, but not from $$$i + 1$$$ to $$$i$$$. After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. If the traveler cannot go from their current city to a neighboring city, their journey ends; it is also possible to end the journey whenever the traveler wants to.

The goal of the traveler is to visit as many different cities as possible (they can visit a city multiple times, but only the first visit is counted). For each city $$$i$$$, calculate the maximum number of different cities the traveler can visit during exactly one journey if they start in the city $$$i$$$.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). The second line contains the string $$$s$$$ consisting of exactly $$$n$$$ characters, each character is either L or R.

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

## Output Format
For each test case, print $$$n + 1$$$ integers. The $$$i$$$-th integer should be equal to the maximum number of different cities the traveler can visit during one journey if this journey starts in the $$$i$$$-th city.

## Examples
```input
2
6
LRRRLL
3
LRL
```
```output
1 3 2 3 1 3 2
1 4 1 4
```

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
There are $$$n$$$ lanterns in a row. The lantern $$$i$$$ is placed in position $$$i$$$ and has power equal to $$$p_i$$$.

Each lantern can be directed to illuminate either some lanterns to the left or some lanterns to the right. If the $$$i$$$-th lantern is turned to the left, it illuminates all such lanterns $$$j$$$ that $$$j \in [i - p_i, i - 1]$$$. Similarly, if it is turned to the right, it illuminates all such lanterns $$$j$$$ that $$$j \in [i + 1, i + p_i]$$$.

Your goal is to choose a direction for each lantern so each lantern is illuminated by at least one other lantern, or report that it is impossible.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of lanterns.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n$$$) — the power of the $$$i$$$-th lantern.

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

## Output Format
For each test case, print the answer as follows:

If it is possible to direct all lanterns so that each lantern is illuminated, print YES in the first line and a string of $$$n$$$ characters L and/or R (the $$$i$$$-th character is L if the $$$i$$$-th lantern is turned to the left, otherwise this character is R) in the second line. If there are multiple answers, you may print any of them.

If there is no answer, simply print NO for that test case.

## Examples
```input
4
8
0 0 3 1 1 1 1 2
2
1 1
2
2 2
2
0 1
```
```output
YES
RRLLLLRL
YES
RL
YES
RL
NO
```

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
$$$n$$$ heroes fight against each other in the Arena. Initially, the $$$i$$$-th hero has level $$$a_i$$$.

Each minute, a fight between two different heroes occurs. These heroes can be chosen arbitrarily (it's even possible that it is the same two heroes that were fighting during the last minute).

When two heroes of equal levels fight, nobody wins the fight. When two heroes of different levels fight, the one with the higher level wins, and his level increases by $$$1$$$.

The winner of the tournament is the first hero that wins in at least $$$100^{500}$$$ fights (note that it's possible that the tournament lasts forever if no hero wins this number of fights, then there is no winner). A possible winner is a hero such that there exists a sequence of fights that this hero becomes the winner of the tournament.

Calculate the number of possible winners among $$$n$$$ heroes.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of heroes. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the initial level of the $$$i$$$-th hero.

## Output Format
For each test case, print one integer — the number of possible winners among the given $$$n$$$ heroes.

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

## Note
In the first test case of the example, the only possible winner is the first hero.

In the second test case of the example, each fight between the heroes results in nobody winning it, so the tournament lasts forever and there is no winner.

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
Suppose you are living with two cats: A and B. There are $$$n$$$ napping spots where both cats usually sleep.

Your cats like to sleep and also like all these spots, so they change napping spot each hour cyclically:

- Cat A changes its napping place in order: $$$n, n - 1, n - 2, \dots, 3, 2, 1, n, n - 1, \dots$$$ In other words, at the first hour it's on the spot $$$n$$$ and then goes in decreasing order cyclically;
- Cat B changes its napping place in order: $$$1, 2, 3, \dots, n - 1, n, 1, 2, \dots$$$ In other words, at the first hour it's on the spot $$$1$$$ and then goes in increasing order cyclically.

The cat B is much younger, so they have a strict hierarchy: A and B don't lie together. In other words, if both cats'd like to go in spot $$$x$$$ then the A takes this place and B moves to the next place in its order (if $$$x < n$$$ then to $$$x + 1$$$, but if $$$x = n$$$ then to $$$1$$$). Cat B follows his order, so it won't return to the skipped spot $$$x$$$ after A frees it, but will move to the spot $$$x + 2$$$ and so on.

Calculate, where cat B will be at hour $$$k$$$?

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$) — the number of spots and hour $$$k$$$.

## Output Format
For each test case, print one integer — the index of the spot where cat B will sleep at hour $$$k$$$.

## Examples
```input
7
2 1
2 2
3 1
3 2
3 3
5 5
69 1337
```
```output
1
2
1
3
2
2
65
```

## Note
In the first and second test cases $$$n = 2$$$, so:

- at the $$$1$$$-st hour, A is on spot $$$2$$$ and B is on $$$1$$$;
- at the $$$2$$$-nd hour, A moves to spot $$$1$$$ and B — to $$$2$$$.

- at the $$$1$$$-st hour, A is on spot $$$3$$$ and B is on $$$1$$$;
- at the $$$2$$$-nd hour, A moves to spot $$$2$$$; B'd like to move from $$$1$$$ to $$$2$$$, but this spot is occupied, so it moves to $$$3$$$;
- at the $$$3$$$-rd hour, A moves to spot $$$1$$$; B also would like to move from $$$3$$$ to $$$1$$$, but this spot is occupied, so it moves to $$$2$$$.

In the sixth test case:

- A's spots at each hour are $$$[5, 4, 3, 2, 1]$$$;
- B's spots at each hour are $$$[1, 2, 4, 5, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A Pythagorean triple is a triple of integer numbers $$$(a, b, c)$$$ such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to $$$a$$$, $$$b$$$ and $$$c$$$, respectively. An example of the Pythagorean triple is $$$(3, 4, 5)$$$.

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: $$$c = a^2 - b$$$.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple $$$(3, 4, 5)$$$: $$$5 = 3^2 - 4$$$, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

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

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

## Output Format
For each test case, print one integer — the number of triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

## Examples
```input
3
3
6
9
```
```output
0
1
1
```

## Note
The only Pythagorean triple satisfying $$$c = a^2 - b$$$ with $$$1 \le a \le b \le c \le 9$$$ is $$$(3, 4, 5)$$$; that's why the answer for $$$n = 3$$$ is $$$0$$$, and the answer for $$$n = 6$$$ (and for $$$n = 9$$$) is $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive (greater than zero) integer $$$n$$$.

You have to represent $$$n$$$ as the sum of integers (possibly negative) consisting only of ones (digits '1'). For example, $$$24 = 11 + 11 + 1 + 1$$$ and $$$102 = 111 - 11 + 1 + 1$$$.

Among all possible representations, you have to find the one that uses the minimum number of ones in total.

## Input Format
The single line contains one integer $$$n$$$ ($$$1 \le n < 10^{50}$$$).

## Output Format
Print one integer $$$x$$$ — the minimum number of ones, such that there exist a representation of $$$n$$$ as the sum of integers (possibly negative) that uses $$$x$$$ ones in total.

## Examples
```input
24
```
```output
6
```
-----
```input
102
```
```output
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: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
You have $$$c_1$$$ letters 'a', $$$c_2$$$ letters 'b', ..., $$$c_{26}$$$ letters 'z'. You want to build a beautiful string of length $$$n$$$ from them (obviously, you cannot use the $$$i$$$-th letter more than $$$c_i$$$ times). Each $$$c_i$$$ is greater than $$$\frac{n}{3}$$$.

A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than $$$1$$$ in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than $$$1$$$ (for example, "aca"). Another example: the string "abcaa" is beautiful.

Calculate the number of different strings you can build, and print the answer modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 400$$$).

The second line contains $$$26$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_{26}$$$ ($$$\frac{n}{3} < c_i \le n$$$).

## Output Format
Print one integer — the number of strings you can build, taken modulo $$$998244353$$$.

## Examples
```input
4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
```
```output
422500
```
-----
```input
3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2
```
```output
16900
```
-----
```input
400
348 322 247 158 209 134 151 267 268 176 214 379 372 291 388 135 147 304 169 149 193 351 380 368 181 340
```
```output
287489790
```

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
There is a square field of size $$$n \times n$$$ in which two cells are marked. These cells can be in the same row or column.

You are to mark two more cells so that they are the corners of a rectangle with sides parallel to the coordinate axes.

For example, if $$$n=4$$$ and a rectangular field looks like this (there are asterisks in the marked cells):

$$$$$$ \begin{matrix} . & . & * & . \\ . & . & . & . \\ * & . & . & . \\ . & . & . & . \\ \end{matrix} $$$$$$

Then you can mark two more cells as follows

$$$$$$ \begin{matrix} * & . & * & . \\ . & . & . & . \\ * & . & * & . \\ . & . & . & . \\ \end{matrix} $$$$$$

If there are several possible solutions, then print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 400$$$). Then $$$t$$$ test cases follow.

The first row of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the number of rows and columns in the table.

The following $$$n$$$ lines each contain $$$n$$$ characters '.' or '*' denoting empty and marked cells, respectively.

It is guaranteed that the sums of $$$n$$$ for all test cases do not exceed $$$400$$$.

It is guaranteed that there are exactly two asterisks on the field. They can be in the same row/column.

It is guaranteed that the solution exists.

## Output Format
For each test case, output $$$n$$$ rows of $$$n$$$ characters — a field with four asterisks marked corresponding to the statements. If there multiple correct answers, print any of them.

## Examples
```input
6
4
..*.
....
*...
....
2
*.
.*
2
.*
.*
3
*.*
...
...
5
.....
..*..
.....
.*...
.....
4
....
....
*...
*...
```
```output
*.*.
....
*.*.
....
**
**
**
**
*.*
*.*
...
.....
.**..
.....
.**..
.....
....
....
**..
**..
```

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 number $$$n$$$ and an array $$$b_1, b_2, \ldots, b_{n+2}$$$, obtained according to the following algorithm:

- some array $$$a_1, a_2, \ldots, a_n$$$ was guessed;
- array $$$a$$$ was written to array $$$b$$$, i.e. $$$b_i = a_i$$$ ($$$1 \le i \le n$$$);
- The $$$(n+1)$$$-th element of the array $$$b$$$ is the sum of the numbers in the array $$$a$$$, i.e. $$$b_{n+1} = a_1+a_2+\ldots+a_n$$$;
- The $$$(n+2)$$$-th element of the array $$$b$$$ was written some number $$$x$$$ ($$$1 \le x \le 10^9$$$), i.e. $$$b_{n+2} = x$$$; The
- array $$$b$$$ was shuffled.

For example, the array $$$b=[2, 3, 7, 12 ,2]$$$ it could be obtained in the following ways:

- $$$a=[2, 2, 3]$$$ and $$$x=12$$$;
- $$$a=[3, 2, 7]$$$ and $$$x=2$$$.

For the given array $$$b$$$, find any array $$$a$$$ that could have been guessed initially.

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

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

The second row of each test case contains $$$n+2$$$ integers $$$b_1, b_2, \ldots, b_{n+2}$$$ ($$$1 \le b_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, output:

- "-1", if the array $$$b$$$ could not be obtained from any array $$$a$$$;
- $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, otherwise.

If there are several arrays of $$$a$$$, you can output any.

## Examples
```input
4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1
```
```output
2 3 7 
-1
2 2 2 3 9 
1 2 6
```

Now solve the problem and return the code.