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 soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
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
String x is an anagram of string y, if we can rearrange the letters in string x and get exact string y. For example, strings "DOG" and "GOD" are anagrams, so are strings "BABA" and "AABB", but strings "ABBAC" and "CAABA" are not.

You are given two strings s and t of the same length, consisting of uppercase English letters. You need to get the anagram of string t from string s. You are permitted to perform the replacing operation: every operation is replacing some character from the string s by any other character. Get the anagram of string t in the least number of replacing operations. If you can get multiple anagrams of string t in the least number of operations, get the lexicographically minimal one.

The lexicographic order of strings is the familiar to us "dictionary" order. Formally, the string p of length n is lexicographically smaller than string q of the same length, if p1 = q1, p2 = q2, ..., pk - 1 = qk - 1, pk < qk for some k (1 ≤ k ≤ n). Here characters in the strings are numbered from 1. The characters of the strings are compared in the alphabetic order.

## Input Format
The input consists of two lines. The first line contains string s, the second line contains string t. The strings have the same length (from 1 to 105 characters) and consist of uppercase English letters.

## Output Format
In the first line print z — the minimum number of replacement operations, needed to get an anagram of string t from string s. In the second line print the lexicographically minimum anagram that could be obtained in z operations.

## Examples
```input
ABA
CBA
```
```output
1
ABC
```
-----
```input
CDBABC
ADCABD
```
```output
2
ADBADC
```

## Note
The second sample has eight anagrams of string t, that can be obtained from string s by replacing exactly two letters: "ADBADC", "ADDABC", "CDAABD", "CDBAAD", "CDBADA", "CDDABA", "DDAABC", "DDBAAC". These anagrams are listed in the lexicographical order. The lexicographically minimum anagram is "ADBADC".

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
Maxim has got a calculator. The calculator has two integer cells. Initially, the first cell contains number 1, and the second cell contains number 0. In one move you can perform one of the following operations:

1. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the second cell number b + 1;
2. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the first cell number a·b.

Maxim is wondering, how many integers x (l ≤ x ≤ r) are there, such that we can write the number x to the first cell of the calculator, having performed at most p moves.

## Input Format
The first line contains three integers: l, r, p (2 ≤ l ≤ r ≤ 109, 1 ≤ p ≤ 100).

The numbers in the line are separated by single spaces.

## Output Format
In a single line print a single integer — the answer to the problem.

## Examples
```input
2 10 3
```
```output
1
```
-----
```input
2 111 100
```
```output
106
```
-----
```input
2 111 11
```
```output
47
```

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 Valera has got some free time, he goes to the library to read some books. Today he's got t free minutes to read. That's why Valera took n books in the library and for each book he estimated the time he is going to need to read it. Let's number the books by integers from 1 to n. Valera needs ai minutes to read the i-th book.

Valera decided to choose an arbitrary book with number i and read the books one by one, starting from this book. In other words, he will first read book number i, then book number i + 1, then book number i + 2 and so on. He continues the process until he either runs out of the free time or finishes reading the n-th book. Valera reads each book up to the end, that is, he doesn't start reading the book if he doesn't have enough free time to finish reading it.

Print the maximum number of books Valera can read.

## Input Format
The first line contains two integers n and t (1 ≤ n ≤ 105; 1 ≤ t ≤ 109) — the number of books and the number of free minutes Valera's got. The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 104), where number ai shows the number of minutes that the boy needs to read the i-th book.

## Output Format
Print a single integer — the maximum number of books Valera can read.

