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

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ zeros. You are also given a set of $$$m$$$ not necessarily different segments. Each segment is defined by two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) and represents a subarray $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ of the array $$$a$$$.

Let's call the segment $$$l_i, r_i$$$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $$$a = [1, 0, 1, 0, 1]$$$, then the segment $$$[1, 5]$$$ is beautiful (the number of ones is $$$3$$$, the number of zeros is $$$2$$$), but the segment $$$[3, 4]$$$ is not is beautiful (the number of ones is $$$1$$$, the number of zeros is $$$1$$$).

You also have $$$q$$$ changes. For each change you are given the number $$$1 \le x \le n$$$, which means that you must assign an element $$$a_x$$$ the value $$$1$$$.

You have to find the first change after which at least one of $$$m$$$ given segments becomes beautiful, or report that none of them is beautiful after processing all $$$q$$$ changes.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 10^5$$$) — the size of the array $$$a$$$ and the number of segments, respectively.

Then there are $$$m$$$ lines consisting of two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) —the boundaries of the segments.

The next line contains an integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of changes.

The following $$$q$$$ lines each contain a single integer $$$x$$$ ($$$1 \le x \le n$$$) — the index of the array element that needs to be set to $$$1$$$. It is guaranteed that indexes in queries are distinct.

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

## Output Format
For each test case, output one integer  — the minimum change number after which at least one of the segments will be beautiful, or $$$-1$$$ if none of the segments will be beautiful.

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

## Note
In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $$$[1; 5]$$$ there will be 3 ones and only 2 zeros, so the answer is 3.

In the second case, there won't be any beautiful segments.

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 have two vessels with water. The first vessel contains $$$a$$$ grams of water, and the second vessel contains $$$b$$$ grams of water. Both vessels are very large and can hold any amount of water.

You also have an empty cup that can hold up to $$$c$$$ grams of water.

In one move, you can scoop up to $$$c$$$ grams of water from any vessel and pour it into the other vessel. Note that the mass of water poured in one move does not have to be an integer.

What is the minimum number of moves required to make the masses of water in the vessels equal? Note that you cannot perform any actions other than the described moves.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

Each test case consists of a single line containing three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b, c \le 100$$$) — the mass of water in the vessels and the capacity of the cup, respectively.

## Output Format
For each test case, output a single number — the minimum number of moves required to make the masses of water in the vessels equal. It can be shown, that it is always possible.

## Examples
```input
6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3
```
```output
1
3
0
1
50
16
```

## Note
In the first test case, only one move is enough: if we pour $$$2$$$ grams of water from the second vessel into the first one, both vessels will contain $$$5$$$ grams of water.

In the second example test case, three moves are enough:

- Pour $$$3$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$17 - 3 = 14$$$ grams of water, and the second vessel will contain $$$4 + 3 = 7$$$ grams.
- Pour $$$2$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$14 - 2 = 12$$$ grams of water, and the second vessel will contain $$$7 + 2 = 9$$$ grams.
- Finally, pour $$$1.5$$$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $$$12 - 1.5 = 10.5$$$ grams of water, and the second vessel will contain $$$9 + 1.5 = 10.5$$$ grams.

Note that this is not the only way to equalize the vessels in $$$3$$$ moves, but there is no way to do it in $$$2$$$ moves.

In the third example test case, the vessels initially contain the same amount of water, so no moves are needed. The answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$l \le r$$$. You need to find positive integers $$$a$$$ and $$$b$$$ such that the following conditions are simultaneously satisfied:

- $$$l \le a + b \le r$$$
- $$$\gcd(a, b) \neq 1$$$

or report that they do not exist.

$$$\gcd(a, b)$$$ denotes the greatest common divisor of numbers $$$a$$$ and $$$b$$$. For example, $$$\gcd(6, 9) = 3$$$, $$$\gcd(8, 9) = 1$$$, $$$\gcd(4, 2) = 2$$$.

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

Then the descriptions of the test cases follow.

The only line of the description of each test case contains $$$2$$$ integers $$$l, r$$$ ($$$1 \le l \le r \le 10^7$$$).

## Output Format
For each test case, output the integers $$$a, b$$$ that satisfy all the conditions on a separate line. If there is no answer, instead output a single number $$$-1$$$.

If there are multiple answers, you can output any of them.

## Examples
```input
11
11 15
1 3
18 19
41 43
777 777
8000000 10000000
2000 2023
1791791 1791791
1 4
2 3
9840769 9840769
```
```output
6 9
-1
14 4
36 6
111 666
4000000 5000000 
2009 7
-1
2 2
-1
6274 9834495
```

## Note
In the first test case, $$$11 \le 6 + 9 \le 15$$$, $$$\gcd(6, 9) = 3$$$, and all conditions are satisfied. Note that this is not the only possible answer, for example, $$$\{4, 10\}, \{5, 10\}, \{6, 6\}$$$ are also valid answers for this test case.

