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
There is a grid with $$$n$$$ rows and $$$m$$$ columns. Some cells are colored black, and the rest of the cells are colored white.

In one operation, you can select some black cell and do exactly one of the following:

- color all cells in its row black, or
- color all cells in its column black.

You are given two integers $$$r$$$ and $$$c$$$. Find the minimum number of operations required to make the cell in row $$$r$$$ and column $$$c$$$ black, or determine that it is impossible.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$r$$$, and $$$c$$$ ($$$1 \leq n, m \leq 50$$$; $$$1 \leq r \leq n$$$; $$$1 \leq c \leq m$$$) — the number of rows and the number of columns in the grid, and the row and column of the cell you need to turn black, respectively.

Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either 'B' or 'W' — a black and a white cell, respectively.

## Output Format
For each test case, if it is impossible to make the cell in row $$$r$$$ and column $$$c$$$ black, output $$$-1$$$.

Otherwise, output a single integer — the minimum number of operations required to make the cell in row $$$r$$$ and column $$$c$$$ black.

## Examples
```input
9
3 5 1 4
WBWWW
BBBWB
WWBBB
4 3 2 1
BWW
BBW
WBB
WWB
2 3 2 2
WWW
WWW
2 2 1 1
WW
WB
5 9 5 9
WWWWWWWWW
WBWBWBBBW
WBBBWWBWW
WBWBWBBBW
WWWWWWWWW
1 1 1 1
B
1 1 1 1
W
1 2 1 1
WB
2 1 1 1
W
B
```
```output
1
0
-1
2
2
0
-1
1
1
```

## Note
The first test case is pictured below.

We can take the black cell in row $$$1$$$ and column $$$2$$$, and make all cells in its row black. Therefore, the cell in row $$$1$$$ and column $$$4$$$ will become black.

In the second test case, the cell in row $$$2$$$ and column $$$1$$$ is already black.

In the third test case, it is impossible to make the cell in row $$$2$$$ and column $$$2$$$ black.

The fourth test case is pictured below.

We can take the black cell in row $$$2$$$ and column $$$2$$$ and make its column black.

Then, we can take the black cell in row $$$1$$$ and column $$$2$$$ and make its row black.

Therefore, the cell in row $$$1$$$ and column $$$1$$$ will become black.

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

# Problem
You are given a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, with edges numbered from $$$1$$$ to $$$n-1$$$. A tree is a connected undirected graph without cycles. You have to assign integer weights to each edge of the tree, such that the resultant graph is a prime tree.

A prime tree is a tree where the weight of every path consisting of one or two edges is prime. A path should not visit any vertex twice. The weight of a path is the sum of edge weights on that path.

Consider the graph below. It is a prime tree as the weight of every path of two or less edges is prime. For example, the following path of two edges: $$$2 \to 1 \to 3$$$ has a weight of $$$11 + 2 = 13$$$, which is prime. Similarly, the path of one edge: $$$4 \to 3$$$ has a weight of $$$5$$$, which is also prime.

Print any valid assignment of weights such that the resultant tree is a prime tree. If there is no such assignment, then print $$$-1$$$. It can be proven that if a valid assignment exists, one exists with weights between $$$1$$$ and $$$10^5$$$ as well.

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

Then, $$$n-1$$$ lines follow. The $$$i$$$-th line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) denoting that edge number $$$i$$$ is between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

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

## Output Format
For each test case, if a valid assignment exists, then print a single line containing $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$), where $$$a_i$$$ denotes the weight assigned to the edge numbered $$$i$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any.

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

## Note
For the first test case, there are only two paths having one edge each: $$$1 \to 2$$$ and $$$2 \to 1$$$, both having a weight of $$$17$$$, which is prime.

The second test case is described in the statement.

It can be proven that no such assignment exists for the third test case.

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 an array $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ distinct integers. You are allowed to perform the following operation on it:

