KTU Programming Camp (Day 2)
A. Fitting boxes
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Programming is fun, but programmers usually don't like geometry problems, though they are often part of the programming competitions. Jonas participated in a programming competition yesterday and one of the problems that he hadn't solved was a geometry problem. Jonas is a very stubborn programmer, and he always works hard to solve the problems he didn't solve in a contest. Certainly, Jonas was able to solve the problem when he got home after a while, but let's see if you can do it better than Jonas today. In this problem you are given 2 rectangles and you need to find if you can fit one of them into the other. The dimensions (A1, B1), (A2, B2) of the rectangles are given. Rectangles can be rotated, if necessary, in order to fit them. The width of the sides of the rectangles is negligible. The rectangle inside can coincide with the outer rectangle sides, for example 1 x 1 rectangle fits inside 2 x 1.

Input

Each test case contains 4 positive integers separated by a space character, A1 ≤ 103, B1 ≤ 103, A2 ≤ 103, B2 ≤ 103.

Output

Output "Yes" if it's possible to fit one box into another, or "No" if it's not possible.

Examples
Input
4 4 4 4
Output
Yes
Input
20 1 1 10
Output
Yes
Input
10 10 5 16
Output
No
Input
10 10 11 1
Output
Yes
Input
100 100 200 1
Output
No
B. Board with lights and switches
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Informikas, while cleaning his basement, have found some interesting stuff. One of them was a board, which had many many squares. On every square there was a light bulb. To light the light bulbs there were switches, one for every column and one for every row.

To light a bulb in some square you need to turn on the switches on both the corresponding column and corresponding row. For example, to turn the light in square on a second row and third column, you need to turn on the switch for the second row and switch for the third column. However, by turning second row and second and third columns, you would turn on two lights – one on the square (2;2) and the second one on the square (2;3).

Informikas quickly came up with a game he could play with this board. He would start a game by choosing number N. Then he would turn on N switches, some of them on columns and some of them on rows. This would cause for some number K1 of lights to turn on. He would count those lights, then restore all the switches to the "off" position and repeat the procedure again. However, this time he would turn on K1 switches and in result light on K2 bulbs. Later he would repeat once again by turning on K2 switches and so on.

For example, in the picture above, Informikas would turn five switches, two on top and three on left (picture on the left, black dots). This would result in six lights (picture in the middle). Later Informikas would repeat the procedure by turning on six switches (picture on the right).

Because Informikas would like to be a billionaire, he wants to light at least a billion lights playing this game. However, he would like to achieve that by taking as few iterations as possible.

Knowing what is the initial number N, could you help Informikas by calculating the least possible count of iterations?

Input

The input consists of single integer N (1 ≤ N ≤ 109) – the initial amount of switches to turn on.

You can consider the board as infinitely big – it can accomodate switching on any number of lights in both rows and columns.

Output

Output a single number – the least possible count of iterations to light up 109 or more lamps, or -1 if there are no way to reach such number of lights.

Examples
Input
1
Output
-1
Input
1000000000
Output
1
Input
5000
Output
2
Note

In the first test case it is impossible to light even a single light. In the second test case you could light 2x999999998 lights. In the third test case you could 1000x4000 lights and later 1000000x3000000 lights.

C. Rating Shuffle
time limit per test
0.3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At a prosperious competitive programming website TopForces each user has a personal rating, which is an integer number. There are n users registered, conveniently numbered with numbers from 1 to n. The i-th user has rating of value ai.

TopForces host regular contests; in a single contest, the rating of each user either increases or decreases by value d. The administrator of the website is curious of the following question: what is the minimal possible number of contests, such that in the end i-th user will have the i-th greatest rating on TopForces?

For clarity, in this problem all users must have distinct ratings after the end of all contests.

Input

The first line of input contains two space-separated integers n and d, the number of users (1 ≤ n ≤ 105) and the change of the rating in a single contest (1 ≤ d ≤ 109). The second line of input contains n space-separated integers a1, a2, ..., an, the ratings of the users ( - 109 ≤ ai ≤ 109).

Output

Output a single integer – the minimum possible number of contests such that there exists a scenario in which after all the contests the i-th user has the i-th greatest rating.

