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

# Problem
You are given a weighted undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Let's define the weight of the path consisting of $$$k$$$ edges with indices $$$e_1, e_2, \dots, e_k$$$ as $$$\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}$$$, where $$$w_i$$$ — weight of the $$$i$$$-th edge in the graph.

Your task is to find the minimum weight of the path from the $$$1$$$-st vertex to the $$$i$$$-th vertex for each $$$i$$$ ($$$2 \le i \le n$$$).

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph.

Following $$$m$$$ lines contains three integers $$$v_i, u_i, w_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$1 \le w_i \le 10^9$$$; $$$v_i \neq u_i$$$) — endpoints of the $$$i$$$-th edge and its weight respectively.

## Output Format
Print $$$n-1$$$ integers — the minimum weight of the path from $$$1$$$-st vertex to the $$$i$$$-th vertex for each $$$i$$$ ($$$2 \le i \le n$$$).

## Examples
```input
5 4
5 3 4
2 1 1
3 2 2
2 4 2
```
```output
1 2 2 4
```
-----
```input
6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4
```
```output
2 1 4 3 1
```
-----
```input
7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4
```
```output
3 4 2 7 7 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: 4.0 seconds
Memory limit: 32.0 MB

# Problem
Note that the memory limit is unusual.

You are given an integer $$$n$$$ and two sequences $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$.

Let's call a set of integers $$$S$$$ such that $$$S \subseteq \{1, 2, 3, \dots, n\}$$$ strange, if, for every element $$$i$$$ of $$$S$$$, the following condition is met: for every $$$j \in [1, i - 1]$$$, if $$$a_j$$$ divides $$$a_i$$$, then $$$j$$$ is also included in $$$S$$$. An empty set is always strange.

The cost of the set $$$S$$$ is $$$\sum\limits_{i \in S} b_i$$$. You have to calculate the maximum possible cost of a strange set.

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

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

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^5 \le b_i \le 10^5$$$).

## Output Format
Print one integer — the maximum cost of a strange set.

## Examples
```input
9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1
```
```output
16
```
-----
```input
2
42 42
-37 13
```
```output
0
```
-----
```input
2
42 42
13 -37
```
```output
13
```

## Note
The strange set with the maximum cost in the first example is $$$\{1, 2, 4, 8, 9\}$$$.

The strange set with the maximum cost in the second example is 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a road consisting of several rows. Each row is divided into several rectangular tiles, and all tiles in the same row are equal. The first row contains exactly one rectangular tile. Look at the picture below which shows how the tiles are arranged.

The road is constructed as follows:

- the first row consists of $$$1$$$ tile;
- then $$$a_1$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_1$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;
- then $$$a_2$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_2$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;
- ...
- then $$$a_n$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_n$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row.

An example of the road with $$$n = 2$$$, $$$a_1 = 4$$$, $$$b_1 = 2$$$, $$$a_2 = 2$$$, $$$b_2 = 3$$$. Rows are arranged from left to right.

You start from the only tile in the first row and want to reach the last row (any tile of it). From your current tile, you can move to any tile in the next row which touches your current tile.

Calculate the number of different paths from the first row to the last row. Since it can be large, print it modulo $$$998244353$$$.

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

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^5$$$; $$$|a_i - b_i| \le 5$$$).

Additional constraint on the input: the sequence of $$$a_i$$$ and $$$b_i$$$ never results in a row with non-positive number of tiles.

## Output Format
Print one integer — the number of paths from the first row to the last row, taken modulo $$$998244353$$$.

## Examples
```input
2
4 2
2 3
```
```output
850
```
-----
```input
3
4 1
2 3
3 1
```
```output
10150
```
-----
```input
8
328 323
867 868
715 718
721 722
439 435
868 870
834 834
797 796
```
```output
759099319
```

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 two integers $$$n$$$ and $$$k$$$.

You should create an array of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ such that the sum $$$(a_1 + a_2 + \dots + a_n)$$$ is divisible by $$$k$$$ and maximum element in $$$a$$$ is minimum possible.

What is the minimum possible maximum element in $$$a$$$?

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

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

## Output Format
For each test case, print one integer — the minimum possible maximum element in array $$$a$$$ such that the sum $$$(a_1 + \dots + a_n)$$$ is divisible by $$$k$$$.

## Examples
```input
4
1 5
4 3
8 8
8 17
```
```output
5
2
1
3
```

## Note
In the first test case $$$n = 1$$$, so the array consists of one element $$$a_1$$$ and if we make $$$a_1 = 5$$$ it will be divisible by $$$k = 5$$$ and the minimum possible.

In the second test case, we can create array $$$a = [1, 2, 1, 2]$$$. The sum is divisible by $$$k = 3$$$ and the maximum is equal to $$$2$$$.

In the third test case, we can create array $$$a = [1, 1, 1, 1, 1, 1, 1, 1]$$$. The sum is divisible by $$$k = 8$$$ and the maximum is equal to $$$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
You have a statistic of price changes for one product represented as an array of $$$n$$$ positive integers $$$p_0, p_1, \dots, p_{n - 1}$$$, where $$$p_0$$$ is the initial price of the product and $$$p_i$$$ is how the price was increased during the $$$i$$$-th month.

Using these price changes you are asked to calculate the inflation coefficients for each month as the ratio of current price increase $$$p_i$$$ to the price at the start of this month $$$(p_0 + p_1 + \dots + p_{i - 1})$$$.

Your boss said you clearly that the inflation coefficients must not exceed $$$k$$$ %, so you decided to increase some values $$$p_i$$$ in such a way, that all $$$p_i$$$ remain integers and the inflation coefficients for each month don't exceed $$$k$$$ %.

You know, that the bigger changes — the more obvious cheating. That's why you need to minimize the total sum of changes.

What's the minimum total sum of changes you need to make all inflation coefficients not more than $$$k$$$ %?

## 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 two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$1 \le k \le 100$$$) — the length of array $$$p$$$ and coefficient $$$k$$$.

The second line of each test case contains $$$n$$$ integers $$$p_0, p_1, \dots, p_{n - 1}$$$ ($$$1 \le p_i \le 10^9$$$) — the array $$$p$$$.

## Output Format
For each test case, print the minimum total sum of changes you need to make all inflation coefficients not more than $$$k$$$ %.

## Examples
```input
2
4 1
20100 1 202 202
3 100
1 1 1
```
```output
99
0
```

## Note
In the first test case, you can, for example, increase $$$p_0$$$ by $$$50$$$ and $$$p_1$$$ by $$$49$$$ and get array $$$[20150, 50, 202, 202]$$$. Then you get the next inflation coefficients:

1. $$$\frac{50}{20150} \le \frac{1}{100}$$$;
2. $$$\frac{202}{20150 + 50} \le \frac{1}{100}$$$;
3. $$$\frac{202}{20200 + 202} \le \frac{1}{100}$$$;

In the second test case, you don't need to modify array $$$p$$$, since the inflation coefficients are already good:

1. $$$\frac{1}{1} \le \frac{100}{100}$$$;
2. $$$\frac{1}{1 + 1} \le \frac{100}{100}$$$;

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