The next qualifying round of the Russian Code Cup 2016 International Programmers Championship has come to an end . And according to the established tradition, we invite you to familiarize yourself with the solutions of the tasks that were offered to the contestants in the last round. This time there were six tasks, although two hours were still allocated for their solution. 604 people fought for entering the next round. The RCC is held for the first time, including for English-speaking participants. The result did not keep waiting - a serious competition will be made up for Russian-speaking programmers. 50 people reached the final and 19 of them are not Russian-speaking participants. Among the finalists are representatives of Russia, Ukraine, Belarus, Lithuania, Slovakia, Armenia, Poland, Switzerland, Finland, Japan, China, South Korea.

1. Test
2. Centipede
3. Binary tree
4. Test tubes and reagents
5. Money exchange
6. Task F

Task A. Examination

Condition
')
Time limit of 2 seconds
256 MB memory limit

Soon Kolya will have to write an important test, so he decided to prepare thoroughly. He found out that the control will have n variants, the i- th of which consists of m _i tasks, numbered from 1 to m _i . For each task of each option, Kohl estimated the time t _ij minutes, which the solution will take from him.

During the control, he plans to solve the tasks strictly in the order in which they are arranged in the variant. It is necessary to hand over the work no later than the end of the control, which lasts t minutes. Of course, Kohl could have written off the control, but he believes that this is not very correct. Therefore, ready to write off no more than one job. He will spend t ₀ minutes writing off any task.

Now, knowing all this information, he wants for each option to find out how many tasks he will have time to decide if he gets this option.

Input Format

The first line contains three integers n , t and t ₀ (1 ≤ n ≤ 100, 1 ≤ t ≤ 10 000, 1 ≤ t ₀ ≤ 100) - the number of options, the duration of the control and the time that Kolya will spend on cheating the task.

The following n lines contain a description of the options. The first number m _i (1 ≤ m _i ≤ 100) is the number of tasks in option i . The next m _i numbers t _ij (1 ≤ t _ij ≤ 100) is the time that Kohl spends on solving the j- th task in the i- th variant.

Output format

For each option, print a single integer on the new line - the number of tasks that Kohl will have time to decide if he gets this option.

Examples

Input data
4 45 5
5 10 10 10 10 10
4 30 10 10 10
3 40 40 5
1,100

Output
five
four
2
one

Decision

Let's sort through the prefix of tasks that Kohl will decide. Find the time he spends if he solves all the tasks himself, and the maximum time he spends on one task in this case. It is clear that if he will write off, then it is necessary to write off the longest task of those he does. Then the time that Kohl spends is S - max (0, M - t ₀ ). Now we find the largest prefix for which this time does not exceed t .

Problem B. Centipede

Condition

Time limit of 2 seconds
256 MB memory limit

In childhood, the boy Fili had a millipede at home. In total, the centipede had n legs, some of which were right and some were left. Every day, the centipede used only some of its legs, but at least one left and at least one right.

Every day Phil wrote two numbers in his notebook - how many left and how many right legs the centipede used on that day.

Phil wants to see from his notes how many left and how many right legs his centipede had. Unfortunately, Phil is not perfect and could make mistakes in several records. Filya considers the entry l _i , r _i correct if the centipede had at least l _i left and at least r _i right legs.

Help him understand how many centipedes could have left and right legs, so that as many records as possible were correct.

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 10 000).
Each of the tests is described as follows: the first line of the test description contains the number n (2 ≤ n ≤ 10 ⁹ ) - the total number of centipede legs, and the second line the number m (1 ≤ m ≤ 10 ⁵ ) - the number of records.

The following m lines contain two numbers each l _i and r _i (1 ≤ l _i , r _i ≤ n ) - the number of left and right legs used by the centipede on the i- th day according to Fili's records, respectively.

The total number of records for all tests does not exceed 10 ⁵ .

Output format

For each test in a separate line print the answer to it - the number of left and right legs at the centipede, so that the maximum possible number of records is correct.

Examples

Input data
3
four
3
12
13
14
2
2
2 2
12
five
four
14
2 3
3 2
4 1

Output
13
eleven
14

Decision

