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
It seems like the year of 2013 came only yesterday. Do you know a curious fact? The year of 2013 is the first year after the old 1987 with only distinct digits.

Now you are suggested to solve the following problem: given a year number, find the minimum year number which is strictly larger than the given one and has only distinct digits.

## Input Format
The single line contains integer y (1000 ≤ y ≤ 9000) — the year number.

## Output Format
Print a single integer — the minimum year number that is strictly larger than y and all it's digits are distinct. It is guaranteed that the answer exists.

## Examples
```input
1987
```
```output
2013
```
-----
```input
2013
```
```output
2014
```

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've got an n × m matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not.

A matrix is prime if at least one of the two following conditions fulfills:

- the matrix has a row with prime numbers only;
- the matrix has a column with prime numbers only;

Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the number of rows and columns in the matrix, correspondingly.

Each of the following n lines contains m integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 105.

The numbers in the lines are separated by single spaces.

## Output Format
Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.

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

## Note
In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 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 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
The Greatest Secret Ever consists of n words, indexed by positive integers from 1 to n. The secret needs dividing between k Keepers (let's index them by positive integers from 1 to k), the i-th Keeper gets a non-empty set of words with numbers from the set Ui = (ui, 1, ui, 2, ..., ui, |Ui|). Here and below we'll presuppose that the set elements are written in the increasing order.

We'll say that the secret is safe if the following conditions are hold:

- for any two indexes i, j (1 ≤ i < j ≤ k) the intersection of sets Ui and Uj is an empty set;
- the union of sets U1, U2, ..., Uk is set (1, 2, ..., n);
- in each set Ui, its elements ui, 1, ui, 2, ..., ui, |Ui| do not form an arithmetic progression (in particular, |Ui| ≥ 3 should hold).

Let us remind you that the elements of set (u1, u2, ..., us) form an arithmetic progression if there is such number d, that for all i (1 ≤ i < s) fulfills ui + d = ui + 1. For example, the elements of sets (5), (1, 10) and (1, 5, 9) form arithmetic progressions and the elements of sets (1, 2, 4) and (3, 6, 8) don't.

Your task is to find any partition of the set of words into subsets U1, U2, ..., Uk so that the secret is safe. Otherwise indicate that there's no such partition.

## Input Format
The input consists of a single line which contains two integers n and k (2 ≤ k ≤ n ≤ 106) — the number of words in the secret and the number of the Keepers. The numbers are separated by a single space.

## Output Format
If there is no way to keep the secret safe, print a single integer "-1" (without the quotes). Otherwise, print n integers, the i-th of them representing the number of the Keeper who's got the i-th word of the secret.

If there are multiple solutions, print any of them.

## Examples
```input
11 3
```
```output
3 1 2 1 1 2 3 2 2 3 1
```
-----
```input
5 2
```
```output
-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: 512.0 MB

# Problem
You've got string s, consisting of small English letters. Some of the English letters are good, the rest are bad.

A substring s[l...r] (1 ≤ l ≤ r ≤ |s|) of string s  =  s1s2...s|s| (where |s| is the length of string s) is string  slsl + 1...sr.

The substring s[l...r] is good, if among the letters  sl, sl + 1, ..., sr there are at most k bad ones (look at the sample's explanation to understand it more clear).

Your task is to find the number of distinct good substrings of the given string s. Two substrings s[x...y] and s[p...q] are considered distinct if their content is different, i.e. s[x...y] ≠ s[p...q].

## Input Format
The first line of the input is the non-empty string s, consisting of small English letters, the string's length is at most 1500 characters.

The second line of the input is the string of characters "0" and "1", the length is exactly 26 characters. If the i-th character of this string equals "1", then the i-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

The third line of the input consists a single integer k (0 ≤ k ≤ |s|) — the maximum acceptable number of bad characters in a good substring.

## Output Format
Print a single integer — the number of distinct good substrings of string s.

## Examples
```input
ababab
01000000000000000000000000
1
```
```output
5
```
-----
```input
acbacbacaa
00000000000000000000000000
2
```
```output
8
```

## Note
In the first example there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second example there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

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
There are three horses living in a horse land: one gray, one white and one gray-and-white. The horses are really amusing animals, which is why they adore special cards. Each of those cards must contain two integers, the first one on top, the second one in the bottom of the card. Let's denote a card with a on the top and b in the bottom as (a, b).

Each of the three horses can paint the special cards. If you show an (a, b) card to the gray horse, then the horse can paint a new (a + 1, b + 1) card. If you show an (a, b) card, such that a and b are even integers, to the white horse, then the horse can paint a new $$( \frac { a } { 2 }, \frac { b } { 2 } )$$ card. If you show two cards (a, b) and (b, c) to the gray-and-white horse, then he can paint a new (a, c) card.

Polycarpus really wants to get n special cards (1, a1), (1, a2), ..., (1, an). For that he is going to the horse land. He can take exactly one (x, y) card to the horse land, such that 1 ≤ x < y ≤ m. How many ways are there to choose the card so that he can perform some actions in the horse land and get the required cards?

Polycarpus can get cards from the horses only as a result of the actions that are described above. Polycarpus is allowed to get additional cards besides the cards that he requires.

## Input Format
The first line contains two integers n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 109). The second line contains the sequence of integers a1, a2, ..., an (2 ≤ ai ≤ 109). Note, that the numbers in the sequence can coincide.

The numbers in the lines are separated by single spaces.

## Output Format
Print a single integer — the answer to the problem.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Examples
```input
1 6
2
```
```output
11
```
-----
```input
1 6
7
```
```output
14
```
-----
```input
2 10
13 7
```
```output
36
```

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

# Problem
Consider integer sequence a1, a2, ..., an. You should run queries of two types:

- The query format is "0 i val". In reply to this query you should make the following assignment: ai = val.
- The query format is "1 l r k". In reply to this query you should print the maximum sum of at most k non-intersecting subsegments of sequence al, al + 1, ..., ar. Formally, you should choose at most k pairs of integers (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k) such that the sum ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the sequence has. The next line contains n integers a1, a2, ..., an (|ai| ≤ 500).

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries. The next m lines contain the queries in the format, given in the statement.

All changing queries fit into limits: 1 ≤ i ≤ n, |val| ≤ 500.

All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most k non-intersecting subsegments doesn't exceed 10000.

## Output Format
For each query to count the maximum sum of at most k non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

## Examples
```input
9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3
```
```output
17
25
0
```
-----
```input
15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1
```
```output
14
11
15
0
15
26
18
23
8
```

## Note
In the first query of the first example you can select a single pair (1, 9). So the described sum will be 17.

Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25.

The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative.

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
Shaass has decided to hunt some birds. There are n horizontal electricity wires aligned parallel to each other. Wires are numbered 1 to n from top to bottom. On each wire there are some oskols sitting next to each other. Oskol is the name of a delicious kind of birds in Shaass's territory. Supposed there are ai oskols sitting on the i-th wire.

Sometimes Shaass shots one of the birds and the bird dies (suppose that this bird sat at the i-th wire). Consequently all the birds on the i-th wire to the left of the dead bird get scared and jump up on the wire number i - 1, if there exists no upper wire they fly away. Also all the birds to the right of the dead bird jump down on wire number i + 1, if there exists no such wire they fly away.

Shaass has shot m birds. You're given the initial number of birds on each wire, tell him how many birds are sitting on each wire after the shots.

## Input Format
The first line of the input contains an integer n, (1 ≤ n ≤ 100). The next line contains a list of space-separated integers a1, a2, ..., an, (0 ≤ ai ≤ 100).

The third line contains an integer m, (0 ≤ m ≤ 100). Each of the next m lines contains two integers xi and yi. The integers mean that for the i-th time Shaass shoot the yi-th (from left) bird on the xi-th wire, (1 ≤ xi ≤ n, 1 ≤ yi). It's guaranteed there will be at least yi birds on the xi-th wire at that moment.

## Output Format
On the i-th line of the output print the number of birds on the i-th wire.

## Examples
```input
5
10 10 10 10 10
5
2 5
3 13
2 12
1 13
4 6
```
```output
0
12
5
0
16
```
-----
```input
3
2 4 1
1
2 2
```
```output
3
0
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 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 lights aligned in a row. These lights are numbered 1 to n from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there's at least one adjacent light which is already switched on.

He knows the initial state of lights and he's wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo 1000000007 (109 + 7).

## Input Format
The first line of the input contains two integers n and m where n is the number of lights in the sequence and m is the number of lights which are initially switched on, (1 ≤ n ≤ 1000, 1 ≤ m ≤ n). The second line contains m distinct integers, each between 1 to n inclusive, denoting the indices of lights which are initially switched on.

## Output Format
In the only line of the output print the number of different possible ways to switch on all the lights modulo 1000000007 (109 + 7).

## Examples
```input
3 1
1
```
```output
1
```
-----
```input
4 2
1 4
```
```output
2
```
-----
```input
11 2
4 8
```
```output
6720
```

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
The polar bears are going fishing. They plan to sail from (sx, sy) to (ex, ey). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (x, y).

- If the wind blows to the east, the boat will move to (x + 1, y).
- If the wind blows to the south, the boat will move to (x, y - 1).
- If the wind blows to the west, the boat will move to (x - 1, y).
- If the wind blows to the north, the boat will move to (x, y + 1).

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (x, y). Given the wind direction for t seconds, what is the earliest time they sail to (ex, ey)?

## Input Format
The first line contains five integers t, sx, sy, ex, ey (1 ≤ t ≤ 105,  - 109 ≤ sx, sy, ex, ey ≤ 109). The starting location and the ending location will be different.

The second line contains t characters, the i-th character is the wind blowing direction at the i-th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

## Output Format
If they can reach (ex, ey) within t seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

## Examples
```input
5 0 0 1 1
SESNW
```
```output
4
```
-----
```input
10 5 3 3 6
NENSWESNEE
```
```output
-1
```

## Note
In the first sample, they can stay at seconds 1, 3, and move at seconds 2, 4.

In the second sample, they cannot sail to the destination.

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
Yaroslav has an array p = p1, p2, ..., pn (1 ≤ pi ≤ n), consisting of n distinct integers. Also, he has m queries:

- Query number i is represented as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
- The answer to the query li, ri is the number of pairs of integers q, w (li ≤ q, w ≤ ri) such that pq is the divisor of pw.

Help Yaroslav, answer all his queries.

## Input Format
The first line contains the integers n and m (1 ≤ n, m ≤ 2·105). The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). The following m lines contain Yaroslav's queries. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n).

## Output Format
Print m integers — the answers to Yaroslav's queries in the order they appear in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

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

# Problem
Yaroslav calls an array of r integers a1, a2, ..., ar good, if it meets the following conditions: |a1 - a2| = 1, |a2 - a3| = 1, ..., |ar - 1 - ar| = 1, |ar - a1| = 1, at that $$a_{1} = \min_{i=1}^{r} a_{i}$$.

An array of integers b1, b2, ..., br is called great, if it meets the following conditions:

1. The elements in it do not decrease (bi ≤ bi + 1).
2. If the inequalities 1 ≤ r ≤ n and 1 ≤ bi ≤ m hold.
3. If we can rearrange its elements and get at least one and at most k distinct good arrays.

Yaroslav has three integers n, m, k. He needs to count the number of distinct great arrays. Help Yaroslav! As the answer may be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Two arrays are considered distinct if there is a position in which they have distinct numbers.

## Input Format
The single line contains three integers n, m, k (1 ≤ n, m, k ≤ 100).

## Output Format
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

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

Now solve the problem and return the code.