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
Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.

## Input Format
The first line contains one number n (1 ≤ n ≤ 105), the size of the array.

The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.

## Output Format
Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.

If there are several possible answers you may output any of them.

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

## Note
A subsegment B of an array A from l to r is an array of size r - l + 1 where Bi = Al + i - 1 for all 1 ≤ i ≤ r - l + 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
Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.

Amr has n different types of chemicals. Each chemical i has an initial volume of ai liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.

To do this, Amr can do two different kind of operations.

- Choose some chemical i and double its current volume so the new volume will be 2ai
- Choose some chemical i and divide its volume by two (integer division) so the new volume will be $$\left[\frac{a_{i}}{2}\right]$$

Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?

## Input Format
The first line contains one number n (1 ≤ n ≤ 105), the number of chemicals.

The second line contains n space separated integers ai (1 ≤ ai ≤ 105), representing the initial volume of the i-th chemical in liters.

## Output Format
Output one integer the minimum number of operations required to make all the chemicals volumes equal.

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

## Note
In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.

In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Little Lesha loves listening to music via his smartphone. But the smartphone doesn't have much memory, so Lesha listens to his favorite songs in a well-known social network InTalk.

Unfortunately, internet is not that fast in the city of Ekaterinozavodsk and the song takes a lot of time to download. But Lesha is quite impatient. The song's duration is T seconds. Lesha downloads the first S seconds of the song and plays it. When the playback reaches the point that has not yet been downloaded, Lesha immediately plays the song from the start (the loaded part of the song stays in his phone, and the download is continued from the same place), and it happens until the song is downloaded completely and Lesha listens to it to the end. For q seconds of real time the Internet allows you to download q - 1 seconds of the track.

Tell Lesha, for how many times he will start the song, including the very first start.

## Input Format
The single line contains three integers T, S, q (2 ≤ q ≤ 104, 1 ≤ S < T ≤ 105).

## Output Format
Print a single integer — the number of times the song will be restarted.

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

## Note
In the first test, the song is played twice faster than it is downloaded, which means that during four first seconds Lesha reaches the moment that has not been downloaded, and starts the song again. After another two seconds, the song is downloaded completely, and thus, Lesha starts the song twice.

In the second test, the song is almost downloaded, and Lesha will start it only once.

In the third sample test the download finishes and Lesha finishes listening at the same moment. Note that song isn't restarted in this 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a database by using those numbers and keep the track of everything.

During an audit, you were surprised to find out that the items are not numbered sequentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chosen to make the numbers of the items sequential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum use of the current numbering.

You have been given information on current inventory numbers for n items in the company. Renumber items so that their inventory numbers form a permutation of numbers from 1 to n by changing the number of as few items as possible. Let us remind you that a set of n numbers forms a permutation if all the numbers are in the range from 1 to n, and no two numbers are equal.

## Input Format
The first line contains a single integer n — the number of items (1 ≤ n ≤ 105).

The second line contains n numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — the initial inventory numbers of the items.

## Output Format
Print n numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.

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

## Note
In the first test the numeration is already a permutation, so there is no need to change anything.

In the second test there are two pairs of equal numbers, in each pair you need to replace one number.

In the third test you need to replace 2 by 1, as the numbering should start from one.

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
Geometric progression with the first element a and common ratio b is a sequence of numbers a, ab, ab2, ab3, ....

You are given n integer geometric progressions. Your task is to find the smallest integer x, that is the element of all the given progressions, or else state that such integer does not exist.

## Input Format
The first line contains integer (1 ≤ n ≤ 100) — the number of geometric progressions.

Next n lines contain pairs of integers a, b (1 ≤ a, b ≤ 109), that are the first element and the common ratio of the corresponding geometric progression.

## Output Format
If the intersection of all progressions is empty, then print  - 1, otherwise print the remainder of the minimal positive integer number belonging to all progressions modulo 1000000007 (109 + 7).

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

## Note
In the second sample test one of the progressions contains only powers of two, the other one contains only powers of three.

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
Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes ai money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence ai. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.

Help Kefa cope with this task!

## Input Format
The first line contains integer n (1 ≤ n ≤ 105).

The second line contains n integers a1,  a2,  ...,  an (1 ≤ ai ≤ 109).

## Output Format
Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.

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

## Note
In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.

In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.

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
When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were n dishes. Kefa knows that he needs exactly m dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible.

Kefa knows that the i-th dish gives him ai units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself k rules of eating food of the following type — if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c.

Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task!

## Input Format
The first line of the input contains three space-separated numbers, n, m and k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

The second line contains n space-separated numbers ai, (0 ≤ ai ≤ 109) — the satisfaction he gets from the i-th dish.