To solve this problem, you can sort all the records by the number of left legs. Next we will sort out the number of left legs in ascending order. If the left legs are l _i , then the first i records may potentially be correct, and all subsequent records are exactly wrong (except for the number of legs equal to _{i i} ).

Now you need to know how many entries from the first i will be correct. The record with number j ≤ i is true if r _j ≤ n - l _i . Finding all such r _j is a standard problem and is solved, for example, by a tree of segments.

It was also necessary to note that the sum of the numbers in the response must be equal to n , and correctly handle the case where all the entries may be incorrect.

Problem C. Binary tree

Condition

Time limit 4 seconds
256 MB memory limit

Student Vasya needs to grow a complete binary tree, all the leaves of which have the same distance from the root, for the bioinformatics test.

Recall that a hanging tree is a connected non-oriented graph without cycles, in which one of the vertices is a root. The parent of a peak is its neighbor, closest to the root, the root has no parent. The remaining neighbors of the summit are called her sons. A peak that has no sons is called a leaf. A complete binary tree is a hanging tree, each vertex of which is not a leaf, has exactly two sons.

Unfortunately, during the semester, Vasya spent too much time on programming olympiads and did not really follow the growth of his tree. A few days before the test, Vasya realized that his tree had grown, but perhaps it was wrong and he did not even have a root. Vasya can choose any of its vertices by the root of the tree and try to obtain from it the required complete binary tree by adding vertices. In one day, Vasya can add a new peak to the tree, making it the son of one of the existing ones.

Vasya wants to know if he can even complete the task, what peak for this he needs to choose by the root and what is the minimum number of days that will be spent on the task. If there are several vertices that can be selected by the root to get a complete binary tree, all the leaves of which have the same distance to the root, for the minimum number of days, then it needs a vertex with a minimum number.

When deriving the number of days he needs, Vasya wants to see only the remainder of dividing this number by the number 10 ⁹ + 7. Please note that Vasya needs to minimize the number of days for which he can complete the formation of the tree, and not the remainder of its division At 10 ⁹ + 7, the balance must be taken immediately before the withdrawal.

Input Format

The input contains several test cases. The first line contains the number of tests t .

Each of the following t tests is described as follows: in the first line of the test description, a single integer n is given (2 ≤ n ≤ 2 • 10 ⁵ ) - the number of vertices in the tree. The next n - 1 lines of the test description give pairs of numbers u _i , v _i (1 ≤ u _i , v _i ≤ n ) - the numbers of the vertices connected by the i -th edge. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of the numbers n in all tests does not exceed 2 • 10 ⁵ .

Output format

Print the answer for each test on a separate line.

If no vertex can be selected by the root and after that for a certain number of days you get a complete binary tree, all the leaves of which have the same distance to the root, output -1.

Otherwise, print two integers - the number of the vertex to be selected by the root, and the remainder of dividing the number of days Vasya needs by 10 ⁹ + 7. If there are several vertices that allow you to complete the task in the shortest time, output the vertex with the minimum number.

Examples

Input data
3
3
13
3 2
four
4 2
3 2
3 1
five
12
13
14
15

Output
thirty
2 3
-one

Decision

To minimize the number of days Vasya has to spend, you need to minimize the height of the final binary tree - if the leaf depth in the final tree is h , then Vasya will spend 2 ^h - 1 - n days to suspend the required number of vertices.

Note that if there is a vertex of degree greater than 3 in the tree, then the task will not be performed, - in a full binary tree all vertices have no more than three neighbors. Note that the root in the answer has exactly two sons.

Thus, in order to solve the problem, you need to sort out the root - the vertex of the degree is not greater than 2 - and choose a root with such a vertex that the maximum distance from it to all others is minimal. This will be the height of the final tree.

Task D. Test tubes and reagents

Condition

Time limit of 2 seconds
256 MB memory limit

Today, a chemistry teacher gave Pete a very important task - to pour the reagents into test tubes. He was given n tubes and m reagents. For each tube, min _i and max _i are known - the minimum and maximum total amount of liquid in milliliters, which can be in it, respectively, as well as the reagent number c _i and the number p _i . For each reagent, the number v _i is also known - how many milliliters it has in Petit. The teacher asks Petya to pour all the reagents so that in the i- th tube at least p _i percent of all the liquid in it is occupied by the reagent c _i , and also that the limits on min _i and max _i are satisfied in each test tube. All reagents must be completely bottled. We assume that no chemical reactions and changes in the volume of reagents occurs.

