2017-2018 8th BSUIR Open Programming Contest. Semifinal
A. BSUIR Open
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

— And what if you make the task about BSUIR Open, where you need to find substring BSUIR Open?

— No, it's very simple.

— Indeed!

You are given a string s consisting only of digits and capital letters of the English alphabet. You can choose some characters from this string and make a new one from the chosen symbols. Determine how many ways you can get the string «BSUIROPEN» (without quotation marks). Two ways are considered different if there is such an index i that the i-th character of the string was selected in only one of the ways.

Input

You are given a single string s (1 ≤ |s| ≤ 1 000) — the original string, consisting only of digits and capital letters of the English alphabet.

Output

Print a single number — the number of ways to get the string "BSUIROPEN". Since the answer may be too large, print it modulo 109 + 7.

Examples
Input
BSUIROPEN2018
Output
1
Input
BOSOQIVBONEOMOPTURSOCOS
Output
42

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

You work in a team consisting of n people. According to tradition, everybody brings pizza as a birthday treat. If the birthday falls on non-working days(Saturdays and Sundays), the treat is postponed to Monday. You decided to find out one interesting fact. How often can days when pizza is served by several people (at least two) at once happen? Namely, you want to find the mathematical expectation of the number of such days in 2019. Just to let you know: the first of January in 2019 falls on Tuesday. Assume that each day of the year (excluding February, 29th) is equally probable for a birthday and birthdays are independent. The probability of being born on February, 29th is zero.

Input

The only line contains one integer n (1 ≤ n ≤ 200).

Output

You are required to output a real number — the answer to the problem. Absolute or relative error should not exceed 10 - 9.

Examples
Input
1
Output
0.000000000000
Input
2
Output
0.005081628823

C. Good subset
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call set X good, if XOR-sum of all elements is 42.

You have a queue (initially empty). n operations of two types are performed:

  1. add element to the end of the queue;
  2. extract element from the beginning of the queue;

You have to answer after each operation: can we pick a good subset from the queue, or not.

Input

The first line contains one integer n (1 ≤ n ≤ 100 000) — number of queries.

Next n lines contain operations. Operation of the first type is described in format '+ x', where x (0 ≤ x ≤ 42) — the number you have to add to the queue. Operation of the second type is written as character '-'.

Output

Print n lines. In each line print 'Yes' (if it is possible to pick a good subset from the queue), or 'No' otherwise.

Examples
Input
2
+ 42
-
Output
Yes
No
Input
5
+ 2
+ 8
+ 32
+ 11
-
Output
No
No
Yes
Yes
No

D. Friends rescue
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once, during the evening walk through the forest, the boy Vova came to the river and saw that his friend Vanya was stuck on the other shore. Vova needs to save his friend, because he can not swim! There are n × (n + 1) islands in the river in the form of a grid. However, there are no bridges between them! There on the shore Vova met an evil wizard Zedikus, who agreed to help him only if Vova solves one difficult task. Vova needs to calculate the number of ways to build bridges so that there is at least one way from one shore to another. Help Vova solve this problem. Vova is allowed to build bridges only between neighboring islands.

More formally, each island has coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ n + 1), where r is the line number, and c — column number. If the island has coordinates (r, c), then the neighboring islands have coordinates (r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1), if any exist. The islands that are in the first and last column, that is the islands with coordinates (r, c), where (that is, c is equal to either 1, or n + 1), are already connected to the shores.

The way from one shore to another is a sequence of islands (r1, c1), (r2, c2), ..., (rk, ck) such that for each i (1 ≤ i < k) there is a bridge between the islands (ri, ci) and (ri + 1, ci + 1), also the island (r1, c1) is in the first column (c1 = 1), and the island (rk, ck) is in the last column (ck = n + 1).

Two ways to build bridges are considered different if there is such a bridge that in one way it is built, and in another there is not. For a better understanding, see the illustration of one way to build bridges.

You can see two shores described in the problem statement on the picture. The left shore is denoted as L, and the right one as R. Green circles depict the islands. Rounded rectangles depict the bridges. As can be seen, the shown bridge configuration contains the path between the left and the right shores. As a reminder, the bridges between the left shore L and the left column of the islands are present initially. Same thing goes for the right bank R and the right column of islands. rows and columns arrows correspond to the coordinate axes for rows and columns
Input

