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$$$ of $$$n$$$ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as $$$\operatorname{DIFF}(a) - \operatorname{MEX}(a)$$$, where $$$\operatorname{MEX}$$$ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $$$\operatorname{DIFF}$$$ is the number of different numbers in the array.

For example, $$$\operatorname{MEX}(\{1, 2, 3\}) = 0$$$, $$$\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

You should find the minimal cost of the array $$$a$$$ if you are allowed to make at most $$$k$$$ operations.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$) — the length of the array $$$a$$$ and the number of operations that you are allowed to make.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

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

## Output Format
For each test case output a single integer — minimal cost that it is possible to get making at most $$$k$$$ operations.

## Examples
```input
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
```
```output
0
1
2
0
```

## Note
In the first test case no operations are needed to minimize the value of $$$\operatorname{DIFF} - \operatorname{MEX}$$$.

In the second test case it is possible to replace $$$5$$$ by $$$1$$$. After that the array $$$a$$$ is $$$[0,\, 2,\, 4,\, 1]$$$, $$$\operatorname{DIFF} = 4$$$, $$$\operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3$$$, so the answer is $$$1$$$.

In the third test case one possible array $$$a$$$ is $$$[4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]$$$, $$$\operatorname{DIFF} = 5$$$, $$$\operatorname{MEX} = 3$$$.

In the fourth test case one possible array $$$a$$$ is $$$[1,\, 2,\, 3,\, 0,\, 0,\, 0]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's consider Euclid's algorithm for finding the greatest common divisor, where $$$t$$$ is a list:

There is an array $$$p$$$ of pairs of positive integers that are not greater than $$$m$$$. Initially, the list $$$t$$$ is empty. Then the function is run on each pair in $$$p$$$. After that the list $$$t$$$ is shuffled and given to you.

You have to find an array $$$p$$$ of any size not greater than $$$2 \cdot 10^4$$$ that produces the given list $$$t$$$, or tell that no such array exists.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$t$$$ and the constraint for integers in pairs.

The second line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le m$$$) — the elements of the array $$$t$$$.

## Output Format
- If the answer does not exist, output $$$-1$$$.
- If the answer exists, in the first line output $$$k$$$ ($$$1 \le k \le 2 \cdot 10^4$$$) — the size of your array $$$p$$$, i. e. the number of pairs in the answer. The $$$i$$$-th of the next $$$k$$$ lines should contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$) — the $$$i$$$-th pair in $$$p$$$.

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

## Examples
```input
7 20
1 8 1 6 3 2 3
```
```output
3
19 11
15 9
3 7
```
-----
```input
2 10
7 1
```
```output
-1
```
-----
```input
2 15
1 7
```
```output
1
15 8
```
-----
```input
1 1000000000
845063470
```
```output
-1
```

## Note
In the first sample let's consider the array $$$t$$$ for each pair:

- $$$(19,\, 11)$$$: $$$t = [8, 3, 2, 1]$$$;
- $$$(15,\, 9)$$$: $$$t = [6, 3]$$$;
- $$$(3,\, 7)$$$: $$$t = [1]$$$.

So in total $$$t = [8, 3, 2, 1, 6, 3, 1]$$$, which is the same as the input $$$t$$$ (up to a permutation).

In the second test case it is impossible to find such array $$$p$$$ of pairs that all integers are not greater than $$$10$$$ and $$$t = [7, 1]$$$

In the third test case for the pair $$$(15,\, 8)$$$ array $$$t$$$ will be $$$[7, 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 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 binary string $$$s$$$. You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of $$$s$$$ should be in exactly one substring.

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

Each test case contains a binary string $$$s$$$ ($$$1 \le |s| \le 10^6$$$).

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case output the answer to the problem as follows:

- If the answer does not exist, output $$$-1$$$.
- If the answer exists, firstly output an integer $$$k$$$ — the number of substrings in the answer. After that output $$$k$$$ non-intersecting substrings, for $$$i$$$-th substring output two integers $$$l_i, r_i$$$ ($$$1 \le l_i, r_i \le |s|$$$) — the description of $$$i$$$-th substring.

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

## Examples
```input
4
00000
01101
0111011001011
000111100111110
```
```output
-1

3
1 3
4 4
5 5

8
1 2
3 3
4 4
5 6
7 7
8 10
11 12
13 13

5
1 5
6 7
8 11
12 14
15 15
```

## Note
In the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2.

In the second test case such cut is valid:

- $$$011_2 = 3_{10}$$$,
- $$$0_2 = 0_{10}$$$,
- $$$1_2 = 1_{10}$$$.

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: 64.0 MB

# Problem
Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick's attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least k prime numbers from 2 to n inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.

Two prime numbers are called neighboring if there are no other prime numbers between them.

You are to help Nick, and find out if he is right or wrong.

## Input Format
The first line of the input contains two integers n (2 ≤ n ≤ 1000) and k (0 ≤ k ≤ 1000).

## Output Format
Output YES if at least k prime numbers from 2 to n inclusively can be expressed as it was described above. Otherwise output NO.

## Examples
```input
27 2
```
```output
YES
```
-----
```input
45 7
```
```output
NO
```

## Note
In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.

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: 64.0 MB

# Problem
Nick's company employed n people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are m applications written in the following form: «employee ai is ready to become a supervisor of employee bi at extra cost ci». The qualification qj of each employee is known, and for each application the following is true: qai > qbi.

Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 1000) — amount of employees in the company. The following line contains n space-separated numbers qj (0 ≤ qj ≤ 106)— the employees' qualifications. The following line contains number m (0 ≤ m ≤ 10000) — amount of received applications. The following m lines contain the applications themselves, each of them in the form of three space-separated numbers: ai, bi and ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application qai > qbi.