- Choose two elements from the array $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$) such that $$$\gcd(a_i, a_j)$$$ is not present in the array, and add $$$\gcd(a_i, a_j)$$$ to the end of the array. Here $$$\gcd(x, y)$$$ denotes greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Note that the array changes after each operation, and the subsequent operations are performed on the new array.

What is the maximum number of times you can perform the operation on the array?

## Input Format
The first line consists of a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

The second line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). All $$$a_i$$$ are distinct.

## Output Format
Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

## Examples
```input
5
4 20 1 25 30
```
```output
3
```
-----
```input
3
6 10 15
```
```output
4
```

## Note
In the first example, one of the ways to perform maximum number of operations on the array is:

- Pick $$$i = 1, j= 5$$$ and add $$$\gcd(a_1, a_5) = \gcd(4, 30) = 2$$$ to the array.
- Pick $$$i = 2, j= 4$$$ and add $$$\gcd(a_2, a_4) = \gcd(20, 25) = 5$$$ to the array.
- Pick $$$i = 2, j= 5$$$ and add $$$\gcd(a_2, a_5) = \gcd(20, 30) = 10$$$ to the array.

It can be proved that there is no way to perform more than $$$3$$$ operations on the original array.

In the second example one can add $$$3$$$, then $$$1$$$, then $$$5$$$, and $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Team Red and Team Blue competed in a competitive FPS. Their match was streamed around the world. They played a series of $$$n$$$ matches.

In the end, it turned out Team Red won $$$r$$$ times and Team Blue won $$$b$$$ times. Team Blue was less skilled than Team Red, so $$$b$$$ was strictly less than $$$r$$$.

You missed the stream since you overslept, but you think that the match must have been neck and neck since so many people watched it. So you imagine a string of length $$$n$$$ where the $$$i$$$-th character denotes who won the $$$i$$$-th match  — it is R if Team Red won or B if Team Blue won. You imagine the string was such that the maximum number of times a team won in a row was as small as possible. For example, in the series of matches RBBRRRB, Team Red won $$$3$$$ times in a row, which is the maximum.

You must find a string satisfying the above conditions. If there are multiple answers, print any.

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

Each test case has a single line containing three integers $$$n$$$, $$$r$$$, and $$$b$$$ ($$$3 \leq n \leq 100$$$; $$$1 \leq b < r \leq n$$$, $$$r+b=n$$$).

## Output Format
For each test case, output a single line containing a string satisfying the given conditions. If there are multiple answers, print any.

## Examples
```input
3
7 4 3
6 5 1
19 13 6
```
```output
RBRBRBR
RRRBRR
RRBRRBRRBRRBRRBRRBR
```
-----
```input
6
3 2 1
10 6 4
11 6 5
10 9 1
10 8 2
11 9 2
```
```output
RBR
RRBRBRBRBR
RBRBRBRBRBR
RRRRRBRRRR
RRRBRRRBRR
RRRBRRRBRRR
```

## Note
The first test case of the first example gives the optimal answer for the example in the statement. The maximum number of times a team wins in a row in RBRBRBR is $$$1$$$. We cannot minimize it any further.

The answer for the second test case of the second example is RRBRBRBRBR. The maximum number of times a team wins in a row is $$$2$$$, given by RR at the beginning. We cannot minimize the answer any further.

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 a grid with $$$n$$$ rows and $$$m$$$ columns. Rows and columns are numbered from $$$1$$$ to $$$n$$$, and from $$$1$$$ to $$$m$$$. The intersection of the $$$a$$$-th row and $$$b$$$-th column is denoted by $$$(a, b)$$$.

Initially, you are standing in the top left corner $$$(1, 1)$$$. Your goal is to reach the bottom right corner $$$(n, m)$$$.

You can move in four directions from $$$(a, b)$$$: up to $$$(a-1, b)$$$, down to $$$(a+1, b)$$$, left to $$$(a, b-1)$$$ or right to $$$(a, b+1)$$$.