Examples
Input
3 2
1 3 5
Output
2
Input
2 1
2 2
Output
1
Input
3 5
5 -3 1
Output
1
D. Degree Sequence Tree
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Serhan is a very naughty boy. He is well known to have shattered every single toy he got as a present. When asked by his parents what are his reasons for doing it he invokes countless philosophies talking about reaching the true meaning of a notion by bringing it to it's essence. In other words, he thinks learning truly occurs when something is broken apart and analyzed.

In order to cure these bad habits, his parents decided to prove him wrong by giving him a tree with N nodes as a present. Serhan's first reaction was to tear apart his new present. Yet, he was now confused. There was more to the tree than a bunch of shattered vertices, yet there those vertices stood in a complete mess. His understanding of life was now shattered. In order to retrieve the core meaning of the tree he had to build it back.

The boy seems to remember the degree of each of his vertices, but has no idea how to build the tree back, he has never build anything before. It is your responsibility to give him a way to unite the vertices to each other in order to build back the tree. If this task is impossible, output -1 and leave Serhan in eternal pain and remorse.

Input

The input contains on the first line N(1 ≤ N ≤ 200000), the number of vertices. On the next line there are N integers describing the degree of each vertex.

Output

Output N - 1 lines with 2 integers, each describing an edge of the initial tree. If there are multiple trees satisfying the degree sequence you can output any of them. If there is no such tree output -1 on a single line.

Examples
Input
5
1 2 3 1 1
Output
1 2
2 3
3 4
3 5
Input
3
2 2 1
Output
-1
E. Pretty Buses
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

In a country there are n cities connected by m roads. For each road, you have to pay a certain tax when you travel it.

The communication in the country is done by buses, which are driven by drivers. Initially, in city i, there is bus i which has driver i. In a bus there can be unlimited number of drivers. All drivers want to be in the same bus. For this, you can do two operations:

DRIVE b x y = the bus b is driven from city x to city y. You can perform this if bus b is initially in city x, the bus b has at least one driver and there is a road between x and y. The cost of this operation is the tax road of x-y.

MOVE d x y = the driver d moves from bus x to bus y. For this, driver d must be initially in bus x and bus x and bus y must be in the same city. The cost of this operation is 0.

Additionally, no driver can change the bus for more than 25 times.

Find the minimal cost to move all drivers into the same bus. Also, output a sequence of moves that obtains the cost.

Input

The first line of the input contains numbers n and m(1 ≤ n ≤ 200000, 1 ≤ m ≤ 400000). Next m lines describe the roads by 3 integers: x, y and c, which means there is a road from x to y of tax c.

Output

The first line of the output contains the minimal cost. Next lines contains the operations for obtaining the minimal cost, written in the format from the legend. When all operations are performed, output "Done".

Examples
Input
3 3
1 2 1
1 3 1
2 3 2
Output
2
Drive 2 2 1
Move 1 1 2
Drive 3 3 1
Move 3 3 2
Done
Input
4 5
1 2 1
1 3 1
2 3 2
2 4 1
3 4 2
Output
3
Drive 4 4 2
Move 2 2 4
Drive 4 2 1
Move 1 1 4
Drive 3 3 1
Move 3 3 4
Done
F. Sequence of words
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Elfus has an important language exam. He reads the first task: given a text with n characters, let's consider all words of length L. The task can be reduced to sort all words lexicographically and then, write K-th word from this list. Elfus is lazy, so on the paper sheet he'll only write the beginning position of such an word. If there are multiple beginning positions such as the word that starts there will be Kth lexicographically word, you may output any of them!

Please write a program that answers Q queries like the one from above.

Input

On the first line you get the text, as a string of n characters (1 ≤ n ≤ 105) Next line contains number number Q (1 ≤ Q ≤ 105). Next Q lines contain two numbers: L and K, describing a query.

Output

Output Q lines, representing the answer for each query.

Examples
Input
mlcpet
2
3 3
3 4
Output
1
4
Input
yourtexthereblabla
3
6 2
4 5
2 13
Output
12
6
5
G. Constant speed
time limit per test
1.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

George is driving his car on a road of length n. There are n + 1 signs on this road and they are indexed starting from 1 in the order they are seen. George likes to take notes, so he writes down all of the signs he has seen. His notes can be represented as a string s of length n + 1.

  • If si is a digit, it marks the start of a speed limit restriction
  • If si is ), it marks the end of a speed limit restriction
  • If si is  * , it means that it's a sign that can be ignored (we only care about speed restrictions)