## Output Format
Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

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

## Note
In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -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 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: 3.0 seconds
Memory limit: 128.0 MB

# Problem
Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations:

- to take two adjacent characters and replace the second character with the first one,
- to take two adjacent characters and replace the first character with the second one

To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: |a| = 1, |b| = 1, |c| = 1, and for string «bbc»: |a| = 0, |b| = 2, |c| = 1.

While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is  - 1 ≤ |a| - |b| ≤ 1,  - 1 ≤ |a| - |c| ≤ 1 и  - 1 ≤ |b| - |c| ≤ 1.

Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string s. This number should be calculated modulo 51123987.

## Input Format
The first line contains integer n (1 ≤ n ≤ 150) — the length of the given string s. Next line contains the given string s. The initial string can be balanced as well, in this case it should be counted too. The given string s consists only of characters a, b and c.

## Output Format
Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string s, modulo 51123987.

## Examples
```input
4
abca
```
```output
7
```
-----
```input
4
abbc
```
```output
3
```
-----
```input
2
ab
```
```output
1
```

## Note
In the first sample it is possible to get 51 different strings through the described operations, but only 7 of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.

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: 64.0 MB

# Problem
Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0 as he has unpleasant memories about zero divide.

Would you help Nick find out how many numbers will be written on the last page.

## Input Format
The only input line contains three space-separated integers b, n and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.

## Output Format
In the only line output the amount of numbers written on the same page as the last number.

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

## Note
In both samples there are exactly 4 numbers of length 3 in binary number system. In the first sample Nick writes 3 numbers on the first page and 1 on the second page. In the second sample all the 4 numbers can be written on the first page.

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: 128.0 MB

# Problem
In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1

• «bab» — 1..3

• «a» — 2..2

• «b» — 3..3

• «bb» — 3..4

• «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3

2. 1..3 cross with 2..2

3. 1..3 cross with 3..3

4. 1..3 cross with 3..4

5. 3..3 cross with 3..4

6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

## Output Format
In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

## Examples
```input
4
babb
```
```output
6
```
-----
```input
2
aa
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are beta testing the new secret Terraria update. This update will add quests to the game!

Simply, the world map can be represented as an array of length $$$n$$$, where the $$$i$$$-th column of the world has height $$$a_i$$$.

There are $$$m$$$ quests you have to test. The $$$j$$$-th of them is represented by two integers $$$s_j$$$ and $$$t_j$$$. In this quest, you have to go from the column $$$s_j$$$ to the column $$$t_j$$$. At the start of the quest, you are appearing at the column $$$s_j$$$.

In one move, you can go from the column $$$x$$$ to the column $$$x-1$$$ or to the column $$$x+1$$$. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height $$$p$$$ to the column with the height $$$q$$$, then you get some amount of fall damage. If the height $$$p$$$ is greater than the height $$$q$$$, you get $$$p - q$$$ fall damage, otherwise you fly up and get $$$0$$$ damage.

For each of the given quests, determine the minimum amount of fall damage you can get during this quest.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5; 1 \le m \le 10^5$$$) — the number of columns in the world and the number of quests you have to test, respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the height of the $$$i$$$-th column of the world.

The next $$$m$$$ lines describe quests. The $$$j$$$-th of them contains two integers $$$s_j$$$ and $$$t_j$$$ ($$$1 \le s_j, t_j \le n; s_j \ne t_j$$$), which means you have to move from the column $$$s_j$$$ to the column $$$t_j$$$ during the $$$j$$$-th quest.

Note that $$$s_j$$$ can be greater than $$$t_j$$$.

## Output Format
Print $$$m$$$ integers. The $$$j$$$-th of them should be the minimum amount of fall damage you can get during the $$$j$$$-th quest completion.

## Examples
```input
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2
```
```output
2
10
0
7
3
1
```

Now solve the problem and return the code.