2016-2017 7th BSUIR Open Programming Contest. Final
A. Tree Orientation
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

There are different legends for tasks. They can be long or short. They can be boring or funny. They can be understandable or not. You decide: what is this.

Given an undirected tree with n vertices. Find out how many different ways you can orient the edges of the tree so that the result graph will contain exactly m sink vertices. Sink vertex is a vertex with zero outdegree.

Input

The first line of input contains two numbers n (the total number of vertices) and m (required number of sink vertices).

Each of the following n - 1 rows contains a description of the edges, i.e. its ends ui and vi.

1 ≤ n ≤ 1000
0 ≤ m ≤ n
1 ≤ ui, vi ≤ n
Output

You should output an amount of ways to orient the tree modulo 109 + 7.

Example
Input
5 2
1 2
2 3
3 4
3 5
Output
8

B. A Masterpiece
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Supercomputer Deep Thought had answered the question to life, the universe, and everything a long time back and now has nothing to do. Suddenly another question has come to him recently. One famous artist has always been looking for an approach to create an "ideal" masterpiece and has spent 42 years to find the solution. He simply has decided to ask Deep Thought about it.

This question was too simple for supercomputer and he has produced the solution right after 42 seconds since the artist came. The algorithm is designed as follows:

  1. Take any world famous painting shaped as a square. For example, you may take Leonardo da Vinci's Joconde.
  2. Make a copy of this painting. Cut it into n2 identical size square pieces. It would be even better if you have performed it on the genuine masterpiece.
  3. Assign the numbers from 1 to n2 to obtained squares.
  4. Reorder the squares in such a way to guarantee that every subset consisting n squares including indices of every row and column should have equal sum of numbers written on these squares.
  5. To complete a masterpiece it is very important to make sure that the difference of every two adjacent by side elements exceeds 1.

Deep Thought refused to provide a masterpiece generation program for a given dimension n. Therefore, you have to do it by yourself.

Input

A single line contains only one positive integer number n – number of rows and columns in the cut painting.

1 ≤ n ≤ 42
Output

In the first line output number n. In the following n lines containing n integers each should be printed matrix. The printed matrix should agree with given above constraints to form a masterpiece. If multiple solution exist, you may output any of them. If solution does not exist, you should output -1.

Examples
Input
5
Output
5
12 14 11 13 15
22 24 21 23 25
7 9 6 8 10
17 19 16 18 20
2 4 1 3 5
Input
3
Output
-1

C. Auction
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Famous yacht company "Boats, boats, boats" have decided to sell their products using so called paired auction to increase their sales amount. Only two customers are taking part in this kind of auctions and the procedure differs from classical auctions. The initial price of a yacht is 1 ruble and then during each step one of the customers is multiplying current price by a integer number from 2 to 9. The bidding process is going on while current price does not exceed n rubles, which is known in advance. Thus, customer made last bid will get the yacht for 1 ruble only and the other customer will have to pay the full yacht price n rubles, accordingly.

You are a rich man and you have decided to take part in t paired auctions. Therefore, your finance managers have to determine the outcome for each auction knowing the actual price of the yacht ni. Outcome is the chance to buy a yacht for 1 ruble if you and another customer are doing optimal bids. Furthermore, you always start the paired auction, i.e. increasing the price during the first round.

Input

First line contains positive integer t – number of paired auctions you are taking part in.

Each of the next t lines contain only one positive integer ni – actual price for each of auctions, accordingly.

1 ≤ t ≤ 42
2 ≤ ni ≤ 1018
Output

You should output exactly t strings. Each of them contains "YES" (without quotation marks) if you can buy a yacht for 1 ruble during the auction and "NO" otherwise.

Example
Input
1
42
Output
YES

D. Deck Building
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

There are n cards on the table. Each card has two numbers written on it — the card rank and the serial number. You should form a deck:

  • You take cards one by one in any order from the cards remaining on the table;
  • You are not allowed to take two cards of the same rank one after another. The first card can have any rank;
  • Starting from the second card, you need to pay one coin for each card on the table having the rank which is strictly within the range between the current card and the previous card ranks;
  • All the cards having serial number which is less than or equal to the current card serial number are removed from the cards remaining on the table after the payment;
  • Starting from the third card, the "the force direction changing" condition must be fulfilled, i.e. let us denote the current, the previous and pre-previous selected cards ranks by a, b and c. If b < min(a, c) or b > max(a, c) then the condition is fulfilled;
  • The deck forming is terminated when it's not possible to select a card from the cards remaining on the table.

Calculate the total cost in coins of all possible decks. Two decks are considered to be different if there is a card that enters one deck and does not enter another. However, different cards can have the same rank and serial number.

Input

The first line contains integer n — total amount of cards on the table .

Each of the following n rows contains two integers si (i-th card rank) and ki (i-th card serial number).

1 ≤ n ≤ 105
1 ≤ si, ki ≤ 109
Output

You are required to output a total cost in coins of all possible decks modulo 109 + 7.

Example
Input
6
8 8
5 9
9 4
3 9
3 1
7 5
Output
42

E. The secret of betting
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Hi! I'm a hardcore sports fan. Watching your favorite sports team win is an exciting moment. And it can be not only joyful, but profitable, if you know how to win bets with bookmakers. But how to predict who will win the match? That is the question…

But I’ve finally revealed the secret. All the players have all the different numbers from 1 to n on their shirts. The trick is to know a special order of n players standing during the national anthem. If |Ai - i| ≤ k for any i in range [1, n], then the game will end in victory for your favorite team. Out of kindness, the referee will tell you the number k before the match starts.

