2015-2016 6th BSUIR Open Programming Contest. Semifinal
A. LIS and GCD
time limit per test
15 s
memory limit per test
1024 MB
input
standard input
output
standard output

You are given two arrays a and b. Each array has n integer numbers. You need to compute the sum of GCDs of all subsequences of array b such that the corresponding subsequences of array a are increasing.

Input

The first input line contains one integer number n. The second line contains n integer numbers ai. The third line contains n integer numbers bi.

1 ≤ n ≤ 105
1 ≤ ai ≤ 109
1 ≤ bi ≤ 106
Output

Display the answer modulo 109 + 7.

Examples
Input
2
1 2
1 2
Output
4
Input
2
2 1
1 2
Output
3
Input
4
2 3 1 4
2 3 6 9
Output
29
Note

Third example: Here are examples of increasing subsequences from a and the corresponding GCD values: {2}->2, {3}->3, {1}->6, {4}-> 9, {2,3}->1, {2,4}->1, {3,4}->3, {1,4}->3, {2,3,4}->1.

B. Sum-and-sum
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Little Lyosha has an array, which consists of n integers. Every day he selects a certain continuous segment of the array and carefully examines each of its subsegments. For every subsegment he calculates bitwise AND of its elements, adds the sum of all elements of the subsegment to it and then writes down the calculated value into his Notebook of Important Numbers. Note that numbers in the array can be negative, so when calculating bitwise AND one should use their absolute values. At the end of the day, after Lyosha has carefully examined all the subsegments, he looks through all the written values, takes the maximal number among them and then writes it down into his Notebook of Very Important Numbers. The Notebook of Very Important Numbers is naturally very important for Lyosha, so he wants to make sure that there are no errors. Help the little boy to check his notes.

Input

The first line contains two integers n and m — the length of the array and the number of notes Little Lyosha wants to check. The second line contains n integers ai — elements of the array. Then m lines follow. The i-th line contains integers li and ri, which means that on the i-th day the boy played with segment [li, ri] of the array.

1 ≤ n ≤ 3 × 105
1 ≤ m ≤ 3 × 104
|ai| ≤ 105
1 ≤ li ≤ ri ≤ n
Output

Print m lines. On the i-th line print the number that Lyosha should have written in his notebook at the i-th day.

Example
Input
7 3
3 -3 3 -3 6 5 -3
2 4
3 7
2 6
Output
6
15
15

C. A lost array
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Fortune smiled upon little Lyosha: he managed to get a very rare and unique array A, which consists of n integers. Having obtained such a precious object, the boy immediately brought it to his underground laboratory so as to fathom the mystery of the array's structure. As an experienced researcher, Lyosha decided not to hurry with performing all the horrible experiments with the poor array, but to observe it at first. On a piece of paper he made some notes on m observations of the array. Each observation is described by 3 numbers li, ri and si, which mean, that the sum of elements modulo 2 on the subsegment [li, ri] of the array equals si. Lyosha has prepared everything required for the (m + 1)-th observation, but at that point he heard his mother calling him for dinner. Once the boy returned to his lab after the dinner, he shuddered with horror: the array was gone. At all. All the hopes of the little boy of getting the Nobel Prize in the field of array research have vanished in no time. However Lyosha remembered, that he still had some information left about the array. Based on the facts he had previously written down, he decided to build a virtual prototype of the array and conduct experiments with it. Of course, the little boy realized there was no way he could restore an identical copy of the lost array, because there are infinitely many arrays which comply with his previously written down observations. Certainly, all of us know, that operations with huge numbers take huge amount of time, and things get even worse when it comes to negative ones. In order to make his computer prototype as fast as possible, little Lyosha decided to build an array that complies with his notes, its elements are all non-negative and their sum is as small as possible. Help him to do it!

Input

The first line of the input contains two integers n and m — the size of the lost array and the number of observations, which little boy made about it. Then m lines follow. The i-th line contains three integers li, ri and si - description of the i-th observation.

1 ≤ n ≤ 40
0 ≤ m ≤ 100
1 ≤ li ≤ ri ≤ n
0 ≤ si ≤ 1
0 ≤ ai ≤ 109
Output