Help Petya to complete the teacher's assignment, or tell me that, no matter how hard he tries, he will fail to do it.

For example, in the first test set from the example, the following answer will do:

• In the first tube pour 3 milliliters of the first reagent and 2 milliliters of the second.
• In the second tube, pour 4 milliliters of the third reagent and 1 milliliter of the second.
• Pour 3 milliliters of the fourth reagent and 1 milliliter of the second into the last tube.

In this case, all restrictions on min _i and max _i are fulfilled, as well as restrictions on the percentages of reagents in the test tubes: in the first tube 3/5 = 60% of the first reagent, in the second tube 4/5 = 80% of the third reagent, and in the last tube 3/4 = 75% ≥ 70% of the fourth reagent. Also, all reagents are completely poured, so all the requirements given by the teacher are met and the answer is correct.

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 100).

Each of the following t tests is described as follows: the first line of the test description contains two numbers n , m (1 ≤ n , m ≤ 10 ⁵ ) - the number of tubes and reagents, respectively.

The i- th of the following n lines contains four integers min _i , max _i , c _i , p _i (1 ≤ min _i ≤ max _i ≤ 10 ⁵ , 1 ≤ c _i ≤ m , 1 ≤ p _i ≤ 100) - the minimum and maximum total amount of milliliters of liquid that can be poured into the i- th tube, the number of the reagent and its minimum percentage in the tube, respectively.

The last line of the test description contains m integers v _i (1 ≤ v _i ≤ 10 ⁵ ) - the number of milliliters of the i-th reagent in Petit.

It is guaranteed that the sum n and the sum m in all tests does not exceed 10 ⁵ .

Output format

For each test output the answer to it.

If the answer exists, in the first line output YES, and in the i- th of the next n lines print first the number k - the number of different reagents in the i -th test tube, and then k positive numbers id , v - the number of the reagent and its amount in the test tube . If there are multiple answers, you are allowed to print any.

If the answer to the test does not exist, in a single line print NO.

The answer will be considered correct if all the conditions mentioned in the task are fulfilled, and the relative or absolute error does not exceed 10 ^–6 .

Examples

Input data
2
3 4
5 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3
3 4
6 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3

Output
YES
2 1 3.0000000000 2 2.0000000000
2 2 1.0000000000 3 4.0000000000
2 2 1.0000000000 4 3.0000000000
NO

Decision

We present a constructive algorithm in several stages:

• If sum (min _i )> sum (v _i ) is the answer NO.
• If sum (max _i ) <sum (v _i ) is the answer NO.
• Pour into each tube min _i • p _i / 100 milliliters of reagent c _i .
• After that, for each reagent i, sort the tubes for which c _j = i , by increasing p _j and we will in turn pour the remaining reagent number i into them.
• In each tube we pour more (max _j - min _j ) p _j / 100 milliliters of the i -th reagent or less if it ends.
• All remaining from the reagents will be poured into the tubes in any way: in the i- th tube, in total, you can pour any amount of liquid that does not exceed the summary _i • 100 / p _i (summary _i - the total amount of liquid in it at the current moment).
• If the spill fails and the liquid remains, the answer is NO.
• The only remaining problem is that in some test tubes there may still be less than min _i milliliters of fluid.
• To fix this in test tube i, first by transferring from all the other test tubes j reagents other than c _j to the i -th test tube, so that at least the _{j j of the} liquid remain in the j -th test tube.
• If this is not enough, by transferring from the remaining tubes of j liquid number c _j (now it does not spoil the condition on the percentage).

After these actions, the resulting separation of reagents into test tubes will always satisfy all the conditions of the problem.
Finally, we note that in this problem there could be certain problems with accuracy. Tests of the jury were built in this sense quite humanely, but after the tour, Peter Mitrichev (whom we congratulate on winning the qualifying round) showed a test in which significant losses of accuracy occur. We will try to further avoid subtleties with accuracy in problems with real numbers.

Problem E. Money exchange

Condition

Time limit 4 seconds
256 MB memory limit

During his long life, Borya collected a collection of n coins. He laid out all these coins in a row. At the same time, the i- th in a row has a coin value of a _i .

