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
Vasily the bear has two favorite integers n and k and a pencil. Besides, he's got k jars with different water color paints. All jars are numbered in some manner from 1 to k, inclusive. The jar number i contains the paint of the i-th color.

Initially the bear took a pencil and drew four segments on the coordinate plane. All of them end at point (0, 0). They begin at: (0, 2n), (0,  - 2n), (2n, 0), ( - 2n, 0). Then for each i = 1, 2, ..., n, the bear drew two squares. The first square has the following vertex coordinates: (2i, 0), ( - 2i, 0), (0,  - 2i), (0, 2i). The second square has the following vertex coordinates: ( - 2i - 1,  - 2i - 1), ( - 2i - 1, 2i - 1), (2i - 1,  - 2i - 1), (2i - 1, 2i - 1). After that, the bear drew another square: (1, 0), ( - 1, 0), (0,  - 1), (0, 1). All points mentioned above form the set of points A.

The sample of the final picture at n = 0

The sample of the final picture at n = 2

The bear decided to paint the resulting picture in k moves. The i-th move consists of the following stages:

1. The bear chooses 3 distinct points in set А so that any pair of the chosen points has a segment on the picture between them. The chosen points and segments mark the area that mustn't contain any previously painted points.
2. The bear paints the area bounded by the chosen points and segments the i-th color.

Note that after the k-th move some parts of the picture can stay unpainted.

The bear asked you to calculate, how many distinct ways there are to paint his picture. A way to paint the picture is a sequence of three-element sets of points he chose on each step. Two sequences are considered distinct if there is such number i (1 ≤ i ≤ k), that the i-th members of these sequences do not coincide as sets. As the sought number can be rather large, you only need to calculate the remainder after dividing it by number 1000000007 (109 + 7).

## Input Format
The first line contains two integers n and k, separated by a space (0 ≤ n, k ≤ 200).

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

## Examples
```input
0 0
```
```output
1
```
-----
```input
0 1
```
```output
8
```
-----
```input
0 2
```
```output
32
```
-----
```input
1 1
```
```output
32
```

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 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: 2.0 seconds
Memory limit: 64.0 MB

# Problem
Today the «Z» city residents enjoy a shell game competition. The residents are gathered on the main square to watch the breath-taking performance. The performer puts 3 non-transparent cups upside down in a row. Then he openly puts a small ball under one of the cups and starts to shuffle the cups around very quickly so that on the whole he makes exactly 3 shuffles. After that the spectators have exactly one attempt to guess in which cup they think the ball is and if the answer is correct they get a prize. Maybe you can try to find the ball too?

## Input Format
The first input line contains an integer from 1 to 3 — index of the cup which covers the ball before the shuffles. The following three lines describe the shuffles. Each description of a shuffle contains two distinct integers from 1 to 3 — indexes of the cups which the performer shuffled this time. The cups are numbered from left to right and are renumbered after each shuffle from left to right again. In other words, the cup on the left always has index 1, the one in the middle — index 2 and the one on the right — index 3.

## Output Format
In the first line output an integer from 1 to 3 — index of the cup which will have the ball after all the shuffles.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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: 2.0 seconds
Memory limit: 64.0 MB

# Problem
After a terrifying forest fire in Berland a forest rebirth program was carried out. Due to it N rows with M trees each were planted and the rows were so neat that one could map it on a system of coordinates so that the j-th tree in the i-th row would have the coordinates of (i, j). However a terrible thing happened and the young forest caught fire. Now we must find the coordinates of the tree that will catch fire last to plan evacuation.

The burning began in K points simultaneously, which means that initially K trees started to burn. Every minute the fire gets from the burning trees to the ones that aren’t burning and that the distance from them to the nearest burning tree equals to 1.

Find the tree that will be the last to start burning. If there are several such trees, output any.

## Input Format
The first input line contains two integers N, M (1 ≤ N, M ≤ 2000) — the size of the forest. The trees were planted in all points of the (x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M) type, x and y are integers.

The second line contains an integer K (1 ≤ K ≤ 10) — amount of trees, burning in the beginning.

The third line contains K pairs of integers: x1, y1, x2, y2, ..., xk, yk (1 ≤ xi ≤ N, 1 ≤ yi ≤ M) — coordinates of the points from which the fire started. It is guaranteed that no two points coincide.

## Output Format
Output a line with two space-separated integers x and y — coordinates of the tree that will be the last one to start burning. If there are several such trees, output any.

