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
Now you get Baby Ehab's first words: "Given an integer $$$n$$$, find the longest subsequence of $$$[1,2, \ldots, n-1]$$$ whose product is $$$1$$$ modulo $$$n$$$." Please solve the problem.

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly all) elements. The product of an empty subsequence is equal to $$$1$$$.

## Input Format
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

## Output Format
The first line should contain a single integer, the length of the longest subsequence.

The second line should contain the elements of the subsequence, in increasing order.

If there are multiple solutions, you can print any.

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

## Note
In the first example, the product of the elements is $$$6$$$ which is congruent to $$$1$$$ modulo $$$5$$$. The only longer subsequence is $$$[1,2,3,4]$$$. Its product is $$$24$$$ which is congruent to $$$4$$$ modulo $$$5$$$. Hence, the answer is $$$[1,2,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Nastia has $$$2$$$ positive integers $$$A$$$ and $$$B$$$. She defines that:

- The integer is good if it is divisible by $$$A \cdot B$$$;
- Otherwise, the integer is nearly good, if it is divisible by $$$A$$$.

For example, if $$$A = 6$$$ and $$$B = 4$$$, the integers $$$24$$$ and $$$72$$$ are good, the integers $$$6$$$, $$$660$$$ and $$$12$$$ are nearly good, the integers $$$16$$$, $$$7$$$ are neither good nor nearly good.

Find $$$3$$$ different positive integers $$$x$$$, $$$y$$$, and $$$z$$$ such that exactly one of them is good and the other $$$2$$$ are nearly good, and $$$x + y = z$$$.

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

The first line of each test case contains two integers $$$A$$$ and $$$B$$$ ($$$1 \le A \le 10^6$$$, $$$1 \le B \le 10^6$$$) — numbers that Nastia has.

## Output Format
For each test case print:

- "YES" and $$$3$$$ different positive integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le x, y, z \le 10^{18}$$$) such that exactly one of them is good and the other $$$2$$$ are nearly good, and $$$x + y = z$$$.
- "NO" if no answer exists.

If there are multiple answers, print any.

## Examples
```input
3
5 3
13 2
7 11
```
```output
YES
10 50 60
YES
169 39 208
YES
28 154 182
```

## Note
In the first test case: $$$60$$$ — good number; $$$10$$$ and $$$50$$$ — nearly good numbers.

In the second test case: $$$208$$$ — good number; $$$169$$$ and $$$39$$$ — nearly good numbers.

In the third test case: $$$154$$$ — good number; $$$28$$$ and $$$182$$$ — nearly good numbers.

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
Nastia has received an array of $$$n$$$ positive integers as a gift.

She calls such an array $$$a$$$ good that for all $$$i$$$ ($$$2 \le i \le n$$$) takes place $$$gcd(a_{i - 1}, a_{i}) = 1$$$, where $$$gcd(u, v)$$$ denotes the greatest common divisor (GCD) of integers $$$u$$$ and $$$v$$$.

You can perform the operation: select two different indices $$$i, j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$) and two integers $$$x, y$$$ ($$$1 \le x, y \le 2 \cdot 10^9$$$) so that $$$\min{(a_i, a_j)} = \min{(x, y)}$$$. Then change $$$a_i$$$ to $$$x$$$ and $$$a_j$$$ to $$$y$$$.

The girl asks you to make the array good using at most $$$n$$$ operations.

It can be proven that this is always possible.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — the array which Nastia has received as a gift.

It's guaranteed that the sum of $$$n$$$ in one test doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each of $$$t$$$ test cases print a single integer $$$k$$$ ($$$0 \le k \le n$$$) — the number of operations. You don't need to minimize this number.

In each of the next $$$k$$$ lines print $$$4$$$ integers $$$i$$$, $$$j$$$, $$$x$$$, $$$y$$$ ($$$1 \le i \neq j \le n$$$, $$$1 \le x, y \le 2 \cdot 10^9$$$) so that $$$\min{(a_i, a_j)} = \min{(x, y)}$$$ — in this manner you replace $$$a_i$$$ with $$$x$$$ and $$$a_j$$$ with $$$y$$$.

If there are multiple answers, print any.

## Examples
```input
2
5
9 6 3 11 15
3
7 5 13
```
```output
2
1 5 11 9
2 5 7 6
0
```

## Note
Consider the first test case.

Initially $$$a = [9, 6, 3, 11, 15]$$$.