An example of such a string is . Every start sign will have a corresponding end sign. In this case, those pairs are (1, 5) and (3, 4).

Between signs i and i + 1, the restriction that is applied is the one corresponding to the last previously seen start sign (its index is  ≤ i) without an end pair (check samples for clarification).

George asks himself: What is the minimum number of pairs of signs that need to be removed such that the speed limit between signs a and b is constant? He needs to answer q such questions, so he needs your help.

Input

The first line will contain two integers, n and q(1 ≤ n, q ≤ 100 000) – the length of the road and the number of questions. The second line will contain a string s of length n + 1.

Output

You should print q lines. On line i you should print the answer to the ith question.

Examples
Input
4 4
1*9))
2 4
2 3
1 5
4 5
Output
1
0
1
0

Input
5 1
55)5))
1 6
Output
0

Note

The speed limits in the first sample are:

  • Between signs 1 and 2 the speed limit is 1
  • Between signs 2 and 3 the speed limit is 1
  • Between signs 3 and 4 the speed limit is 9
  • Between signs 4 and 5 the speed limit is 1

In order to make the speed limit constant between the signs 2 and 4, we must delete the pair of signs (3, 4).

H. K-palindrome
time limit per test
0.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Let's have K natural numbers: b1, b2, ..., bk. We say that X (in base 10) is K-palindrome if there exist at least one bi such as X written in base bi is a palindrome.

Answer Q queries of form: how many numbers from a range [L, U] are K-palindromes?

Input

First line of the input contains number K (1 ≤ K ≤ 13). The next line has K numbers, representing the array b (2 ≤ bi ≤ 100000). The third line contains number Q (1 ≤ Q ≤ 100000). Next Q lines contain two numbers L and U, describing queries, (0 ≤ L ≤ U ≤ 100000000).

Output

Answer each of the Q queries, one query per line.

Examples
Input
2
2 3
2
0 10
11 15
Output
10
2
I. Lazy mobile users
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Informikas is creating a website. He has gathered a great amount of information, come up with a beautiful design and optimized the page for best user experience.

To make the structure of the webpage simple, Informikas abides to simple rules:

  • every page has zero or more links;
  • no page has a link to the homepage;
  • there are no two pages who are linking to the same page;
  • a page cannot link to itself;
  • when starting from the homepage, you can reach every other page on the site.

However, not everything is flawless. After showing his website to friends he have found out that people, who browse the Internet on their mobile phones, are very lazy:

  • they hate to input website address by hand, so they store the homepage address in the bookmarks. That means they always enter the site through homepage and never through some internal page;
  • for browsing they only use back button and links displayed on the pages;
  • they get easily annoyed when they open the same page (either by clicking link or clicking "back" button) for some specific number of times. And when they get annoyed, they just immediately close the browser.

Links and "back" button works as in every browser:

  • pressing the link will load a page that is linked;
  • pressing the "back" button causes browser to open the page from which user came to the current page.

Informikas would like to know, what is the maximum number of pages a mobile user could view before getting annoyed. Having the list of webpages with links inside them and the count of times a user has to see the same page to get annoyed, find that number.

Input

In the first line of input there are two integers N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ 105) – the number of webpages and the number of times mobile user could see the same page before getting annoyed. The pages are numbered from 1 to N. Every following N lines consist of integer Mi (0 ≤ Mi, 1 ≤ i ≤ N) – the number of links inside the page i – followed by Mi integers Qi, j (1 ≤ Qi, j ≤ N,) – the names of pages, meaning that page i has a link to page Qi, j.

The homepage (the page mobile user starts browsing the website) has the index 1 (the page described on the second line of input).

Output

Output single integer, equal to the maximum number of pages mobile user could see before getting annoyed.

Examples
Input
3 1
2 2 3
0
0
Output
2
Input
3 2
2 2 3
0
0
Output
3
Input
8 2
3 2 3 4
2 5 7
0
0
1 6
0
1 8
0
Output
7
Note

In the first test case, user enters the home page and then clicks a link to one of the other two pages (either 2 or 3). Any of the two pages have no links. Now, by pressing "back" button, mobile user would reopen homepage, get annoyed and leave. This gives an answer of 2.

In the second test case mobile user could go 1 > 2 < 1 > 3 (here > means clicking the link and < means pressing back button). This results in 3 viewed pages.