The only line of input contains a single integer n (1 ≤ n ≤ 42) — the dimension of the grid of islands.

Output

Output a single integer — the answer to the task modulo 109 + 7.

Examples
Input
1
Output
1
Input
42
Output
37237670

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

You are given a string s consisting only of digits "1"-"9", characters "a"-"z", "*" and "=" representing the equation. The equation contains only multiplication operations (symbol "*"), positive integers less than 10 and unknown variables. Variables can only be located on the left side of the equation, may occur more than once, and their names are lowercase letters of the English alphabet.

If, instead of unknown variables, you substitute some positive integers so that the result of operations on the left side of the equation equals to the result on the right side, then this set of numbers is called the solution of this equation.

You need to determine how many solutions this equation has. Two solutions are considered different if there is at least one variable present in the equation, the value of which is different.

Input

You are given a single string s (|s| ≤ 1 000) — the original equation. The string has exactly one character "=".

It is guaranteed that at least one unknown variable is present in the equation.

Output

In a single line print one integer — the number of solutions of this equation modulo 109 + 7.

Print "-1" if the equation has an infinite number of solutions.

Examples
Input
a*b=4*2
Output
4
Input
x*y*1=7*9*8*8
Output
42
Note

All solutions for the equation from the first example:

  1. a = 1, b = 8
  2. a = 2, b = 4
  3. a = 4, b = 2
  4. a = 8, b = 1

F. The closest subsequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array A consisting of n integers, and some number k. You are required to find such a subsequence of A that its median m will be as close as possible to the number k, i.e. |m - k| is minimal, and this subsequence has maximum length among all such subsequences.

The median of the array X of length len is the number in the array X (xi ≤ xi + 1) at position , when array is sorted in the nondecreasing order. Let us assume that the array X indices start from 1.

Input

The first line contains two integers n and k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 109) — the array A size and the number, which is meant to be the closest to the median, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — array A elements.

Output

The first line contains one integer l (1 ≤ len ≤ n) — the subsequence size.

The second line contains len integers p1, p2, ..., plen (1 ≤ pi ≤ n, pi < pi + 1) — the indices of the array A elements included in this subsequence.

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

G. Digital characteristic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The digital characteristic of number n is a function f(n) such that:

where g(n) — the sum of the digits of the decimal representation of a number n.

Vanya has already learned how to quickly calculate a digital characteristic for significantly large numbers in the mind, so he decided to show this skill to all participants of the BSUIR Open 2018. The participants didn't really like his bragging, so they offered him to calculate the digital characteristic for a very large number. The number was so huge that it was impossible to write it down on a paper.

Instead of the number itself, Vanya received its description which could help him to restore this number. Description consists of four numbers a, b, m and k. To get the initial number, Vanya must first generate k numbers ai such that for i > 1, . The received numbers he must write on a piece of paper in the reversed order, thus having received one large number. Finally he must find a digital characteristic for this number.

Now it remains to learn how to check the answer. Write a program that will determine the digital characteristic according to a given description of the number.

Input

The first line contains an integer t (1 ≤ t ≤ 10 000) — an amount of numbers, for which is needed to calculate digital characteristic.

Each of the next t lines contains description of a number. Each description consists of four integers a, b, m and k (0 ≤ a, b ≤ 109, 2 ≤ m ≤ 109 + 7, 1 ≤ k ≤ 109) — number generation parameters.

It is guaranteed that the numbers restored from those descriptions do not contain leading zeros. Note that the 0 number does not contain leading zeros.

Output

Print t lines. For each line print ans (0 ≤ ans ≤ 9) — digital characteristic of appropriate number.

Example
Input
4
1 1 10 5
4 5 7 8
1 2 3 4
42 42 2018 18
Output
6
7
4
9
Note

According to the first description the number is 54321. Its digital characteristic equals f(54321) = f(15) = f(6) = 6.

According to the fourth description the number is 7567146726305885465044624203783362942522101681268442.

H. Large and even
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let f(x) be the greatest even divisor of x or 0, if there is no such divisor.

You are given n queries li, ri. For each of them you have to find .

Input