For example, k = 1 and the order of the players is (3, 4, 1, 2). Your team will definitely lose under the circumstances. But if k = 2, they will definitely win.

I have already made enough money from bookmakers, so now it’s your turn to use this trick. Count the number of winning permutations of n players for a given k.

Input

The first line contains two integers n (a number of players on a team) and k (a secret parameter you were told).

0 ≤ k ≤ 9
1 ≤ n ≤ 1010 - k
Output

You are required to output a number of winning permutations modulo 109 + 7.

Example
Input
4 2
Output
14

F. Financial Reports
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Financial analysts of "WeRRich" company are working on a current annual report. They have n data points of company's shares fluctuations sorted by time stamps in chronological order. The analysts are required to compute the most wealthy period, i.e. a consecutive non-empty time interval, which has maximum sum of fluctuations within a year period.

Unfortunately, top management of the company is not satisfied with the annual report results, hence analysts have decided to adjust the report by swapping two fluctuations in the time series. It looks like a perfect crime, but financiers are not able to develop efficient enough algorithm to perform the plan. Now they have to ask software engineers to help them out. So they are required to determine the fluctuation indices to swap and a maximum fluctuation sum, which is possible to obtain as a result.

Input

First line contains positive integer n – a number of fluctuations of shares within a financial year.

Second line contains exactly n integers ai – values of fluctuations given in chronological order.

2 ≤ n ≤ 105
|ai| ≤ 109
Output

The maximal fluctuations sum during the most wealthy period should be printed in a first line.

Second line should contain two different numbers – indices of swapped fluctuations. If multiple solution exist, you may output any of them.

Example
Input
5
1 -2 -3 4 -5
Output
5
4 2

G. Moore's Law
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

In 1965, one of the Intel corporation founders, Gordon Moore noticed that number of transistors on integrated circuit chip doubles every 24 month. Nowadays, British scientists have decided to clarify this empirical law. As a result of this research, the number of transistors can be only represented as a decimal number containing only digits 1 and 2. Thus, first generation of integrated circuits had only 2 transistors and second generation had 12 transistors, respectively. Furthermore, according to a new version of Moore's Law, for n-th generation of integrated circuit number of transistors should be a multiple of 2n. To check the British scientists' experimental results you are required to design a program, which computes number of transistors on n-th generation of integrated circuits according to a new Moore's law.

Input

A single line contains a positive integer n – considered generation of integrated circuits.

1 ≤ n ≤ 42
Output

You are required to compute number of transistors on integrated circuit chip for given generation n according to the given above constraints. The output should not exceed 10100000. If multiple answers exist, you may output any of them. If the correct number of transistors does not exist, output -1.

Examples
Input
1
Output
2
Input
2
Output
2112

H. Plagiarism
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Modern computer systems are quite advanced in plagiarism detection. Consider some text p pretending to be original and text o, which has been copied from some source. Text p is considered as a plagiarism of order k if it has several disjoint substrings of length at least k, concatenation of which is a text o. The order of substrings concatenation to text o corresponds to their order in text p.

Since plagiarism from a single source is a well known problem, engineers started development of a system determining plagiarism from multiple sources. At the very first stage of the system design many training texts are required. Therefore, during the first stage they need to generate a text, which is a plagiarism of order k of two given original texts a and b.

Input

First line contains positive integer k – order of plagiarism for a text, minimal length of which you are required to find.

Second and third lines contain strings a and b – original texts to generate a plagiarism of order k.

All the strings consist of lower case Latin symbols.

1 ≤ k ≤ 100
1 ≤ |a|, |b| ≤ 100
Output

The minimal length of plagiarism of order k text for original texts a and b should be printed in a single line.

Examples
Input
2
abaaa
babaa
Output
6
Input
3
abacabadabacaba
bababanana
Output
19

I. Number builder
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

This will be a simple task. Even more. We like to generate different numbers, we think and you will like it. You are given an integer s. Try to generate the maximum number with the sum of digits equal to s, which does not contain zeros, and also any adjacent digits are not equal.

Input

The single line contains the number s.

1 ≤ s ≤ 42
Output

Output a single number containing the answer to the problem.

Examples
Input
1
Output
1
Input
2
Output
2

J. Find a triangle
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Someone has drawn a non-degenerate triangle with integer coordinates of vertexes on a chequered piece of paper. However, he did not tell anyone, where this triangle is located. Therefore, you are very curious about it. Fortunately, this guy agreed to answer your questions about it. You have to tell him coordinates of two different points (x1, y1) and (x2, y2) and he will draw a directed line and will tell you whether it crosses a triangle or not. If a line crosses the triangle this guy will tell you if the triangle is located on the left or on the right relative to the line.

The answer to each of the questions can be described as follows.

  • '+' the triangle is fully located on the right relative to the line.
  • '-' the triangle is fully located on the left relative to the line.
  • 'X' line crosses the triangle at least in one point
Someone will be very bored if you ask him more than 600 questions and will refuse to answer afterwards.
Input

After each request you will be given a line, which can be one of three possible characters ('-', '+' or 'X').

Output

To make a request you have to print a line according to a following format. All coordinates must be integer. Q x1 y1 x2 y2.

|x1|, |x2|, |y1|, |y2| ≤ 42 × 104

If you figured out the final location of the triangle, you have to print the line in a following format A x1 y1 x2 y2 x3 y3. If you guessed the correct location of the triangle, the order of points does not affect the correctness of your answer.

|x1|, |x2|, |x3|, |y1|, |y2|, |y3| ≤ 105

Please note, that you have to print a new line character after each request and flush the buffer. For example, you can do it using fflush(stdout) in C++, System.out.flush() in Java, and flush(output) in Pascal.