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
Ivan has an array consisting of n elements. Each of the elements is an integer from 1 to n.

Recently Ivan learned about permutations and their lexicographical order. Now he wants to change (replace) minimum number of elements in his array in such a way that his array becomes a permutation (i.e. each of the integers from 1 to n was encountered in his array exactly once). If there are multiple ways to do it he wants to find the lexicographically minimal permutation among them.

Thus minimizing the number of changes has the first priority, lexicographical minimizing has the second priority.

In order to determine which of the two permutations is lexicographically smaller, we compare their first elements. If they are equal — compare the second, and so on. If we have two permutations x and y, then x is lexicographically smaller if xi < yi, where i is the first index in which the permutations x and y differ.

Determine the array Ivan will obtain after performing all the changes.

## Input Format
The first line contains an single integer n (2 ≤ n ≤ 200 000) — the number of elements in Ivan's array.

The second line contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ n) — the description of Ivan's array.

## Output Format
In the first line print q — the minimum number of elements that need to be changed in Ivan's array in order to make his array a permutation. In the second line, print the lexicographically minimal permutation which can be obtained from array with q changes.

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

## Note
In the first example Ivan needs to replace number three in position 1 with number one, and number two in position 3 with number four. Then he will get a permutation [1, 2, 4, 3] with only two changed numbers — this permutation is lexicographically minimal among all suitable.

In the second example Ivan does not need to change anything because his array already is a permutation.

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
Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take ti seconds to save i-th item. In addition, for each item, he estimated the value of di — the moment after which the item i will be completely burned and will no longer be valuable for him at all. In particular, if ti ≥ di, then i-th item cannot be saved.

Given the values pi for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item a first, and then item b, then the item a will be saved in ta seconds, and the item b — in ta + tb seconds after fire started.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of items in Polycarp's house.

Each of the following n lines contains three integers ti, di, pi (1 ≤ ti ≤ 20, 1 ≤ di ≤ 2 000, 1 ≤ pi ≤ 20) — the time needed to save the item i, the time after which the item i will burn completely and the value of item i.

## Output Format
In the first line print the maximum possible total value of the set of saved items. In the second line print one integer m — the number of items in the desired set. In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.

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

## Note
In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2 seconds. Thus, the total value of the saved items will be 6 + 5 = 11.

In the second example Polycarp can save only the first item, since even if he immediately starts saving the second item, he can save it in 3 seconds, but this item will already be completely burned by this time.

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
There are n cities in Berland. Some pairs of them are connected with m directed roads. One can use only these roads to move from one city to another. There are no roads that connect a city to itself. For each pair of cities (x, y) there is at most one road from x to y.

A path from city s to city t is a sequence of cities p1, p2, ... , pk, where p1 = s, pk = t, and there is a road from city pi to city pi + 1 for each i from 1 to k - 1. The path can pass multiple times through each city except t. It can't pass through t more than once.

A path p from s to t is ideal if it is the lexicographically minimal such path. In other words, p is ideal path from s to t if for any other path q from s to t pi < qi, where i is the minimum integer such that pi ≠ qi.

There is a tourist agency in the country that offers q unusual excursions: the j-th excursion starts at city sj and ends in city tj.

For each pair sj, tj help the agency to study the ideal path from sj to tj. Note that it is possible that there is no ideal path from sj to tj. This is possible due to two reasons:

- there is no path from sj to tj;
- there are paths from sj to tj, but for every such path p there is another path q from sj to tj, such that pi > qi, where i is the minimum integer for which pi ≠ qi.

The agency would like to know for the ideal path from sj to tj the kj-th city in that path (on the way from sj to tj).

For each triple sj, tj, kj (1 ≤ j ≤ q) find if there is an ideal path from sj to tj and print the kj-th city in that path, if there is any.

## Input Format
The first line contains three integers n, m and q (2 ≤ n ≤ 3000,0 ≤ m ≤ 3000, 1 ≤ q ≤ 4·105) — the number of cities, the number of roads and the number of excursions.

Each of the next m lines contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi), denoting that the i-th road goes from city xi to city yi. All roads are one-directional. There can't be more than one road in each direction between two cities.

Each of the next q lines contains three integers sj, tj and kj (1 ≤ sj, tj ≤ n, sj ≠ tj, 1 ≤ kj ≤ 3000).

## Output Format
In the j-th line print the city that is the kj-th in the ideal path from sj to tj. If there is no ideal path from sj to tj, or the integer kj is greater than the length of this path, print the string '-1' (without quotes) in the j-th line.

## Examples
```input
7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2
2 6 1
1 7 3
1 3 2
1 3 5
```
```output
2
-1
-1
2
-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
Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform:

- U — move from the cell (x, y) to (x, y + 1);
- D — move from (x, y) to (x, y - 1);
- L — move from (x, y) to (x - 1, y);
- R — move from (x, y) to (x + 1, y).

Ivan entered a sequence of n commands, and the robot processed it. After this sequence the robot ended up in the starting cell (0, 0), but Ivan doubts that the sequence is such that after performing it correctly the robot ends up in the same cell. He thinks that some commands were ignored by robot. To acknowledge whether the robot is severely bugged, he needs to calculate the maximum possible number of commands that were performed correctly. Help Ivan to do the calculations!

## Input Format
The first line contains one number n — the length of sequence of commands entered by Ivan (1 ≤ n ≤ 100).

The second line contains the sequence itself — a string consisting of n characters. Each character can be U, D, L or R.

## Output Format
Print the maximum possible number of commands from the sequence the robot could perform to end up in the starting cell.

## Examples
```input
4
LDUR
```
```output
4
```
-----
```input
5
RRRUU
```
```output
0
```
-----
```input
6
LLRRRR
```
```output
4
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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 string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

