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: 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 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
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 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 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 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
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 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
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 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
Filip has a row of cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal:

- $$$1$$$ — place water in an empty cell.
- $$$2$$$ — remove water from a cell and place it in any other empty cell.

If at some moment cell $$$i$$$ ($$$2 \le i \le n-1$$$) is empty and both cells $$$i-1$$$ and $$$i+1$$$ contains water, then it becomes filled with water.

Find the minimum number of times he needs to perform action $$$1$$$ in order to fill all empty cells with water.

Note that you don't need to minimize the use of action $$$2$$$. Note that blocked cells neither contain water nor can Filip place water in them.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells.

The next line contains a string $$$s$$$ of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is '.' if the cell $$$i$$$ is empty and '#' if cell $$$i$$$ is blocked.

## Output Format
For each test case, output a single number — the minimal amount of actions $$$1$$$ needed to fill all empty cells with water.

## Examples
```input
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#
```
```output
2
2
5
0
2
```

## Note
Test Case 1

In the first test case, Filip can put water in cells $$$1$$$ and $$$3$$$. As cell $$$2$$$ is between $$$2$$$ cells with water, it gets filled with water too.

Test Case 2

In the second case, he can put water sources in cells $$$3$$$ and $$$5$$$. That results in cell $$$4$$$ getting filled with water. Then he will remove water from cell $$$5$$$ and place it into cell $$$6$$$. As cell $$$5$$$'s neighbors, cell $$$4$$$ and cell $$$6$$$, have water in them, cell $$$5$$$ also gets filled with water. You can see the illustration of this case below.

Operations in the second test case. White cells are empty, grey ones are blocked, and blue ones are water.

Test Case 3

In the third case, he can put water in all the empty cells. That requires $$$5$$$ actions of type $$$1$$$.

Test Case 4

In the fourth case, there are no empty cells. Therefore, he does not have to put any water in them.

Test Case 5

In the fifth test case, there exists a sequence of actions that requires only $$$2$$$ type $$$1$$$ actions.

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
Let $$$a$$$, $$$b$$$, and $$$c$$$ be integers. We define function $$$f(a, b, c)$$$ as follows:

Order the numbers $$$a$$$, $$$b$$$, $$$c$$$ in such a way that $$$a \le b \le c$$$. Then return $$$\gcd(a, b)$$$, where $$$\gcd(a, b)$$$ denotes the greatest common divisor (GCD) of integers $$$a$$$ and $$$b$$$.

So basically, we take the $$$\gcd$$$ of the $$$2$$$ smaller values and ignore the biggest one.

You are given an array $$$a$$$ of $$$n$$$ elements. Compute the sum of $$$f(a_i, a_j, a_k)$$$ for each $$$i$$$, $$$j$$$, $$$k$$$, such that $$$1 \le i < j < k \le n$$$.

More formally, compute $$$$$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).$$$$$$

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — 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^5$$$) — elements of the array $$$a$$$.

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

## Output Format
For each test case, output a single number — the sum from the problem statement.

## Examples
```input
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16
```
```output
24
203
```

## Note
In the first test case, the values of $$$f$$$ are as follows:

- $$$i=1$$$, $$$j=2$$$, $$$k=3$$$, $$$f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$$$;
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$$$.

In the second test case, there are $$$56$$$ ways to choose values of $$$i$$$, $$$j$$$, $$$k$$$. The sum over all $$$f(a_i,a_j,a_k)$$$ is $$$203$$$.

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