2017-2018 8th BSUIR Open Programming Contest. Final
A. One-time passwords
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nowadays two-factor authentication, when user is required to use primary password and one or more one-time passwords, is becoming more widespread. Consider one of possible ways to generate such kind of passwords.

Let F(Q) be a number of positive integers not greater than Q, which can be represented as 2x - 2y when x, y are non-negative integer numbers. Consider all possible numbers Q such as F(Q) = N and sort them in ascending order by number of one-bits in their binary representation. If two numbers have the same number of one-bits in binary representation, they should be compared by their values. Proposed algorithm chooses K-th number in this sorted sequence.

You are required to find one-time passwords for T authentication sessions.

Input

First line contains an integer number T — number of authentication sessions. Next T lines contain two numbers Ni and Ki each — parameters of one-time password generation algorithms.

1 ≤ T ≤ 105
1 ≤ Ni, Ki ≤ 1018
Output

T lines containing one integer number each — one-time password for corresponding authentication session. Each password should be computed in modulo 109 + 7. If it is impossible to generate one time password, -1 should be printed.

Example
Input
1
16 10
Output
42

B. Even answer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vanya has an array of N integers a1, a2, ..., aN. He wants to calculate the sum of these numbers. But he also wants the sum to be non-negative, even and minimum possible at the same time. So, he decided to multiply one of the numbers by any integer before adding the numbers.

Help Vanya to get the sum he wants.

Input

The first line of input contains an integer N  — the size of the array A.

In the next line there are N integers a1, a2, ..., aN  — the elements of the array A.

1 ≤ N ≤ 105
 - 109 ≤ ai ≤ 109
Output

Output a single integer — the required sum. If there is no answer then output -1.

Examples
Input
2
7 3
Output
4
Input
2
7 10
Output
10
Input
3
42 43 86
Output
42

C. Kingdom Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, King of Bandiaterra Barbato started thinking how to split his kingdom between two sons Philip and Ferdinand. Barbato's property can be represented by N castles, which can be denoted as integer coordinate points (Xi, Yi). Since, king equally loves his sons, he decided to perform the partition according to the Bandiaterra Fairness Code.

To perform the separation, straight line parallel to Y-axis should be drawn. This line contains point (X, 0). Castles located on the west of the border line (Xi ≤ X) will be inherited by Philip and the ones on the east (X < Xi) – to Ferdinand. Eventually, each brother will have a city, which can be represented as a convex hull of castles inherited by Philip and Ferdinand, accordingly. According to the Bandiaterra Fairness Code, partition is more fair if absolute value of difference between Philip's and Ferdinand's city areas is as close as possible to S – sacral number of Bandiaterra.

Barbato conducted Bandiaterra's council of elders to decide on exact location of the border line and record it to his testament.

Input

First line contains two integer numbers N and S — number of castles and sacral number, accordingly.

Next N lines each contain two integer numbers Xi and Yi — coordinates of each castle. There are no castles with same coordinates. Area of an empty city which has no castles is zero.

1 ≤ N ≤ 100 000
0 ≤ S ≤ 1 000 000 000
|Xi|, |Yi| ≤ 10 000
Output

Single line should contain one number — absolute value between city areas, which is as close as possible to the sacral number of Bandiaterra. If there is more than one possible border lines, output that, which makes absolute difference between city areas as low as possible. Absolute and relative error of your answer should not exceed 10 - 4.

Example
Input
9 31
8 5
-3 1
1 -1
-4 -3
-2 -9
3 -4
9 0
1 7
-7 2
Output
42.0000

D. Badroadville mayoral election
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today people discuss elections at all cross-roads. Scandals, intrigues, investigations, disclosures. In our town called Badroadville it's also time to elect a mayor. And in an attempt to avoid the usual infighting, we decided to change the concept radically: the winner will be determined by deed, not by word. And a deed will be very important — it will be road construction.

There are several districts in Badroadville, where N houses are located. Houses are connected by M bidirectional roads. There are not many roads, as always. The roads between the houses are not duplicated, and there are no roads looping and leading to the same house. There is always at least one path between any pair of houses in a district (by the way, a district can consist of the only house). But there are no roads from one district to another, so unlucky town residents have to wade knee-deep through the mud.