Print n integers ai - elements of the brand new array. If there are several possible arrays, print lexicographically minimal of them. Formally, an array X is lexicographically less then array Y if there is such number k ≤ |X|, that for all i < k Xi = Yi and Xk < Yk.

Example
Input
3 3
2 2 1
3 3 0
2 3 1
Output
0 1 0

D. Bulls and cows
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You woke up on the chilly tiled floor of a farm. "Hello…", said a spooky voice. "I want to play a game." You did not have a choice, so you listened to the game’s rules.

The voice knows a 4-digit secret number, all digits of which are different. You need to guess it and for that you can make several tries. During each try you say a 4-digit number, all digits of which are different. The voice tells you the number of matches. If the matching digits are in their right positions, they are called "bulls"; if in different positions, they are "cows".

For example: the secret number is 3219. Your try is 2310 and the voice’s answer is 12: one bull (the digit 1 is on the right position) and two cows (digits 2 and 3 are present in the number, but they are in different positions).

You have at most 8 tries to guess the secret number. Once you guess it, you can leave the crazy farmer’s place alive. Good luck!

Input

For each your try you will receive a line of two digits: number of bulls and number of cows.

Output

Don’t forget to put a newline character and to flush the output stream after you print your guess. For example fflush(stdout) in C++, System.out.flush() in Java, and flush(output) in Pascal.

Example
Input
0123
0145
0256
0612
0178
0619
Output
11
11
11
30
11
40

E. A+B
time limit per test
1 second
memory limit per test
64 MB
input
standard input
output
standard output

You are given N numbers Ai. You are required to find the sum of Ai. Unfortunately, the numbers in the input were mixed up in such way that the number N is not necessarily the first number of the input.

Input

The first line contains the numbers Xi (0 ≤ Xi ≤  50). The amount of numbers in the input is not greater than 50. Among these numbers are the number N and the numbers Ai.

Output

Calculate the sum of Ai.

Example
Input
23 3 12 7
Output
42

F. Stone, grass and fire
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer Lyosha owns a rectangular field. The field has n rows and m columns. Field cells positions are denoted by pairs of numbers (i, j), where i is the row index and j is the column index. Each cell of the field has either grass (denoted by character '.’) or stone (denoted by character 'X’).

Disasters happen, and Lyosha's field is on fire. The fire has started in different cells. There are k fire sources. The i-th fire source has started in grass cell (xi, yi) and it will burn for ci seconds. Each second the fire spreads from an already burning cell to adjacent cells that have a common edge with the burning cell. If in current cell fire will burn for c second, then this fire will burn for c - 1 seconds in adjacent cells. The fire did not spread to adjacent cells, if it will burn for zero seconds in current cell.

Assume that all fire sources are independent. All fire sources have distinct coordinates. Stone does not burn.

Lyosha is very eager to know how many grass cells are going to burn down.

Input

The first input line contains three integer numbers — n, m, k — which denote the field size and the number of fire sources. Following that are n lines describing the field, each line has m characters. The j-th character in the i-th line denotes type of the (i, j) cell. The next k lines each contain three integer numbers xi, yi, ci that describe the i-th fire source.

1 ≤ N, M ≤ 500
0 ≤ K ≤ N × M
1 ≤ xi ≤ N
1 ≤ yi ≤ M
1 ≤ ci ≤ 109
Output

Output one integer number: the number of grass cells that will burn down.

Example
Input
4 5 2
.X...
.X.X.
.X.X.
...X.
1 3 1
3 3 4
Output
9

G. ReHanoi Towers
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Everybody knows the classical puzzle about Hanoi Towers. There are three rods and one of them has n rings in ascending order of radius, the biggest disk is at the bottom, smallest is at the top. The objective of the puzzle is to move all of the rings to another rod in a minimal number of steps and preserve the disk order. During one step you are allowed to move only one ring and smaller radius rings can only be put on top of bigger radius rings.

You are required to solve modified Hanoi Towers puzzle. You have four rods instead of three. All other rules are left unchanged.

Input

A single integer number n — the number of rings on the first rod.

1 ≤ n ≤ 109
Output

The minimal number of steps modulo 109 + 7.

Examples
Input
2
Output
3
Input
8
Output
33

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

