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: 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 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 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 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
An array $$$b$$$ of length $$$k$$$ is called good if its arithmetic mean is equal to $$$1$$$. More formally, if $$$$$$\frac{b_1 + \cdots + b_k}{k}=1.$$$$$$

Note that the value $$$\frac{b_1+\cdots+b_k}{k}$$$ is not rounded up or down. For example, the array $$$[1,1,1,2]$$$ has an arithmetic mean of $$$1.25$$$, which is not equal to $$$1$$$.

You are given an integer array $$$a$$$ of length $$$n$$$. In an operation, you can append a non-negative integer to the end of the array. What's the minimum number of operations required to make the array good?

We have a proof that it is always possible with finitely many operations.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the initial array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$-10^4\leq a_i \leq 10^4$$$), the elements of the array.

## Output Format
For each test case, output a single integer — the minimum number of non-negative integers you have to append to the array so that the arithmetic mean of the array will be exactly $$$1$$$.

## Examples
```input
4
3
1 1 1
2
1 2
4
8 4 6 2
1
-2
```
```output
0
1
16
1
```

## Note
In the first test case, we don't need to add any element because the arithmetic mean of the array is already $$$1$$$, so the answer is $$$0$$$.

In the second test case, the arithmetic mean is not $$$1$$$ initially so we need to add at least one more number. If we add $$$0$$$ then the arithmetic mean of the whole array becomes $$$1$$$, so the answer is $$$1$$$.

In the third test case, the minimum number of elements that need to be added is $$$16$$$ since only non-negative integers can be added.

In the fourth test case, we can add a single integer $$$4$$$. The arithmetic mean becomes $$$\frac{-2+4}{2}$$$ which is equal to $$$1$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Riley is a very bad boy, but at the same time, he is a yo-yo master. So, he decided to use his yo-yo skills to annoy his friend Anton.

Anton's room can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Let $$$(i, j)$$$ denote the cell in row $$$i$$$ and column $$$j$$$. Anton is currently standing at position $$$(i, j)$$$ in his room. To annoy Anton, Riley decided to throw exactly two yo-yos in cells of the room (they can be in the same cell).

Because Anton doesn't like yo-yos thrown on the floor, he has to pick up both of them and return back to the initial position. The distance travelled by Anton is the shortest path that goes through the positions of both yo-yos and returns back to $$$(i, j)$$$ by travelling only to adjacent by side cells. That is, if he is in cell $$$(x, y)$$$ then he can travel to the cells $$$(x + 1, y)$$$, $$$(x - 1, y)$$$, $$$(x, y + 1)$$$ and $$$(x, y - 1)$$$ in one step (if a cell with those coordinates exists).

Riley is wondering where he should throw these two yo-yos so that the distance travelled by Anton is maximized. But because he is very busy, he asked you to tell him.

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

The only line of each test case contains four integers $$$n$$$, $$$m$$$, $$$i$$$, $$$j$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1\le i\le n$$$, $$$1\le j\le m$$$) — the dimensions of the room, and the cell at which Anton is currently standing.

## Output Format
For each test case, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1, x_2 \leq n$$$, $$$1\le y_1, y_2\le m$$$) — the coordinates of where the two yo-yos should be thrown. They will be thrown at coordinates $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$.

If there are multiple answers, you may print any.

## Examples
```input
7
2 3 1 1
4 4 1 2
3 5 2 2
5 1 2 1
3 1 3 1
1 1 1 1
1000000000 1000000000 1000000000 50
```
```output
1 2 2 3
4 1 4 4
3 1 1 5
5 1 1 1
1 1 2 1
1 1 1 1
50 1 1 1000000000
```

## Note
Here is a visualization of the first 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 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
Alice and Bob are playing a game.

They start with a positive integer $$$n$$$ and take alternating turns doing operations on it. Each turn a player can subtract from $$$n$$$ one of its divisors that isn't $$$1$$$ or $$$n$$$. The player who cannot make a move on his/her turn loses. Alice always moves first.

Note that they subtract a divisor of the current number in each turn.

You are asked to find out who will win the game if both players play optimally.

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

Each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the initial number.

## Output Format
For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

## Examples
```input
4
1
4
12
69
```
```output
Bob
Alice
Alice
Bob
```

## Note
In the first test case, the game ends immediately because Alice cannot make a move.

In the second test case, Alice can subtract $$$2$$$ making $$$n = 2$$$, then Bob cannot make a move so Alice wins.

In the third test case, Alice can subtract $$$3$$$ so that $$$n = 9$$$. Bob's only move is to subtract $$$3$$$ and make $$$n = 6$$$. Now, Alice can subtract $$$3$$$ again and $$$n = 3$$$. Then Bob cannot make a move, so Alice wins.

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
This is the easy version of the problem. The only difference is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

You have a string $$$s$$$, and you can do two types of operations on it:

- Delete the last character of the string.
- Duplicate the string: $$$s:=s+s$$$, where $$$+$$$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $$$k$$$ that can be obtained by doing these operations on string $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a\ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5000$$$) — the length of the original string $$$s$$$ and the length of the desired string.

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

## Output Format
Print the lexicographically smallest string of length $$$k$$$ that can be obtained by doing the operations on string $$$s$$$.

## Examples
```input
8 16
dbcadabc
```
```output
dbcadabcdbcadabc
```
-----
```input
4 5
abcd
```
```output
aaaaa
```

## Note
In the first test, it is optimal to make one duplication: "dbcadabc" $$$\to$$$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $$$3$$$ characters, then duplicate the string $$$3$$$ times, then delete the last $$$3$$$ characters to make the string have length $$$k$$$.

"abcd" $$$\to$$$ "abc" $$$\to$$$ "ab" $$$\to$$$ "a" $$$\to$$$ "aa" $$$\to$$$ "aaaa" $$$\to$$$ "aaaaaaaa" $$$\to$$$ "aaaaaaa" $$$\to$$$ "aaaaaa" $$$\to$$$ "aaaaa".

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
This is the hard version of the problem. The only difference is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

You have a string $$$s$$$, and you can do two types of operations on it:

- Delete the last character of the string.
- Duplicate the string: $$$s:=s+s$$$, where $$$+$$$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $$$k$$$ that can be obtained by doing these operations on string $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a\ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5\cdot 10^5$$$) — the length of the original string $$$s$$$ and the length of the desired string.

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

## Output Format
Print the lexicographically smallest string of length $$$k$$$ that can be obtained by doing the operations on string $$$s$$$.

## Examples
```input
8 16
dbcadabc
```
```output
dbcadabcdbcadabc
```
-----
```input
4 5
abcd
```
```output
aaaaa
```

## Note
In the first test, it is optimal to make one duplication: "dbcadabc" $$$\to$$$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $$$3$$$ characters, then duplicate the string $$$3$$$ times, then delete the last $$$3$$$ characters to make the string have length $$$k$$$.

"abcd" $$$\to$$$ "abc" $$$\to$$$ "ab" $$$\to$$$ "a" $$$\to$$$ "aa" $$$\to$$$ "aaaa" $$$\to$$$ "aaaaaaaa" $$$\to$$$ "aaaaaaa" $$$\to$$$ "aaaaaa" $$$\to$$$ "aaaaa".

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