## Examples
```input
4 5
3 1 2 1
```
```output
3
```
-----
```input
3 3
2 2 3
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You've got a positive integer sequence a1, a2, ..., an. All numbers in the sequence are distinct. Let's fix the set of variables b1, b2, ..., bm. Initially each variable bi (1 ≤ i ≤ m) contains the value of zero. Consider the following sequence, consisting of n operations.

The first operation is assigning the value of a1 to some variable bx (1 ≤ x ≤ m). Each of the following n - 1 operations is assigning to some variable by the value that is equal to the sum of values that are stored in the variables bi and bj (1 ≤ i, j, y ≤ m). At that, the value that is assigned on the t-th operation, must equal at. For each operation numbers y, i, j are chosen anew.

Your task is to find the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

## Input Format
The first line contains integer n (1 ≤ n ≤ 23). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ak ≤ 109).

It is guaranteed that all numbers in the sequence are distinct.

## Output Format
In a single line print a single number — the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

If you cannot perform the sequence of operations at any m, print -1.

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

## Note
In the first sample, you can use two variables b1 and b2 to perform the following sequence of operations.

1. b1 := 1;
2. b2 := b1 + b1;
3. b1 := b1 + b2;
4. b1 := b1 + b1;
5. b1 := b1 + b2.

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

# Problem
A ladies' shop has recently opened in the city of Ultima Thule. To get ready for the opening, the shop bought n bags. Each bag is characterised by the total weight ai of the items you can put there. The weird thing is, you cannot use these bags to put a set of items with the total weight strictly less than ai. However the weights of the items that will be sold in the shop haven't yet been defined. That's what you should determine right now.

Your task is to find the set of the items' weights p1, p2, ..., pk (1 ≤ p1 < p2 < ... < pk), such that:

1. Any bag will be used. That is, for any i (1 ≤ i ≤ n) there will be such set of items that their total weight will equal ai. We assume that there is the infinite number of items of any weight. You can put multiple items of the same weight in one bag.
2. For any set of items that have total weight less than or equal to m, there is a bag into which you can put this set. Similarly, a set of items can contain multiple items of the same weight.
3. Of all sets of the items' weights that satisfy points 1 and 2, find the set with the minimum number of weights. In other words, value k should be as small as possible.

Find and print the required set.

## Input Format
The first line contains space-separated integers n and m (1 ≤ n, m ≤ 106). The second line contains n distinct space-separated integers a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ m) — the bags' weight limits.

## Output Format
In the first line print "NO" (without the quotes) if there isn't set pi, that would meet the conditions.

Otherwise, in the first line print "YES" (without the quotes), in the second line print an integer k (showing how many numbers are in the suitable set with the minimum number of weights), in the third line print k space-separated integers p1, p2, ..., pk (1 ≤ p1 < p2 < ... < pk). If there are multiple solutions, print any of them.

## Examples
```input
6 10
5 6 7 8 9 10
```
```output
YES
5
5 6 7 8 9
```
-----
```input
1 10
1
```
```output
NO
```
-----
```input
1 10
6
```
```output
YES
1
6
```

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
Everybody knows that lucky numbers are positive integers that contain only lucky digits 4 and 7 in their decimal representation. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Polo the Penguin have two positive integers l and r (l < r), both of them are lucky numbers. Moreover, their lengths (that is, the number of digits in the decimal representation without the leading zeroes) are equal to each other.

Let's assume that n is the number of distinct lucky numbers, each of them cannot be greater than r or less than l, and ai is the i-th (in increasing order) number of them. Find a1·a2 + a2·a3 + ... + an - 1·an. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

## Input Format
The first line contains a positive integer l, and the second line contains a positive integer r (1 ≤ l < r ≤ 10100000). The numbers are given without any leading zeroes.

It is guaranteed that the lengths of the given numbers are equal to each other and that both of them are lucky numbers.

## Output Format
In the single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

## Examples
```input
4
7
```
```output
28
```
-----
```input
474
777
```
```output
2316330
```

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 famous joke programming language HQ9+ has only 4 commands. In this problem we will explore its subset — a language called HQ...

## Input Format
The only line of the input is a string between 1 and 106 characters long.

## Output Format
Output "Yes" or "No".

## Examples
```input
HHHH
```
```output
Yes
```
-----
```input
HQHQH
```
```output
No
```
-----
```input
HHQHHQH
```
```output
No
```
-----
```input
HHQQHHQQHH
```
```output
Yes
```

## Note
The rest of the problem statement was destroyed by a stray raccoon. We are terribly sorry for the inconvenience.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Petya is an unexperienced programming contestant. Recently he has come across the following problem:

You are given a non-directed graph which consists of n nodes and m edges. Your task is to determine whether the graph contains a Hamiltonian path.

Petya wrote a quick bug-free code which he believes solves this problem. After that Petya decided to give this problem for April Fools Day contest. Unfortunately, Petya might have made a mistake, and it's quite possible that his algorithm is wrong. But this isn't a good excuse to leave the contest without submitting this problem, is it?

## Input Format
The first line contains two integers n, m (1 ≤ n ≤ 20; 0 ≤ m ≤ 400). Next m lines contain pairs of integers vi, ui (1 ≤ vi, ui ≤ n).

## Output Format
Follow the format of Petya's code output.

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

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
A continued fraction of height n is a fraction of form $$a_{1}+\frac{1}{a_{2}+\frac{1}{\cdots+\frac{1}{a_{n}}}}$$. You are given two rational numbers, one is represented as $$\frac{p}{q}$$ and the other one is represented as a finite fraction of height n. Check if they are equal.

## Input Format
The first line contains two space-separated integers p, q (1 ≤ q ≤ p ≤ 1018) — the numerator and the denominator of the first fraction.

The second line contains integer n (1 ≤ n ≤ 90) — the height of the second fraction. The third line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1018) — the continued fraction.

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

## Output Format
Print "YES" if these fractions are equal and "NO" otherwise.

## Examples
```input
9 4
2
2 4
```
```output
YES
```
-----
```input
9 4
3
2 3 1
```
```output
YES
```
-----
```input
9 4
3
1 2 4
```
```output
NO
```

## Note
In the first sample $$2 + \frac{1}{4} = \frac{9}{4}$$.

In the second sample $$2 + \frac{1}{3+\frac{1}{1}} = 2 + \frac{1}{4} = \frac{9}{4}$$.

In the third sample $$1 + \frac{1}{2+\frac{1}{4}} = \frac{13}{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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Olya has got a directed non-weighted graph, consisting of n vertexes and m edges. We will consider that the graph vertexes are indexed from 1 to n in some manner. Then for any graph edge that goes from vertex v to vertex u the following inequation holds: v < u.

Now Olya wonders, how many ways there are to add an arbitrary (possibly zero) number of edges to the graph so as the following conditions were met:

1. You can reach vertexes number i + 1, i + 2, ..., n from any vertex number i (i < n).
2. For any graph edge going from vertex v to vertex u the following inequation fulfills: v < u.
3. There is at most one edge between any two vertexes.
4. The shortest distance between the pair of vertexes i, j (i < j), for which j - i ≤ k holds, equals j - i edges.
5. The shortest distance between the pair of vertexes i, j (i < j), for which j - i > k holds, equals either j - i or j - i - k edges.

We will consider two ways distinct, if there is the pair of vertexes i, j (i < j), such that first resulting graph has an edge from i to j and the second one doesn't have it.

Help Olya. As the required number of ways can be rather large, print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains three space-separated integers n, m, k (2 ≤ n ≤ 106, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).

The next m lines contain the description of the edges of the initial graph. The i-th line contains a pair of space-separated integers ui, vi (1 ≤ ui < vi ≤ n) — the numbers of vertexes that have a directed edge from ui to vi between them.

It is guaranteed that any pair of vertexes ui, vi has at most one edge between them. It also is guaranteed that the graph edges are given in the order of non-decreasing ui. If there are multiple edges going from vertex ui, then it is guaranteed that these edges are given in the order of increasing vi.

## Output Format
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

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

## Note
In the first sample there are two ways: the first way is not to add anything, the second way is to add a single edge from vertex 2 to vertex 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
In one little known, but very beautiful country called Waterland, lives a lovely shark Valerie. Like all the sharks, she has several rows of teeth, and feeds on crucians. One of Valerie's distinguishing features is that while eating one crucian she uses only one row of her teeth, the rest of the teeth are "relaxing".

For a long time our heroine had been searching the sea for crucians, but a great misfortune happened. Her teeth started to ache, and she had to see the local dentist, lobster Ashot. As a professional, Ashot quickly relieved Valerie from her toothache. Moreover, he managed to determine the cause of Valerie's developing caries (for what he was later nicknamed Cap).

It turned that Valerie eats too many crucians. To help Valerie avoid further reoccurrence of toothache, Ashot found for each Valerie's tooth its residual viability. Residual viability of a tooth is a value equal to the amount of crucians that Valerie can eat with this tooth. Every time Valerie eats a crucian, viability of all the teeth used for it will decrease by one. When the viability of at least one tooth becomes negative, the shark will have to see the dentist again.

Unhappy, Valerie came back home, where a portion of crucians was waiting for her. For sure, the shark couldn't say no to her favourite meal, but she had no desire to go back to the dentist. That's why she decided to eat the maximum amount of crucians from the portion but so that the viability of no tooth becomes negative.

As Valerie is not good at mathematics, she asked you to help her to find out the total amount of crucians that she can consume for dinner.

We should remind you that while eating one crucian Valerie uses exactly one row of teeth and the viability of each tooth from this row decreases by one.

## Input Format
The first line contains three integers n, m, k (1 ≤ m ≤ n ≤ 1000, 0 ≤ k ≤ 106) — total amount of Valerie's teeth, amount of tooth rows and amount of crucians in Valerie's portion for dinner. Then follow n lines, each containing two integers: r (1 ≤ r ≤ m) — index of the row, where belongs the corresponding tooth, and c (0 ≤ c ≤ 106) — its residual viability.

It's guaranteed that each tooth row has positive amount of teeth.

## Output Format
In the first line output the maximum amount of crucians that Valerie can consume for dinner.

## Examples
```input
4 3 18
2 3
1 2
3 6
2 3
```
```output
11
```
-----
```input
2 2 13
1 13
2 12
```
```output
13
```

Now solve the problem and return the code.