In the first operation replace $$$a_1$$$ with $$$11$$$ and $$$a_5$$$ with $$$9$$$. It's valid, because $$$\min{(a_1, a_5)} = \min{(11, 9)} = 9$$$.

After this $$$a = [11, 6, 3, 11, 9]$$$.

In the second operation replace $$$a_2$$$ with $$$7$$$ and $$$a_5$$$ with $$$6$$$. It's valid, because $$$\min{(a_2, a_5)} = \min{(7, 6)} = 6$$$.

After this $$$a = [11, 7, 3, 11, 6]$$$ — a good array.

In the second test case, the initial array is already good.

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 like numbers, don't you? Nastia has a lot of numbers and she wants to share them with you! Isn't it amazing?

Let $$$a_i$$$ be how many numbers $$$i$$$ ($$$1 \le i \le k$$$) you have.

An $$$n \times n$$$ matrix is called beautiful if it contains all the numbers you have, and for each $$$2 \times 2$$$ submatrix of the original matrix is satisfied:

1. The number of occupied cells doesn't exceed $$$3$$$;
2. The numbers on each diagonal are distinct.

Make a beautiful matrix of minimum size.

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

The first line of each test case contains $$$2$$$ integers $$$m$$$ and $$$k$$$ ($$$1 \le m, k \le 10^5$$$) — how many numbers Nastia gave you and the length of the array $$$a$$$, respectively.

The second line of each test case contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_{k}$$$ ($$$0 \le a_i \le m$$$, $$$a_1 + a_2 + \ldots + a_{k} = m$$$), where $$$a_i$$$ is how many numbers $$$i$$$ you have.

It's guaranteed that the sum of $$$m$$$ and $$$k$$$ in one test doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each $$$t$$$ test case print a single integer $$$n$$$ — the size of the beautiful matrix.

In the next $$$n$$$ lines print $$$n$$$ integers $$$b_{i, j}$$$ ($$$0 \le b_{i, j} \le k$$$; if position is empty, print $$$b_{i, j} = 0$$$) — the beautiful matrix $$$b$$$ you made up.

## Examples
```input
2
3 4
2 0 0 1
15 4
2 4 8 1
```
```output
2
4 1
0 1
5
3 0 0 2 2
3 2 3 3 0
0 1 0 4 0
3 0 0 0 0
2 1 3 3 3
```

## Note
Note that $$$0$$$ in this problem represents a blank, not a number.

Examples of possible answers for the first test case:

$$$\begin{array}{cc} 1 & 1 \\ 4 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\ 1 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\ 1 & 1 \\ \end{array}$$$

Examples of not beautiful matrices for the first test case:

$$$\begin{array}{cc} 1 & 0 \\ 4 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\ 7 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\ 4 & 0 \\ \end{array}$$$

The example of the not beautiful matrix for the second test case:

$$$\begin{array}{cc} 3 & 4 & 0 & 2 & 2 \\ 3 & 2 & 3 & 3 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 3 & 3 & 3 \\ \end{array}$$$

Everything is okay, except the left-top submatrix contains $$$4$$$ numbers.

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 permutation $$$a$$$ consisting of $$$n$$$ numbers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array in which each element from $$$1$$$ to $$$n$$$ occurs exactly once).

You can perform the following operation: choose some subarray (contiguous subsegment) of $$$a$$$ and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array.

For example, if $$$a = [2, 1, 4, 5, 3]$$$ and we want to apply the operation to the subarray $$$a[2, 4]$$$ (the subarray containing all elements from the $$$2$$$-nd to the $$$4$$$-th), then after the operation, the array can become $$$a = [2, 5, 1, 4, 3]$$$ or, for example, $$$a = [2, 1, 5, 4, 3]$$$.

Your task is to calculate the minimum number of operations described above to sort the permutation $$$a$$$ in ascending order.

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

The first line of the test case contains a single integer $$$n$$$ ($$$3 \le n \le 50$$$) — the number of elements in the permutation.

The second line of the test case contains $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ — the given permutation $$$a$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations described above to sort the array $$$a$$$ in ascending order.

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

## Note
In the explanations, $$$a[i, j]$$$ defines the subarray of $$$a$$$ that starts from the $$$i$$$-th element and ends with the $$$j$$$-th element.

In the first test case of the example, you can select the subarray $$$a[2, 3]$$$ and swap the elements in it.

In the second test case of the example, the permutation is already sorted, so you don't need to apply any operations.