Boris is going on another trip, but he has very little time left to pack. Therefore, he wants to take a piece of coins lying in a row and hopes that they will be enough for him.

Boris wants to answer several requests. In each request, Borya wants to know what the minimum amount he cannot pay without surrender if he takes all the coins from l _i to r _i -th. More formally - he wants to find such a minimal positive integer z , that it is impossible to choose a subset of coins with numbers from l _i to r _i , the total denomination of which is equal to z .

Input Format

The first line contains two integers n and m (1 ≤ n , m ≤ 150 000) - the number of coins from Bori and the number of queries. The next line contains n numbers a _i (1 ≤ a _i ≤ 10 ⁹ ) - the value of the i- th coin.

The following m lines contain two numbers each, l _i and r _i (1 ≤ l _i ≤ r _i ≤ n ), a description of the queries.

Output format

For each of the m queries, print the minimum amount that cannot be paid without surrender, using coins from l _i to r _{i to the i} .

Examples

Input data
5 5
2 1 5 3 1
15
13
eleven
2 4
2 5

Output
13
four
one
2
eleven

Decision

Consider how to find the minimum amount of money that can not be given using a given set of coins. We will find the answer iteratively. At the very beginning we can only present a sum that is zero, and we did not use any coins.

Suppose that at the next step we considered all coins whose value does not exceed X , and we can pay any amount up to Y inclusive. Let the total value of coins, each of which is worth more than X , but not more than Y + 1, is equal to sum. Then if sum = 0, then we cannot present Y + 1 using this set. Otherwise, we turn to the state that all coins whose value is not more than Y + 1 are considered, and we can represent any amount up to Y + sum inclusive.

Note that the value of the maximum coin, which we considered, is growing at least as fast as the Fibonacci numbers. This means that the process will end in O (log Answer) iterations.

To solve the original problem, it is necessary to learn how to find the sum of numbers smaller than X on the segment. If you do this for O (log n), then you can solve the problem in total for O (m log n log Answer) .

This task is standard. Consider a method that requires a linear amount of memory. To do this, sort all the numbers in the source array and will respond to all requests in parallel. At the next iteration for each request, we know the current maximum amount of money that can be received. Sort all requests by it. Next, we will add to the Fenwick tree the numbers of the original array in ascending order and at the right time update the boundary for the next query.

Task F

Condition

Time limit of 5 seconds
256 MB memory limit

Dwarf Pasha writes a qualifying round for the Gnome Math Cup. As task F, the following is proposed.

Given n positive integers a ₁ , a ₂ , ..., a _n and positive integer d , it is required to find any set of nonzero integers x ₁ , x ₂ , ..., x _n such that a ₁ x ₁ + a ₂ x ₂ + ... + a _n x _n = d . Since the gnomes have poor multiplication and addition, all d , a _i numbers do not exceed 10 ⁶ , and x _i numbers should be from –10 ⁶ to 10 ⁶ , but not equal to 0.

Help Pasha to find at least one set x _i that satisfies the condition of the problem, or tell him that the organizers have done bad tests and there is no answer.

Input Format

The first line of input contains t - the number of tests. Each test is given in two lines. The first line contains two numbers n and d (1 ≤ n ≤ 10 ⁵ , 1 ≤ d ≤ 10 ⁶ ). The second line contains n numbers a _i (1 ≤ a _i ≤ 10 ⁶ ). The sum n for all tests does not exceed 10 ⁵ .

Output format

Print the answer to each test. If the required set x _i exists, then output YES in the first line and output any suitable set in the second line. Otherwise, in the only line of the answer to the test output NO.

Examples

Input data
2
2 1
2 3
3 3
2 3 1000

Output
YES
2 -1
YES
503 -1 -1

Decision