## Input Format
The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

## Output Format
Print one number — the minimum value of k such that there exists at least one k-dominant character.

## Examples
```input
abacaba
```
```output
2
```
-----
```input
zzzzz
```
```output
1
```
-----
```input
abcde
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that pi = i.

Your task is to count the number of almost identity permutations for given numbers n and k.

## Input Format
The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).

## Output Format
Print the number of almost identity permutations for given n and k.

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

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
You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n) in such a way that the value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$ is maximized. Chosen sequence can be empty.

Print the maximum possible value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

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

## Output Format
Print the maximum possible value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$.

## Examples
```input
4 4
5 2 4 1
```
```output
3
```
-----
```input
3 20
199 41 299
```
```output
19
```

## Note
In the first example you can choose a sequence b = {1, 2}, so the sum $$\sum_{i=1}^{k}a_{bi}$$ is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {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
Students Vasya and Petya are studying at the BSU (Byteland State University). At one of the breaks they decided to order a pizza. In this problem pizza is a circle of some radius. The pizza was delivered already cut into n pieces. The i-th piece is a sector of angle equal to ai. Vasya and Petya want to divide all pieces of pizza into two continuous sectors in such way that the difference between angles of these sectors is minimal. Sector angle is sum of angles of all pieces in it. Pay attention, that one of sectors can be empty.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 360)  — the number of pieces into which the delivered pizza was cut.

The second line contains n integers ai (1 ≤ ai ≤ 360)  — the angles of the sectors into which the pizza was cut. The sum of all ai is 360.

## Output Format
Print one integer  — the minimal difference between angles of sectors that will go to Vasya and Petya.

## Examples
```input
4
90 90 90 90
```
```output
0
```
-----
```input
3
100 100 160
```
```output
40
```
-----
```input
1
360
```
```output
360
```
-----
```input
4
170 30 150 10
```
```output
0
```

## Note
In first sample Vasya can take 1 and 2 pieces, Petya can take 3 and 4 pieces. Then the answer is |(90 + 90) - (90 + 90)| = 0.

In third sample there is only one piece of pizza that can be taken by only one from Vasya and Petya. So the answer is |360 - 0| = 360.

In fourth sample Vasya can take 1 and 4 pieces, then Petya will take 2 and 3 pieces. So the answer is |(170 + 10) - (30 + 150)| = 0.

Picture explaning fourth sample:

Both red and green sectors consist of two adjacent pieces of pizza. So Vasya can take green sector, then Petya will take red sector.

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
While Vasya finished eating his piece of pizza, the lesson has already started. For being late for the lesson, the teacher suggested Vasya to solve one interesting problem. Vasya has an array a and integer x. He should find the number of different ordered pairs of indexes (i, j) such that ai ≤ aj and there are exactly k integers y such that ai ≤ y ≤ aj and y is divisible by x.

In this problem it is meant that pair (i, j) is equal to (j, i) only if i is equal to j. For example pair (1, 2) is not the same as (2, 1).

## Input Format
The first line contains 3 integers n, x, k (1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109), where n is the size of the array a and x and k are numbers from the statement.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

## Output Format
Print one integer — the answer to the problem.

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

## Note
In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).

In second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).

In third sample every pair (i, j) is suitable, so the answer is 5 * 5 = 25.

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

# Problem
Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 109 + 7.

## Input Format
First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.

Second line contains n integers ai (1 ≤ ai ≤ 70) — the elements of the array.

## Output Format
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.

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

## Note
In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

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

# Problem
At the Byteland State University marks are strings of the same length. Mark x is considered better than y if string y is lexicographically smaller than x.

Recently at the BSU was an important test work on which Vasya recived the mark a. It is very hard for the teacher to remember the exact mark of every student, but he knows the mark b, such that every student recieved mark strictly smaller than b.

Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious.

More formally: you are given two strings a, b of the same length and you need to figure out the number of different strings c such that:

1) c can be obtained from a by swapping some characters, in other words c is a permutation of a.

2) String a is lexicographically smaller than c.

3) String c is lexicographically smaller than b.

For two strings x and y of the same length it is true that x is lexicographically smaller than y if there exists such i, that x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi.

Since the answer can be very large, you need to find answer modulo 109 + 7.

## Input Format
First line contains string a, second line contains string b. Strings a, b consist of lowercase English letters. Their lengths are equal and don't exceed 106.

It is guaranteed that a is lexicographically smaller than b.

## Output Format
Print one integer  — the number of different strings satisfying the condition of the problem modulo 109 + 7.

## Examples
```input
abc
ddd
```
```output
5
```
-----
```input
abcdef
abcdeg
```
```output
0
```
-----
```input
abacaba
ubuduba
```
```output
64
```

## Note
In first sample from string abc can be obtained strings acb, bac, bca, cab, cba, all of them are larger than abc, but smaller than ddd. So the answer is 5.

In second sample any string obtained from abcdef is larger than abcdeg. So the answer is 0.

Now solve the problem and return the code.