In the second test case, the only pairs $$$\{a, b\}$$$ that satisfy the condition $$$1 \le a + b \le 3$$$ are $$$\{1, 1\}, \{1, 2\}, \{2, 1\}$$$, but in each of these pairs $$$\gcd(a, b)$$$ equals $$$1$$$, so there is no answer.

In the third sample test, $$$\gcd(14, 4) = 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
Given an array $$$a$$$ of $$$n$$$ positive integers. You need to perform the following operation exactly once:

- Choose $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and replace the subarray $$$a[l \ldots r]$$$ with the single element: the product of all elements in the subarray $$$(a_l \cdot \ldots \cdot a_r)$$$.

For example, if an operation with parameters $$$l = 2, r = 4$$$ is applied to the array $$$[5, 4, 3, 2, 1]$$$, the array will turn into $$$[5, 24, 1]$$$.

Your task is to maximize the sum of the array after applying this operation. Find the optimal subarray to apply this operation.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains a single number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case, output $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the boundaries of the subarray to be replaced with the product.

If there are multiple solutions, output any of them.

## Examples
```input
9
4
1 3 1 3
4
1 1 2 3
5
1 1 1 1 1
5
10 1 10 1 10
1
1
2
2 2
3
2 1 2
4
2 1 1 3
6
2 1 2 1 1 3
```
```output
2 4
3 4
1 1
1 5
1 1
1 2
2 2
4 4
1 6
```

## Note
In the first test case, after applying the operation with parameters $$$l = 2, r = 4$$$, the array $$$[1, 3, 1, 3]$$$ turns into $$$[1, 9]$$$, with a sum equal to $$$10$$$. It is easy to see that by replacing any other segment with a product, the sum will be less than $$$10$$$.

In the second test case, after applying the operation with parameters $$$l = 3, r = 4$$$, the array $$$[1, 1, 2, 3]$$$ turns into $$$[1, 1, 6]$$$, with a sum equal to $$$8$$$. It is easy to see that by replacing any other segment with a product, the sum will be less than $$$8$$$.

In the third test case, it will be optimal to choose any operation with $$$l = r$$$, then the sum of the array will remain $$$5$$$, and when applying any other operation, the sum of the array will decrease.

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 four-digit pin code consisting of digits from $$$0$$$ to $$$9$$$ that needs to be entered. Initially, the cursor points to the digit $$$1$$$. In one second, you can perform exactly one of the following two actions:

- Press the cursor to display the current digit,
- Move the cursor to any adjacent digit.

The image above shows the device you are using to enter the pin code. For example, for the digit $$$5$$$, the adjacent digits are $$$4$$$ and $$$6$$$, and for the digit $$$0$$$, there is only one adjacent digit, $$$9$$$.

Determine the minimum number of seconds required to enter the given four-digit pin code.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) - the number of the test cases. This is followed by their description.

The single line of each test case describes the pin code as a string of length $$$4$$$, consisting of digits from $$$0$$$ to $$$9$$$.

## Output Format
For each test case, output the minimum number of seconds required to enter the given pin code.

## Examples
```input
10
1111
1236
1010
1920
9273
0000
7492
8543
0294
8361
```
```output
4
9
31
27
28
13
25
16
33
24
```

## Note
In the first test case, the cursor needs to be pressed $$$4$$$ times.

In the second test case, it can be done in $$$9$$$ seconds as follows:

- Press the cursor.
- Move the cursor to the digit $$$2$$$.
- Press the cursor.
- Move the cursor to the digit $$$3$$$.
- Press the cursor.
- Move the cursor to the digit $$$4$$$.
- Move the cursor to the digit $$$5$$$.
- Move the cursor to the digit $$$6$$$.
- Press the cursor.

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 an array of integers $$$a_1, a_2, \ldots, a_n$$$. You need to make it non-decreasing with the minimum number of operations. In one operation, you do the following:

- Choose an index $$$1 \leq i \leq n$$$,
- Set $$$a_i = a_i \cdot 2$$$.

An array $$$b_1, b_2, \ldots, b_n$$$ is non-decreasing if $$$b_i \leq b_{i+1}$$$ for all $$$1 \leq i < n$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by their description.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 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 the minimum number of operations needed to make the array non-decreasing.

## Examples
```input
9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1
```
```output
0
1
3
6
10
3
0
2
66
```

## Note
No operations are needed in the first test case.

In the second test case, we need to choose $$$i = 2$$$, after which the array will be $$$[2, 2]$$$.

In the third test case, we can apply the following operations:

- Choose $$$i = 3$$$, after which the array will be $$$[3, 2, 2]$$$,
- Choose $$$i = 3$$$, after which the array will be $$$[3, 2, 4]$$$,
- Choose $$$i = 2$$$, after which the array will be $$$[3, 4, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You had a sequence $$$a_1, a_2, \ldots, a_n$$$ consisting of integers from $$$1$$$ to $$$n$$$, not necessarily distinct. For some unknown reason, you decided to calculate the following characteristic of the sequence:

- Let $$$r_i$$$ ($$$1 \le i \le n$$$) be the smallest $$$j \ge i$$$ such that on the subsegment $$$a_i, a_{i+1}, \ldots, a_j$$$ all distinct numbers from the sequence $$$a$$$ appear. More formally, for any $$$k \in [1, n]$$$, there exists $$$l \in [i, j]$$$ such that $$$a_k = a_l$$$. If such $$$j$$$ does not exist, $$$r_i$$$ is considered to be equal to $$$n+1$$$.
- The characteristic of the sequence $$$a$$$ is defined as the sequence $$$r_1, r_2, \ldots, r_n$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$i \le r_i \le n+1$$$) — the characteristic of the lost sequence $$$a$$$.

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 the following:

- If there is no sequence $$$a$$$ with the characteristic $$$r$$$, print "No".
- Otherwise, print "Yes" on the first line, and on the second line, print any sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) that matches the characteristic $$$r$$$.

## Examples
```input
5
3
2 3 4
5
2 3 5 4 6
1
1
3
1 3 4
8
3 6 6 6 8 9 9 9
```
```output
Yes
1 2 1
No
Yes
1 
No
Yes
1 3 5 3 5 1 1 3
```

## Note
In the first test case, the sequence $$$a = [1, 2, 1]$$$ is suitable. The integers $$$1$$$ and $$$2$$$ appear on the subsegments $$$[1, 2]$$$ and $$$[2, 3]$$$.

In the second test case, it can be proved that there is no suitable sequence $$$a$$$.

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
In a sequence $$$a$$$, whose product was equal to $$$2023$$$, $$$k$$$ numbers were removed, leaving a sequence $$$b$$$ of length $$$n$$$. Given the resulting sequence $$$b$$$, find any suitable sequence $$$a$$$ and output which $$$k$$$ elements were removed from it, or state that such a sequence could not have existed.

Notice that you are not guaranteed that such array exists.

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains two integers $$$n$$$ ($$$1 \le n, k \le 5$$$) — the size of sequence $$$b$$$ and the number of numbers removed from sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$b_1,b_2, \ldots,b_n$$$ ($$$1 \leq b_i \leq 2023$$$) — the remaining sequence. The values of $$$b_i$$$ might not be divisors of $$$2023$$$.

## Output Format
For each test case, output "YES" if the sequence $$$a$$$ exists, and in the following line output $$$k$$$ non-negative integers that were removed from the sequence $$$a$$$. If the sequence $$$a$$$ does not exist, output "NO" in a single line.

You can output the answer in any case (uppercase or lowercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers.

## Examples
```input
7
2 2
5 2
3 1
7 17 7
4 2
1 289 1 1
3 1
7 17 17
1 1
289
1 1
2023
1 3
1
```
```output
NO
NO
YES
7 1
YES
1
YES
7
YES
1
YES
7 17 17
```

## Note
In third test case product is equal to $$$289 \cdot 7 = 2023$$$.

In fourth test case product is already equal to $$$2023$$$.

In seventh test case product is equal to $$$7 \cdot 17 \cdot 17 = 2023$$$.

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
A certain number $$$1 \le x \le 10^9$$$ is chosen. You are given two integers $$$a$$$ and $$$b$$$, which are the two largest divisors of the number $$$x$$$. At the same time, the condition $$$1 \le a < b < x$$$ is satisfied.

For the given numbers $$$a$$$, $$$b$$$, you need to find the value of $$$x$$$.

$$$^{\dagger}$$$ The number $$$y$$$ is a divisor of the number $$$x$$$ if there is an integer $$$k$$$ such that $$$x = y \cdot k$$$.

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

The only line of each test cases contains two integers $$$a$$$, $$$b$$$ ($$$1 \le a < b \le 10^9$$$).

It is guaranteed that $$$a$$$, $$$b$$$ are the two largest divisors for some number $$$1 \le x \le 10^9$$$.

## Output Format
For each test case, output the number $$$x$$$, such that $$$a$$$ and $$$b$$$ are the two largest divisors of the number $$$x$$$.

If there are several answers, print any of them.

## Examples
```input
8
2 3
1 2
3 11
1 5
5 10
4 6
3 9
250000000 500000000
```
```output
6
4
33
25
20
12
27
1000000000
```

## Note
For the first test case, all divisors less than $$$6$$$ are equal to $$$[1, 2, 3]$$$, among them the two largest will be $$$2$$$ and $$$3$$$.

For the third test case, all divisors less than $$$33$$$ are equal to $$$[1, 3, 11]$$$, among them the two largest will be $$$3$$$ and $$$11$$$.

For the fifth test case, all divisors less than $$$20$$$ are equal to $$$[1, 2, 4, 5, 10]$$$, among them the two largest will be $$$5$$$ and $$$10$$$.

For the sixth test case, all divisors less than $$$12$$$ are equal to $$$[1, 2, 3, 4, 6]$$$, among them the two largest will be $$$4$$$ and $$$6$$$.

Now solve the problem and return the code.