The answer NO only happens in one case when d is not divisible by the greatest divisor of all numbers a _i . In any other case, the answer always exists. To begin with, we will learn to get at least some answer without any restriction on the values, having previously divided all a _i and d into gcd ( a ₁ , ..., a _n ). If n = 1, then x ₁ = d / a ₁ . In other cases, for each prefix [1, p ] we will select x _{i, p} such that a ₁ x _{1, p} + ... + a _p x _{p, p} = gcd ( a ₁ , ..., a _p ). This is done by the inductive method. x _{1, 1} = 1. Suppose we have already found x _{i, p} and want to find x _{i, p} + 1. Using the advanced Euclidean algorithm, we find s and t : s • gcd ( a ₁ , ..., a _p ) + t • a _{p + 1} = gcd (gcd ( a ₁ , ..., a _p ), a _{p + 1} ) = gcd ( a ₁ , ..., a _{p + 1} ). Then for i ≤ p x _{i, p + 1} = s x _{i, p} and x _{p + 1, p + 1} = t . Having obtained x _{i, n} , we calculate x _i = d / gcd ( a ₁ , ..., a _n ) x _{i, n} = dx _{i, n} . This solution works for O (n ² ) , which is not suitable for restrictions. To shorten the time of work, we will choose among a _{i a} subset that has the greatest common divisor of the same set as the whole set, and one that cannot be reduced. To do this, we will iterate from a ₁ to a _n and take a number in a subset if it reduces the number of different prime dividers. Thus, the selected subset contains no more than 7 elements, since the maximum number of prime divisors for a number less than or equal to 10 ⁶ is 7. For numbers from the subset, we run the described algorithm, and for numbers that are not included in the set, we simply set x _i = 0.

Now the algorithm works for O (n) , but the conditions are not met that x _i modulo do not exceed 10 ⁶ and among them should not be zeros. To do this, we describe the normalization procedure. First we fulfill the first condition for x _i . First of all, let's make all x _i for i > 1 non-negative and less than a ₁ . This is done by a simple equivalent change operation: we subtract from x ₁ ka _i and add to x _i ka ₁ , where k = (x _i mod a ₁ - x _i ) / a ₁ . Note that the results of the operation fit into the 64-bit data type, since x ₁ modulo cannot exceed | d - a ₂ x ₂ - ... - a _n x _n | <10 ⁶ • 10 ⁶ • 10 ⁵ . Now let's go through all x _i , starting from the second, to the last and with each, we will sequentially perform the operation: subtract a ₁ from x _i and add a _i to x ₁ . Note that there is i such that after applying the operation to x ₁ , ..., x _i it turned out 0 ≥ x ₁ ≥ –10 ⁶ . Suppose there is no such i , then all x _i become negative, which could not happen, since a ₁ x ₁ + ... a _n x _n gives d , that is, a positive number. After we learned to receive | x _i | ≤ 10 ⁶ , it remains to make them nonzero. We divide all zeros into pairs, perhaps except for one. In each pair of i and j we assign x _i = a _j and x _j = –a _i . We may have a single index p , for which x _p = 0. We will consider several cases:

• If there is x _j that is not equal in magnitude to a _p , then we apply the operation: subtract sign (x _j ) a _p from x _j and add sign (x _j ) a _j to x _p .
• If there is no such x _j , but a _p ≤ 5 • 10 ⁵ , then you can apply the operation to any x _j : add sign (x _j ) a _p to x _j and subtract sign (x _j ) a _p from x _p .
• Otherwise, there should be a _q , such that a _q ≠ a _p . If this does not exist, then all a _i = a ₁ , and therefore, due to the normalization to the greatest common divisor a _i = a ₁ = 1, the second case should have been fulfilled. We perform the operation: subtract sign (x _j ) a _p from x _q and add sign (x _j ) a _q to x _p . After this, x _q is zero. But now, if n > 2, the first case holds for q , and if n = 2, then the second case holds for q , since d = a _q a _p ≤ 10 ⁶ .

It should be noted that the normalization operation must be performed for each prefix in the algorithm described in the first paragraph in order for the numbers to fit into the 64-bit data type. For further details you can refer to the jury's decision code laid out along with the tests.

***
The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at the development of the Russian IT industry and integrated with the IT.Mail.Ru resource. The IT.Mail.Ru platform is designed for those who are keen on IT and are seeking to develop professionally in this area. The project combines the championships of the Russian AI Cup, the Russian Code Cup and the Russian Developers Cup, educational projects Technopark in MSTU. Bauman, Technosphere at Moscow State University. MV Lomonosov and Tehnotrek MIPT. In addition, using IT.Mail.Ru, you can use tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from specialized events and lectures on IT topics.