In the third test case one of possible paths would be 1 > 3 < 1 > 2 > 5 > 6 < 5 < 2 > 7 > 8. This results in 7 viewed pages (1, 2, 3, 5, 6, 7, 8).

J. The craziness of Juvel
time limit per test
1.2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The well known artist Juvel has started to compose again, but firstly he started to write down on a paper some words. These words are not randomly chosen, being Juvel’s favorite words. After he finally managed to write down all his favorite words, he started to compose a new song. As the artist does not know how to use the punctuation marks, he decided to line the lyrics, creating a string. He reads the lyrics again and changes some letters in order to acquire the perfect song, because he wants this song to become a hit. As the number of favorite words used increases, the quality of the song rises. Juvel wants to know the number of his favorite words used at the beginning of the song and after every change that has been made.

Input

The first line of the input contains an integer N(1 ≤ N ≤ 100) denoting the number of words from his list and an integer M(1 ≤ M ≤ 100000) denoting the number of changes. On the other N lines there is a string with the words from his list. Every word has a length of at most 100. The words from the list are ordered in the Input.

The next line contains a string with the actual song. The length of the song is at most 100000. The next M lines contain an integer pos and a character c, such that it replays the character from the pos position with c. The string with the song is indexed from 1.

Also keep in mind that: length(word1) + length(word2) + … + length(wordn)  - LCP(word1, word2) - LCP(word2, word3) - … - LCP(wordn - 1, wordn) ≤ 100, where LCP is the longest common prefix.

Output

The output contains M + 1 lines, on each line being the number of favorite words used initially and the number of favorite words used after every change.

Examples
Input
3 2
bunaciune
smecherie
valoare
smecheriisibunaciuni
9 e
20 e
Output
0
1
2
K. New GPU
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

No matter how powerful computer you would buy, after some time it becomes too slow to run modern applications (or games). This is why Informikas is thinking about upgrading his graphics card.

You might think that there should be no problem in buying new graphics card – you just decide how much money you would like to spend an using this money you buy the most expensive video card on the market you can afford. However, Informikas doesn't like this approach. If he would buy too powerful graphics card, some of it's power would be left unused. If the graphics card would be not powerful enough, it would bottleneck the system. Informikas would like to choose a graphics card which would fit other components best, no matter how much it would cost.

So, how could one estimate the performance of a video card? Actually, it's pretty simple. You can calculate the performance using a simple formula: . In this formula A and B are constants dependent on both the generation and the feature set of the graphics card, n is the number of cores in the GPU, and P(n) is the performance of the card, measured in Performance Points.

In order to choose the optimal graphics card Informikas has taken into account the other components of the computer (CPU, RAM, etc.) and according to that calculated the optimal performance of the graphics card in Performance Points. He also is sure what generation and feature set of the graphics card he needs and have already found the value of constants on the Internet. Only left to find the most appropriate number of GPU cores. The number of cores should be minimal while the Performance Points of the graphics card should be no less than the optimal performance Informikas has calculated.

Having all that data, could you help Informikas to find the optimal number of GPU cores?

Input

The input consists of three integers A, B and P (1 ≤ A ≤ 105, 1 ≤ B ≤ 105, 1 ≤ P ≤ 109), written on a single line.

Output

Output a single integer – the optimal number of GPU cores.

Examples
Input
1 1 1
Output
1
Input
3 4 7
Output
1
Input
5 7 76
Output
64
L. Plantations
time limit per test
3 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're given a matrix with N lines and N columns. Let's define sum of a square submatrix as sum of all numbers from its main diagonal and from its secondary diagonal. Note that the intersection of the diagonals needs to be added only once to the sum. For example, for the matrix

1 2 3

4 5 6

7 8 9

the sum is 1+5+9+7+3 = 25.

Find the largest square submatrix such as its sum is smaller or equal to W.

Input

The first line contains T, the number of tests (T ≤ 20). Next T lines describe the test cases. On first line of each test there are given two numbers N and W (1 ≤ N ≤ 1000, W is a 32-bit number (can be stored in int type)).

Next N lines contain N elements, describing the element of the matrix. All numbers are positive, up to int maximum value.

Output

Outout the answer for each of the T test cases

Examples
Input
1
3 5
1 1 1
1 1 1
1 1 1
Output
3
Note

Note: The time limit of this problem is unusual. Please check it.