## Examples
```input
3 3
1
2 2
```
```output
1 1
```
-----
```input
3 3
1
1 1
```
```output
3 3
```
-----
```input
3 3
2
1 1 3 3
```
```output
2 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 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: 2.0 seconds
Memory limit: 64.0 MB

# Problem
Once upon a time DravDe, an outstanding person famous for his professional achievements (as you must remember, he works in a warehouse storing Ogudar-Olok, a magical but non-alcoholic drink) came home after a hard day. That day he had to drink 9875 boxes of the drink and, having come home, he went to bed at once.

DravDe dreamt about managing a successful farm. He dreamt that every day one animal came to him and asked him to let it settle there. However, DravDe, being unimaginably kind, could send the animal away and it went, rejected. There were exactly n days in DravDe’s dream and the animal that came on the i-th day, ate exactly ci tons of food daily starting from day i. But if one day the animal could not get the food it needed, it got really sad. At the very beginning of the dream there were exactly X tons of food on the farm.

DravDe woke up terrified...

When he retold the dream to you, he couldn’t remember how many animals were on the farm by the end of the n-th day any more, but he did remember that nobody got sad (as it was a happy farm) and that there was the maximum possible amount of the animals. That’s the number he wants you to find out.

It should be noticed that the animals arrived in the morning and DravDe only started to feed them in the afternoon, so that if an animal willing to join them is rejected, it can’t eat any farm food. But if the animal does join the farm, it eats daily from that day to the n-th.

## Input Format
The first input line contains integers n and X (1 ≤ n ≤ 100, 1 ≤ X ≤ 104) — amount of days in DravDe’s dream and the total amount of food (in tons) that was there initially. The second line contains integers ci (1 ≤ ci ≤ 300). Numbers in the second line are divided by a space.

## Output Format
Output the only number — the maximum possible amount of animals on the farm by the end of the n-th day given that the food was enough for everybody.

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

## Note
Note to the first example: DravDe leaves the second and the third animal on the farm. The second animal will eat one ton of food on the second day and one ton on the third day. The third animal will eat one ton of food on the third day.

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
Levko loves tables that consist of n rows and n columns very much. He especially loves beautiful tables. A table is beautiful to Levko if the sum of elements in each row and column of the table equals k.

Unfortunately, he doesn't know any such table. Your task is to help him to find at least one of them.

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

## Output Format
Print any beautiful table. Levko doesn't like too big numbers, so all elements of the table mustn't exceed 1000 in their absolute value.

If there are multiple suitable tables, you are allowed to print any of them.

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

## Note
In the first sample the sum in the first row is 1 + 3 = 4, in the second row — 3 + 1 = 4, in the first column — 1 + 3 = 4 and in the second column — 3 + 1 = 4. There are other beautiful tables for this sample.

In the second sample the sum of elements in each row and each column equals 7. Besides, there are other tables that meet the statement requirements.

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
Levko loves permutations very much. A permutation of length n is a sequence of distinct positive integers, each is at most n.

Let’s assume that value gcd(a, b) shows the greatest common divisor of numbers a and b. Levko assumes that element pi of permutation p1, p2, ... , pn is good if gcd(i, pi) > 1. Levko considers a permutation beautiful, if it has exactly k good elements. Unfortunately, he doesn’t know any beautiful permutation. Your task is to help him to find at least one of them.

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

## Output Format
In a single line print either any beautiful permutation or -1, if such permutation doesn’t exist.

If there are multiple suitable permutations, you are allowed to print any of them.

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

## Note
In the first sample elements 4 and 3 are good because gcd(2, 4) = 2 > 1 and gcd(3, 3) = 3 > 1. Elements 2 and 1 are not good because gcd(1, 2) = 1 and gcd(4, 1) = 1. As there are exactly 2 good elements, the permutation is beautiful.

The second sample has no beautiful permutations.

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
Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). You've got a number k and an array a containing n numbers. Find out how many k-good numbers are in a (count each number every time it occurs in array a).

## Input Format
The first line contains integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 9). The i-th of the following n lines contains integer ai without leading zeroes (1 ≤ ai ≤ 109).

## Output Format
Print a single integer — the number of k-good numbers in a.

## Examples
```input
10 6
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560
1234560
```
```output
10
```
-----
```input
2 1
1
10
```
```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 have array a1, a2, ..., an. Segment [l, r] (1 ≤ l ≤ r ≤ n) is good if ai = ai - 1 + ai - 2, for all i (l + 2 ≤ i ≤ r).

Let's define len([l, r]) = r - l + 1, len([l, r]) is the length of the segment [l, r]. Segment [l1, r1], is longer than segment [l2, r2], if len([l1, r1]) > len([l2, r2]).

Your task is to find a good segment of the maximum length in array a. Note that a segment of length 1 or 2 is always good.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains integers: a1, a2, ..., an (0 ≤ ai ≤ 109).