In the third test case of the example, you can select the subarray $$$a[3, 5]$$$ and reorder the elements in it so $$$a$$$ becomes $$$[2, 1, 3, 4, 5]$$$, and then select the subarray $$$a[1, 2]$$$ and swap the elements in it, so $$$a$$$ becomes $$$[1, 2, 3, 4, 5]$$$.

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
There are $$$n$$$ people participating in some contest, they start participating in $$$x$$$ minutes intervals. That means the first participant starts at time $$$0$$$, the second participant starts at time $$$x$$$, the third — at time $$$2 \cdot x$$$, and so on.

Duration of contest is $$$t$$$ minutes for each participant, so the first participant finishes the contest at time $$$t$$$, the second — at time $$$t + x$$$, and so on. When a participant finishes the contest, their dissatisfaction equals to the number of participants that started the contest (or starting it now), but haven't yet finished it.

Determine the sum of dissatisfaction of all participants.

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

Each of the next $$$k$$$ lines contains three integers $$$n$$$, $$$x$$$, $$$t$$$ ($$$1 \le n, x, t \le 2 \cdot 10^9$$$) — the number of participants, the start interval and the contest duration.

## Output Format
Print $$$k$$$ lines, in the $$$i$$$-th line print the total dissatisfaction of participants in the $$$i$$$-th test case.

## Examples
```input
4
4 2 5
3 1 2
3 3 10
2000000000 1 2000000000
```
```output
5
3
3
1999999999000000000
```

## Note
In the first example the first participant starts at $$$0$$$ and finishes at time $$$5$$$. By that time the second and the third participants start, so the dissatisfaction of the first participant is $$$2$$$.

The second participant starts at time $$$2$$$ and finishes at time $$$7$$$. By that time the third the fourth participants start, so the dissatisfaction of the second participant is $$$2$$$.

The third participant starts at $$$4$$$ and finishes at $$$9$$$. By that time the fourth participant starts, so the dissatisfaction of the third participant is $$$1$$$.

The fourth participant starts at $$$6$$$ and finishes at $$$11$$$. By time $$$11$$$ everyone finishes the contest, so the dissatisfaction of the fourth participant is $$$0$$$.

In the second example the first participant starts at $$$0$$$ and finishes at time $$$2$$$. By that time the second participants starts, and the third starts at exactly time $$$2$$$. So the dissatisfaction of the first participant is $$$2$$$.

The second participant starts at time $$$1$$$ and finishes at time $$$3$$$. At that time the third participant is solving the contest.

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
Petya once wrote a sad love song and shared it to Vasya. The song is a string consisting of lowercase English letters. Vasya made up $$$q$$$ questions about this song. Each question is about a subsegment of the song starting from the $$$l$$$-th letter to the $$$r$$$-th letter. Vasya considers a substring made up from characters on this segment and repeats each letter in the subsegment $$$k$$$ times, where $$$k$$$ is the index of the corresponding letter in the alphabet. For example, if the question is about the substring "abbcb", then Vasya repeats letter 'a' once, each of the letters 'b' twice, letter 'c" three times, so that the resulting string is "abbbbcccbb", its length is $$$10$$$. Vasya is interested about the length of the resulting string.

Help Petya find the length of each string obtained by Vasya.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n\leq 100\,000$$$, $$$1\leq q \leq 100\,000$$$) — the length of the song and the number of questions.

The second line contains one string $$$s$$$ — the song, consisting of $$$n$$$ lowercase letters of English letters.

Vasya's questions are contained in the next $$$q$$$ lines. Each line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — the bounds of the question.

## Output Format
Print $$$q$$$ lines: for each question print the length of the string obtained by Vasya.

## Examples
```input
7 3
abacaba
1 3
2 5
1 7
```
```output
4
7
11
```
-----
```input
7 4
abbabaa
1 3
5 7
6 6
2 4
```
```output
5
4
1
5
```
-----
```input
13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9
```
```output
82
125
9
191
62
63
97
```

## Note
In the first example Vasya is interested in three questions. In the first question Vasya considers the substring "aba", that transforms to "abba", so the answer is equal to $$$4$$$. In the second question Vasya considers "baca", that transforms to "bbaccca", so the answer is $$$7$$$. In the third question Vasya considers the string "abacaba",that transforms to "abbacccabba" of length $$$11$$$.

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

# Problem
The Alice's computer is broken, so she can't play her favorite card game now. To help Alice, Bob wants to answer $$$n$$$ her questions.