Lyosha is tired of inventing a bicycle, so he decided to invent an unbreakable cipher. Mature cryptanalyst Vasya knows that in his algorithm Lyosha uses x and y such that li ≤ x ≤ ri and lj ≤ y ≤ rj for 1 ≤ i < j ≤ n. Help Vasya decipher Lyosha’s private message. You need to compute number of tuples (x, y, i, j) such that number of ones in binary representation of is odd.

Here denotes addition modulo 2 aka exclusive disjunction aka exclusive OR aka xor.

Input

The first line contains number n. Following that are n lines, where the ith line contains pair of numbers li ri.

1 ≤ n ≤ 105
1 ≤ li ≤ ri ≤ 1018
Output

The only output line should contain the number of tuples (x, y, i, j) modulo 109 + 7.

Example
Input
4
1 4
7 9
6 7
2 8
Output
42

I. Abacaba Ltd.
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Yasha is a young businessman who has read lots of marketing books. He decided to give his company a name that it will be the first in the alphabetical list of organizations of the city. But the city council is tired of all these endless "Abacaba Ltd."-s. So they gave Yasha a random string as the name for his company, in which he must do exactly one modification. Modification is done by swapping any two characters such that the distance between them is equal to any of the favorite numbers of the head of the city council. The distance is calculated as absolute difference of positions of characters in the string. It is guaranteed that such modification is possible.

Input

The first line contains string s — the initial random name. It consists of small latin letters. The second line contains one integer number n —the amount of the favorite numbers of the head of the city council. The next line has n integer numbers ai.

2 ≤ |S| ≤ 105
1 ≤ n ≤ 50
1 ≤ ai < |S|
Output

Output the name of the company that want to choose.

Example
Input
acdbe
2
4 2
Output
abdce

J. Covering distance
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given a set of n geometric points. Assume arbitrary point P and all possible k non-degenerate different triangles Ti formed by point P and two other points within the set. Two triangles are considered different if they differ by at least one vertex. There are mi points ti, j situated strictly within Ti (points on the borders are excluded). Let's determine cover distance as , where dist(X, Y) means Euclidean distance between points X and Y. When there are no applicable points ti, j for point P, then cover distance is equal to -1.

You are required to compute cover distance for each point of the set.

Input

The first line contains number of points n. Following that are n lines, where the ith line contains coordinates of the ith point represented by two integer numbers xi yi. It is guaranteed that all points are distinct.

1 ≤ n ≤ 300
|xi|, |yi| ≤ 109
Output

For each point p output the required average distance. If no point satisfies the above requirements, output  - 1. Your output should have an absolute or relative error of at most 10 - 9.

Example
Input
6
0 2
2 4
-1 3
0 0
1 3
1 2
Output
-1
1.885618083
1.648528137
2.290569415
1.414213562
1

K. Problem
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Tired of long, confusing, boring, tedious fairy-tales and legends in problem statements? All these pathetic authors’ attempts to express their hidden literary talents, which, in fact, they barely have… This inexplicable desire to mangle a crystal clear, orderly and elegant mathematical problem and throw it into our dreary reality… Enough! This problem will be short, clear and unequivocal.

You are given array F, which consists of n integers, and m quadruples ai, bi, ci, di, such that ai ≤ bi, ci ≤ di. For every quadruple compute and print value ansi that is equal to the number of ordered pairs (u, v), such that ai ≤ u ≤ bi, ci ≤ v ≤ di and Fu = Fv.

Input

The first line of the input contains two integers n and m — length of array F and the number of quadruples. The second line contains n space-separated integers Fi. Each of next m lines contains four integers — ai, bi, ci and di.

1 ≤ n ≤ 2 × 105
1 ≤ m ≤ 3 × 104
0 ≤ Fi ≤ 105
1 ≤ ai ≤ bi ≤ n
1 ≤ ci ≤ di ≤ n
Output

Print m lines. The i-th line should contain only one integer — ansi.

Examples
Input
10 5
4 1 5 0 1 1 1 0 2 1
7 10 4 6
3 5 3 5
5 10 4 7
9 10 3 10
1 3 2 10
Output
5
3
13
5
6
Input
5 3
2 1 3 3 2
3 3 2 5
3 4 3 4
4 5 2 2
Output
2
4
0