Next k lines contain the rules. The i-th rule is described by the three numbers xi, yi and ci (1 ≤ xi, yi ≤ n, 0 ≤ ci ≤ 109). That means that if you eat dish xi right before dish yi, then the Kefa's satisfaction increases by ci. It is guaranteed that there are no such pairs of indexes i and j (1 ≤ i < j ≤ k), that xi = xj and yi = yj.

## Output Format
In the single line of the output print the maximum satisfaction that Kefa can get from going to the restaurant.

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

## Note
In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule.

In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 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 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.5 seconds
Memory limit: 256.0 MB

# Problem
One day Kefa the parrot was walking down the street as he was on the way home from the restaurant when he saw something glittering by the road. As he came nearer he understood that it was a watch. He decided to take it to the pawnbroker to earn some money.

The pawnbroker said that each watch contains a serial number represented by a string of digits from 0 to 9, and the more quality checks this number passes, the higher is the value of the watch. The check is defined by three positive integers l, r and d. The watches pass a check if a substring of the serial number from l to r has period d. Sometimes the pawnbroker gets distracted and Kefa changes in some substring of the serial number all digits to c in order to increase profit from the watch.

The seller has a lot of things to do to begin with and with Kefa messing about, he gave you a task: to write a program that determines the value of the watch.

Let us remind you that number x is called a period of string s (1 ≤ x ≤ |s|), if si  =  si + x for all i from 1 to |s|  -  x.

## Input Format
The first line of the input contains three positive integers n, m and k (1 ≤ n ≤ 105, 1 ≤ m + k ≤ 105) — the length of the serial number, the number of change made by Kefa and the number of quality checks.

The second line contains a serial number consisting of n digits.

Then m + k lines follow, containing either checks or changes.

The changes are given as 1 l r c (1 ≤ l ≤ r ≤ n, 0 ≤ c ≤ 9). That means that Kefa changed all the digits from the l-th to the r-th to be c.

The checks are given as 2 l r d (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ r - l + 1).

## Output Format
For each check on a single line print "YES" if the watch passed it, otherwise print "NO".

## Examples
```input
3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1
```
```output
NO
YES
```
-----
```input
6 2 3
334934
2 2 5 2
1 4 4 3
2 1 6 3
1 2 3 8
2 3 6 1
```
```output
NO
YES
NO
```

## Note
In the first sample test two checks will be made. In the first one substring "12" is checked on whether or not it has period 1, so the answer is "NO". In the second one substring "88", is checked on whether or not it has period 1, and it has this period, so the answer is "YES".

In the second statement test three checks will be made. The first check processes substring "3493", which doesn't have period 2. Before the second check the string looks as "334334", so the answer to it is "YES". And finally, the third check processes substring "8334", which does not have period 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
Olesya loves numbers consisting of n digits, and Rodion only likes numbers that are divisible by t. Find some number that satisfies both of them.

Your task is: given the n and t print an integer strictly larger than zero consisting of n digits that is divisible by t. If such number doesn't exist, print  - 1.

## Input Format
The single line contains two numbers, n and t (1 ≤ n ≤ 100, 2 ≤ t ≤ 10) — the length of the number and the number it should be divisible by.

## Output Format
Print one such positive number without leading zeroes, — the answer to the problem, or  - 1, if such number doesn't exist. If there are multiple possible answers, you are allowed to print any of them.

## Examples
```input
3 2
```
```output
712
```

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
Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place have ai coins. If there is an integer i (0 ≤ i < n) such that ai + ai + n + ai + 2n ≠ 6, then Tanya is satisfied.

Count the number of ways to choose ai so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 109 + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3n), such that ai ≠ bi (that is, some gnome got different number of coins in these two ways).

## Input Format
A single line contains number n (1 ≤ n ≤ 105) — the number of the gnomes divided by three.

## Output Format
Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 109 + 7.

## Examples
```input
1
```
```output
20
```
-----
```input
2
```
```output
680
```

## Note
20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex):

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
Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.

More formally, you are given two strings s1, s2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s3 of length n, such that f(s1, s3) = f(s2, s3) = t. If there is no such string, print  - 1.

## Input Format
The first line contains two integers n and t (1 ≤ n ≤ 105, 0 ≤ t ≤ n).

The second line contains string s1 of length n, consisting of lowercase English letters.

The third line contain string s2 of length n, consisting of lowercase English letters.

## Output Format
Print a string of length n, differing from string s1 and from s2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.

## Examples
```input
3 2
abc
xyc
```
```output
ayd
```
-----
```input
1 0
c
b
```
```output
-1
```

Now solve the problem and return the code.