Initially, Bob holds one card with number $$$0$$$ in the left hand and one in the right hand. In the $$$i$$$-th question, Alice asks Bob to replace a card in the left or right hand with a card with number $$$k_i$$$ (Bob chooses which of two cards he changes, Bob must replace exactly one card).

After this action, Alice wants the numbers on the left and right cards to belong to given segments (segments for left and right cards can be different). Formally, let the number on the left card be $$$x$$$, and on the right card be $$$y$$$. Then after the $$$i$$$-th swap the following conditions must be satisfied: $$$a_{l, i} \le x \le b_{l, i}$$$, and $$$a_{r, i} \le y \le b_{r,i}$$$.

Please determine if Bob can answer all requests. If it is possible, find a way to do it.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100\,000$$$, $$$2 \le m \le 10^9$$$) — the number of questions and the maximum possible value on the card.

Then $$$n$$$ queries are described. Every description contains 3 lines.

The first line of the description of the $$$i$$$-th query contains a single integer $$$k_i$$$ ($$$0 \le k_i \le m$$$) — the number on a new card.

The second line of the description of the $$$i$$$-th query contains two integers $$$a_{l, i}$$$ and $$$b_{l, i}$$$ ($$$0 \le a_{l, i} \le b_{l, i} \le m$$$) — the minimum and maximum values of the card at the left hand after the replacement.

The third line of the description of the $$$i$$$-th query contains two integers $$$a_{r, i}$$$ and $$$b_{r,i}$$$ ($$$0 \le a_{r, i} \le b_{r,i} \le m$$$) — the minimum and maximum values of the card at the right hand after the replacement.

## Output Format
At the first line, print "Yes", if Bob can answer all queries, and "No" otherwise.

If Bob can answer all $$$n$$$ queries, then at the second line print $$$n$$$ numbers: a way to satisfy all requirements. If in $$$i$$$-th query Bob needs to replace the card in the left hand, print $$$0$$$, otherwise print $$$1$$$. If there are multiple answers, print any.

## Examples
```input
2 10
3
0 3
0 2
2
0 4
0 2
```
```output
Yes
0 1
```
-----
```input
2 10
3
0 3
0 2
2
3 4
0 1
```
```output
No
```
-----
```input
5 10
3
0 3
0 3
7
4 7
1 3
2
2 3
3 7
8
1 8
1 8
6
1 6
7 10
```
```output
Yes
1 0 0 1 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: 256.0 MB

# Problem
Vasya has an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Vasya thinks that all numbers in his array are strange for some reason. To calculate how strange the $$$i$$$-th number is, Vasya created the following algorithm.

He chooses a subsegment $$$a_l, a_{l+1}, \ldots, a_r$$$, such that $$$1 \le l \le i \le r \le n$$$, sort its elements in increasing order in his head (he can arrange equal elements arbitrary). After that he finds the center of the segment. The center of a segment is the element at position $$$(l + r) / 2$$$, if the length of the segment is odd, and at position $$$(l + r + 1) / 2$$$ otherwise. Now Vasya finds the element that was at position $$$i$$$ before the sorting, and calculates the distance between its current position and the center of the subsegment (the distance between the elements with indices $$$j$$$ and $$$k$$$ is $$$|j - k|$$$).

The strangeness of the number at position $$$i$$$ is the maximum distance among all suitable choices of $$$l$$$ and $$$r$$$.

Vasya wants to calculate the strangeness of each number in his array. Help him to do it.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — Vasya's array.

## Output Format
Print a single line with $$$n$$$ numbers. The $$$i$$$-th of them must be equal to the strangeness of the $$$i$$$-th element of the array.

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

## Note
In the first example:

1. For the first position we choose the segment from $$$1$$$ to $$$5$$$. After sorting, it looks like $$$[1, 2, 3, 4, 5]$$$, the center is $$$3$$$. The distance from the center to $$$5$$$ is $$$2$$$.
2. For the second position we choose the segment from $$$2$$$ to $$$4$$$.
3. For the third position we choose the segment from $$$3$$$ to $$$5$$$.
4. For the fourth position we choose the segment from $$$1$$$ to $$$4$$$. After sorting, it looks like $$$[2, 3, 4, 5]$$$, the center is $$$4$$$. The distance from the center to $$$2$$$ is $$$2$$$.
5. For the fifth position we choose the segment from $$$1$$$ to $$$5$$$.

Now solve the problem and return the code.