## Output Format
Print the length of the longest good segment in array a.

## Examples
```input
10
1 2 3 5 8 13 21 34 55 89
```
```output
10
```
-----
```input
5
1 1 1 1 1
```
```output
2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Vasily the Programmer loves romance, so this year he decided to illuminate his room with candles.

Vasily has a candles.When Vasily lights up a new candle, it first burns for an hour and then it goes out. Vasily is smart, so he can make b went out candles into a new candle. As a result, this new candle can be used like any other new candle.

Now Vasily wonders: for how many hours can his candles light up the room if he acts optimally well? Help him find this number.

## Input Format
The single line contains two integers, a and b (1 ≤ a ≤ 1000; 2 ≤ b ≤ 1000).

## Output Format
Print a single integer — the number of hours Vasily can light up the room for.

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

## Note
Consider the first sample. For the first four hours Vasily lights up new candles, then he uses four burned out candles to make two new ones and lights them up. When these candles go out (stop burning), Vasily can make another candle. Overall, Vasily can light up the room for 7 hours.

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
Many countries have such a New Year or Christmas tradition as writing a letter to Santa including a wish list for presents. Vasya is an ordinary programmer boy. Like all ordinary boys, he is going to write the letter to Santa on the New Year Eve (we Russians actually expect Santa for the New Year, not for Christmas).

Vasya has come up with an algorithm he will follow while writing a letter. First he chooses two strings, s1 anf s2, consisting of uppercase English letters. Then the boy makes string sk, using a recurrent equation sn = sn - 2 + sn - 1, operation '+' means a concatenation (that is, the sequential record) of strings in the given order. Then Vasya writes down string sk on a piece of paper, puts it in the envelope and sends in to Santa.

Vasya is absolutely sure that Santa will bring him the best present if the resulting string sk has exactly x occurrences of substring AC (the short-cut reminds him оf accepted problems). Besides, Vasya decided that string s1 should have length n, and string s2 should have length m. Vasya hasn't decided anything else.

At the moment Vasya's got urgent New Year business, so he asks you to choose two strings for him, s1 and s2 in the required manner. Help Vasya.

## Input Format
The first line contains four integers k, x, n, m (3 ≤ k ≤ 50; 0 ≤ x ≤ 109; 1 ≤ n, m ≤ 100).

## Output Format
In the first line print string s1, consisting of n uppercase English letters. In the second line print string s2, consisting of m uppercase English letters. If there are multiple valid strings, print any of them.

If the required pair of strings doesn't exist, print "Happy new year!" without the quotes.

## Examples
```input
3 2 2 2
```
```output
AC
AC
```
-----
```input
3 3 2 2
```
```output
Happy new year!
```
-----
```input
3 0 2 2
```
```output
AA
AA
```
-----
```input
4 3 2 1
```
```output
Happy new year!
```
-----
```input
4 2 2 1
```
```output
Happy new year!
```

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
Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any $$a,b\in S$$ (a can be equal to b), $$(a \ xor \ b) \in S$$. Where operation xor means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than k. The answer can be very large, so print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains an integer k (0 ≤ k ≤ 109).

## Output Format
Print a single integer — the number of required sets modulo 1000000007 (109 + 7).

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

## Note
In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 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
Teacher thinks that we make a lot of progress. Now we are even allowed to use decimal notation instead of counting sticks. After the test the teacher promised to show us a "very beautiful number". But the problem is, he's left his paper with the number in the teachers' office.

The teacher remembers that the "very beautiful number" was strictly positive, didn't contain any leading zeroes, had the length of exactly p decimal digits, and if we move the last digit of the number to the beginning, it grows exactly x times. Besides, the teacher is sure that among all such numbers the "very beautiful number" is minimal possible.

The teachers' office isn't near and the teacher isn't young. But we've passed the test and we deserved the right to see the "very beautiful number". Help to restore the justice, find the "very beautiful number" for us!

## Input Format
The single line contains integers p, x (1 ≤ p ≤ 106, 1 ≤ x ≤ 9).

## Output Format
If the teacher's made a mistake and such number doesn't exist, then print on a single line "Impossible" (without the quotes). Otherwise, print the "very beautiful number" without leading zeroes.

## Examples
```input
6 5
```
```output
142857
```
-----
```input
1 2
```
```output
Impossible
```
-----
```input
6 4
```
```output
102564
```

## Note
Sample 1: 142857·5 = 714285.

Sample 2: The number that consists of a single digit cannot stay what it is when multiplied by 2, thus, the answer to the test sample is "Impossible".

Now solve the problem and return the code.