You cannot move in the same direction in two consecutive moves, and you cannot leave the grid. What is the minimum number of moves to reach $$$(n, m)$$$?

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of the test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the size of the grid.

## Output Format
For each test case, print a single integer: $$$-1$$$ if it is impossible to reach $$$(n, m)$$$ under the given conditions, otherwise the minimum number of moves.

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

## Note
Test case $$$1$$$: $$$n=1$$$, $$$m=1$$$, and initially you are standing in $$$(1, 1)$$$ so $$$0$$$ move is required to reach $$$(n, m) = (1, 1)$$$.

Test case $$$2$$$: you should go down to reach $$$(2, 1)$$$.

Test case $$$3$$$: it is impossible to reach $$$(1, 3)$$$ without moving right two consecutive times, or without leaving the grid.

Test case $$$4$$$: an optimal moving sequence could be: $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)$$$. It can be proved that this is the optimal solution. So the answer is $$$6$$$.

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

# Problem
$$$m$$$ chairs are arranged in a circle sequentially. The chairs are numbered from $$$0$$$ to $$$m-1$$$. $$$n$$$ people want to sit in these chairs. The $$$i$$$-th of them wants at least $$$a[i]$$$ empty chairs both on his right and left side.

More formally, if the $$$i$$$-th person sits in the $$$j$$$-th chair, then no one else should sit in the following chairs: $$$(j-a[i]) \bmod m$$$, $$$(j-a[i]+1) \bmod m$$$, ... $$$(j+a[i]-1) \bmod m$$$, $$$(j+a[i]) \bmod m$$$.

Decide if it is possible to sit down for all of them, under the given limitations.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$) — the number of people and the number of chairs.

The next line contains $$$n$$$ integers, $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the minimum number of empty chairs, on both sides of the $$$i$$$-th person.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^5$$$.