The first line contains one integer n (1 ≤ n ≤ 105) — the number of queries.

Each line of n subsequent lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ 105) — the description of i-th request.

Output

Print n integers. On i-th line print one integer — the answer for the i-th query.

Examples
Input
1
2 12
Output
42
Input
2
1 42
42 45
Output
462
86

I. Happy triangles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are non-degenerate obtuse triangles where shortest sides differ by no more than q times from each other. Let us call them happy triangles. Find the number of happy triangles that can be formed with angles at the indicated points for the given set of points.

Input

The first line contains two numbers n and q (1 ≤ n ≤ 1 000, 1 ≤ q ≤ 30 000) — the number of points and the factor for the sides comparison respectively. The factor q is given with exactly two decimal places.

Each of the following n rows contains two integers xi yi (|xi|, |yi| ≤ 104) — coordinates of the i-th point.

It is guaranteed that any two given points are distinct and that for any triple of different points A B C the condition |D(A, B) - D(A, C) * Q| > 10 - 6 is fulfilled. D(A, B) is Euclidean distance between points A and B.

Output

A single line contains the number of happy triangles.

Examples
Input
6 2.01
0 2
2 4
-1 3
0 0
1 3
1 2
Output
6
Input
9 2.64
10 -7
0 -6
-1 8
9 -3
-1 10
-3 -1
9 9
-1 -5
4 -3
Output
42

J. Vova, who doesn't know
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vova always wants to learn something new. A lot of things he asks Lesha. This time Lesha gave him the following task...

He was given an array of n integers a1, a2, ..., an. It is necessary to find a permutation p such that will be maximal. Vova has not yet come up with a solution, but you got a chance to come up with a solution faster than him.

Recall that the operation , it is also XOR, which is exclusive OR. This operation corresponds to the operator ^ in programming languages C++ and Java. In the Pascal language, the operator xor is responsible for this operation. For numbers 5 and 3, the result of the operation will be: .

Input

The first line of input contains an integer n (1 ≤ n ≤ 8) — the size of the array A.

In the next line there are n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array A.

Output

In a single line output n integers p1, p2, ..., pn (1 ≤ pi ≤ n) — permutation at which the maximum XOR-sum of the array is reached. We recall that all elements of the permutation are different. If there are several correct answers, you can output any of them.

Example
Input
4
21 2 2018 42
Output
2 4 1 3

K. A Boring Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While boring neighbors' children play boring football outdoors, little Jim plays with his own precious tree, which consists of exactly n vertices. Jim puts a small token onto some vertex S. Game ends as soon as the token reaches special vertex F. Obviously, to end the game token should be moved somehow (for the most dreadfully meticulous our readers it should be noted, that S and F never coincide). Any sequence of token's moves, which resembles any other sequence, which Jim saw before, is considered to be incredibly boring. To avoid incredibly boring sequences little boy moves token randomly: if token is placed on vertex v, he selects uniformly at random one of v's neighbors in the tree and places token onto it. After playing about 4↑↑ 2 times the game started to feel a little boring. On the other hand, quite big number of played games helped Jim to develop intuition about how many moves at average it takes to finish the game with given S and F. On the next day, Jim decided that experimenting on innocent people is more funny than playing with his tree. To begin with he decided to investigate how well do others perform on calculating expected number of moves to finish a game on some particular tree.

Input

The first line of input contains two integers 2 ≤ n ≤ 105 and 1 ≤ q ≤ 105 — number of vertices in tree and number of pairs (S, F) for which expected number of moves should be calculated.

The next n - 1 lines contain the edges of Jim's tree. Each line contains two integers v and u (1 ≤ ui, vi ≤ n, ui ≠ vi) — endpoints of an edge. It is guaranteed that the given graph is a tree.

The next q lines contain pairs 1 ≤ Si, Fi ≤ n (Si ≠ Fi) — start and finish vertex in the i-th experiment.

Output

It can be shown that for any tree with given start and finish vertices S and F the expected number of moves to finish the game can be represented as , where P and Q are coprime and . For each pair of vertices (Si, Fi) output P × Q - 1 modulo 109 + 7 on a separate line.

Example
Input
3 2
1 2
2 3
1 3
1 2
Output
4
1