The candidates running to be the next mayor will build one road between two houses in turns, and the one, who first turns the city into one big and happy district, will become a new mayor of Badroadville.

We suggest you take part in the election race with our candidate and prove that you are ready to rule the town and bring it to the better tomorrow!

As a welcome guest, you can choose who will be the first to start the construction of roads.

Input

The first line contains two integers N and M — the numbers of houses and roads in the town, respectively.

The next M lines describe roads as Ui Vi — the numbers of houses connected by this road.

2 ≤ N ≤ 200
0 ≤ M ≤ N * (N - 1) / 2
1 ≤ Ui, Vi ≤ N
Interaction

Once you've received the current Badroadville scheme of roads, you need to print one of the numbers: "1" or "2" depending on your wish to start the election race the first or the second, respectively.

Now, if it's your turn, you need to print two integers U V — the numbers of houses that you are going to connect by the road. If it is your opponent's turn now, you get two integers U V   — the numbers of houses that your opponent connected by the road.

You must correctly finish the election race when there remains just one district in the town or when the opponent send you two zeroes "0 0".

Please don't forget to output a newline character and to clear a buffer. For example, you may use fflush(stdout) in C++, System.out.flush() in Java, and flush(output) in Pascal.

Examples
Input
4 0
3 4
Output
1
1 2
1 3
Input
5 1
3 5
2 3
0 0
Output
1
1 2
1 5

E. Sweet motivation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is nothing the Little Programmer enjoys better than calculation. At the same time, he doesn’t really enjoy reading books, which he must read in Literature classes. Especially if they are thick. Especially if they are very very fat. That’s why he decided to ignore reading a book containing N pages and put up with bad grade. But the literature teacher was not ready to give up, none of his students had escaped acquaintance with this productive writer. To encourage the Little Programmer’s interest, he invented a rule. After every page read, the student gets just as many sweets as the absolute value of differences of the sums of the digits in the numbers of the previous and the next pages. Such a sweet motivation radically changed the situation: the book was read from the first to the last page immediately. Now all that remains is to find out how many sweets the Little Programmer can receive for such a feat. He has already counted, but the teacher needs your help.

Input

The first and only line contains the number of pages in the book. It’s the integer N.

1 ≤ N < 10100 000
Output

The single line contains the required number of sweets. There are a lot of them, so print it modulo 109 + 7.

Example
Input
29
Output
42

F. Sort hacking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vova claims that he came up with a new kind of sorting algorithm. His algorithm differs in that it can sort, according to Vova, any permutation of length N while doing the same comparisons for any permutation. In total, it makes M comparisons, where the i-th comparison occurs over the numbers at positions xi and yi respectively. If at the time of comparison the number at the position xi turned out to be larger, then he swaps them.

Vanya was skeptical about the discovery of Vova. He is sure that there will be such permutations that Vova's sort can not order in ascending order. Help Vanya determine the number of such permutations.

Input

The first line contains two integers N and M — the size of the permutation and the number of comparisons in the Vova's sort.

The following M lines contain comparisons. The i-th row contains two integers xi and yi — the positions of the compared elements.

1 ≤ N ≤ 15
1 ≤ M ≤ 200
1 ≤ xi, yi ≤ N
Output

In a single line output one integer — the number of permutations that Vova's sort can not order in ascending order.

Examples
Input
3 3
1 2
2 3
1 3
Output
2
Input
2 1
1 2
Output
0
Input
2 1
2 1
Output
2
Note

In the first test case, the following permutations are suitable: [3, 2, 1], [2, 3, 1].

In the second test case, the following permutations are suitable: [1, 2], [2, 1].

G. A Bishop's Journey
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once upon a time there was an unusual bishop who lived on an unusual chess board. The board was unusual because it was of an arbitrary size N × M. The bishop was unusual because it was placed in the corner field of the board. It stood there for a long time and got bored. And so it decided to go on a journey wherever its eyes lead him. As is well known, the eyes of bishops lead them diagonally. Having reached the edge of the board, the bishop turned through 90 degrees and continued to move. And so on. The bishop had stopped only when again got into some (first available) corner.