## Output Format
For each test case print "YES" (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and "NO" (without quotes) otherwise.

You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

## Examples
```input
6
3 2
1 1 1
2 4
1 1
2 5
2 1
3 8
1 2 1
4 12
1 2 1 3
4 19
1 2 1 3
```
```output
NO
YES
NO
YES
NO
YES
```

## Note
Test case $$$1$$$: $$$n>m$$$, so they can not sit down.

Test case $$$2$$$: the first person can sit $$$2$$$-nd and the second person can sit in the $$$0$$$-th chair. Both of them want at least $$$1$$$ empty chair on both sides, chairs $$$1$$$ and $$$3$$$ are free, so this is a good solution.

Test case $$$3$$$: if the second person sits down somewhere, he needs $$$2$$$ empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only $$$5$$$ chairs.

Test case $$$4$$$: they can sit in the $$$1$$$-st, $$$4$$$-th, $$$7$$$-th chairs respectively.

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 two integers $$$x$$$ and $$$y$$$. You want to choose two strictly positive (greater than zero) integers $$$a$$$ and $$$b$$$, and then apply the following operation to $$$x$$$ exactly $$$a$$$ times: replace $$$x$$$ with $$$b \cdot x$$$.

You want to find two positive integers $$$a$$$ and $$$b$$$ such that $$$x$$$ becomes equal to $$$y$$$ after this process. If there are multiple possible pairs, you can choose any of them. If there is no such pair, report it.

For example:

- if $$$x = 3$$$ and $$$y = 75$$$, you may choose $$$a = 2$$$ and $$$b = 5$$$, so that $$$x$$$ becomes equal to $$$3 \cdot 5 \cdot 5 = 75$$$;
- if $$$x = 100$$$ and $$$y = 100$$$, you may choose $$$a = 3$$$ and $$$b = 1$$$, so that $$$x$$$ becomes equal to $$$100 \cdot 1 \cdot 1 \cdot 1 = 100$$$;
- if $$$x = 42$$$ and $$$y = 13$$$, there is no answer since you cannot decrease $$$x$$$ with the given operations.

## 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 two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 100$$$).

## Output Format
If it is possible to choose a pair of positive integers $$$a$$$ and $$$b$$$ so that $$$x$$$ becomes $$$y$$$ after the aforementioned process, print these two integers. The integers you print should be not less than $$$1$$$ and not greater than $$$10^9$$$ (it can be shown that if the answer exists, there is a pair of integers $$$a$$$ and $$$b$$$ meeting these constraints). If there are multiple such pairs, print any of them.

If it is impossible to choose a pair of integers $$$a$$$ and $$$b$$$ so that $$$x$$$ becomes $$$y$$$, print the integer $$$0$$$ twice.

## Examples
```input
3
3 75
100 100
42 13
```
```output
2 5
3 1
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: 512.0 MB

# Problem
The Berland language consists of words having exactly two letters. Moreover, the first letter of a word is different from the second letter. Any combination of two different Berland letters (which, by the way, are the same as the lowercase letters of Latin alphabet) is a correct word in Berland language.

The Berland dictionary contains all words of this language. The words are listed in a way they are usually ordered in dictionaries. Formally, word $$$a$$$ comes earlier than word $$$b$$$ in the dictionary if one of the following conditions hold:

- the first letter of $$$a$$$ is less than the first letter of $$$b$$$;
- the first letters of $$$a$$$ and $$$b$$$ are the same, and the second letter of $$$a$$$ is less than the second letter of $$$b$$$.

So, the dictionary looks like that:

- Word $$$1$$$: ab
- Word $$$2$$$: ac
- ...
- Word $$$25$$$: az
- Word $$$26$$$: ba
- Word $$$27$$$: bc
- ...
- Word $$$649$$$: zx
- Word $$$650$$$: zy

You are given a word $$$s$$$ from the Berland language. Your task is to find its index in the dictionary.

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

Each test case consists of one line containing $$$s$$$ — a string consisting of exactly two different lowercase Latin letters (i. e. a correct word of the Berland language).

## Output Format
For each test case, print one integer — the index of the word $$$s$$$ in the dictionary.

## Examples
```input
7
ab
ac
az
ba
bc
zx
zy
```
```output
1
2
25
26
27
649
650
```

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 a string $$$s$$$, consisting only of Latin letters 'a', and a string $$$t$$$, consisting of lowercase Latin letters.

In one move, you can replace any letter 'a' in the string $$$s$$$ with a string $$$t$$$. Note that after the replacement string $$$s$$$ might contain letters other than 'a'.

You can perform an arbitrary number of moves (including zero). How many different strings can you obtain? Print the number, or report that it is infinitely large.

Two strings are considered different if they have different length, or they differ at some index.

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

The first line of each testcase contains a non-empty string $$$s$$$, consisting only of Latin letters 'a'. The length of $$$s$$$ doesn't exceed $$$50$$$.

The second line contains a non-empty string $$$t$$$, consisting of lowercase Latin letters. The length of $$$t$$$ doesn't exceed $$$50$$$.

## Output Format
For each testcase, print the number of different strings $$$s$$$ that can be obtained after an arbitrary amount of moves (including zero). If the number is infinitely large, print -1. Otherwise, print the number.

## Examples
```input
3
aaaa
a
aa
abc
a
b
```
```output
1
-1
2
```

## Note
In the first example, you can replace any letter 'a' with the string "a", but that won't change the string. So no matter how many moves you make, you can't obtain a string other than the initial one.

In the second example, you can replace the second letter 'a' with "abc". String $$$s$$$ becomes equal to "aabc". Then the second letter 'a' again. String $$$s$$$ becomes equal to "aabcbc". And so on, generating infinitely many different strings.

In the third example, you can either leave string $$$s$$$ as is, performing zero moves, or replace the only 'a' with "b". String $$$s$$$ becomes equal to "b", so you can't perform more moves on it.

Now solve the problem and return the code.