How many unique fields did it visit during his journey around the N × M board?

Input

The first and only line contains integers N and M — the chess board sizes.

1 < N ≤ 1018
1 < M ≤ 1018
Output

The single line contains the only number —required number of visited fields by prime modulo 1018 + 9.

Example
Input
15 22
Output
42

H. Tourist Agency
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For the benefit of their customers, tourist agency "42 best journeys" has chosen N cities, which are connected by N - 1 direct flights and any two of them are connected by air (direct flights and flights with stop-overs). To promote their service, agency has chosen contextual advertising. To avoid annoying repeating ads, provider is only showing unique tours to their customers. Tour includes visiting K (K ≤ N) cities, which are connected by K - 1 direct flights and any two of them are connected by air. Tours are considered unique if one of them has particular city and the second one doesn't.

Head of agency has developed an advertisement strategy and started thinking of their expenses. Provider of contextual ad is charging one US dollar for each advertisement and one Belarusian rouble for each city included in tour. Accountant team is now required to compute final amount of money to be paid. All possible unique tours (ads) have been shown to the customers during this campaign exactly once.

Input

First line contains one integer number N — number of chosen cities. Next N - 1 lines contain two integer numbers Ui and Vi each — indices of cities which are connected by direct flight.

1 ≤ N ≤ 105
1 ≤ Ui, Vi ≤ N
Output

Single line should have two integer numbers — amount of money in US dollars and Belarusian roubles to be paid by agency. Contextual Ads provider bill agency by amount modulo 109 + 7 as a part of their discounts policy.

Example
Input
5
4 2
2 5
3 2
5 1
Output
17 42

I. Permutations again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence Ai consisting of N integers. Find the number of pairs (L, R) for which the subsegment {AL, AL + 1, ..., AR} is a permutation of R - L + 1 numbers.

A permutation of K numbers is any sequence of numbers from 1 to K, where each element occurs only once.

Input

The first line contains number N — a sequence length. The second line contains N integers — sequence Ai elements.

1 ≤ N ≤ 106
1 ≤ Ai ≤ N
Output

Print the number of pairs (L, R), fulfilling the condition.

Example
Input
3
3 1 2
Output
3

J. Restore the sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vanya constructed a sequence fi according to the following rule:

  1. f0 = x, f1 = y;
  2. fi = fi - 1 + fi - 2, i > 1.

Unfortunately, Vanya lost this sequence. However, he memorized one number N, which belongs to this sequence. He also remembers that all elements of the sequence are non-negative integers.

Help Vanya find such x and y, by which he can restore the sequence. Vanya understands that there can be many answers, so he wants the value of x + y to be as small as possible, and in case there are several such pairs, x should be the minimum possible.

Input

The single line contains one integer N — the number that Vanya memorized.

1 ≤ N ≤ 106
Output

In the single line output two integers x and y — the initial parameters of the sequence.

Examples
Input
42
Output
0 2
Input
19
Output
3 2

K. Slogan
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The company «42 shades of green» consists of N departments. To increase team spirit, the company's management asked each department to come up with a slogan, which is a string consisting of at least K lower-case Englsih characters. To assess the work of all departments of the company it was decided to choose a lexicographically minimal string that would contain at least one substring of length K from the slogans of each of the departments as a common slogan. Since the budget for printing a slogan is limited, it should not contain unnecessary characters. So let's consider for each department slogan the first occurrence of any substring of length K in the general slogan and if there is a symbol that is not covered by these occurrences, then such symbol is unnecessary and it needs to be deleted.

Help the company «42 shades of green» find their corporate slogan from the specified slogans of departments.

Input

The first line contains two integers N and K — number of departments and length of substrings.

Each following N lines contain string Si — slogan of the i-th department.

1 ≤ N ≤ 1000
1 ≤ K ≤ 100
K ≤ |Si|
Output

In the only line, output the corporate slogan of the company.

Examples
Input
5 3
abacabada
abada
dada
cadaca
adac
Output
abaacaada
Input
5 3
abacabada
abada
daada
cadaca
adac
Output
aada