Analysis of the tasks of the qualifying round of RCC 2016 / Blog of the Mail.ru Group company

The next - qualifying - round of the international championship of programmers Russian Code Cup 2016 has come to the end . And according to the established tradition, we suggest that you familiarize yourself with the solutions to the problems that were offered to the contestants in the last round. This time there were six tasks, although two hours were still allocated to solve them. 604 people fought for the next round . RCC is held for the first time including for English-speaking participants. The result was not long in coming - serious competition will be made to Russian-speaking programmers. 50 people went to the finals 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 2 seconds
Memory limit 256 megabytes

Soon Kolya will have to write an important control, so he decided to carefully prepare. He found that the control will have n options, the i- th of which consists of m _i tasks, numbered from 1 to m _i . For each task of each option, Kolya estimated the time t _ij minutes, which will take his decision.

During the control, he plans to solve tasks strictly in the order in which they are located in the version. The work must be handed over no later than the end of the control, which lasts tminutes. Of course, Kolya could write off the control, but he believes that this is not very correct. Therefore, I am ready to write off no more than one task. He will spend t ₀ minutes writing off any assignment .

Now, knowing all this information, he wants for each option to find out how many tasks he has time to solve if he comes across 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 test and the time that Kolya will spend on cheating tasks.

In the followingn lines contain a description of the options. The first number m _i (1 ≤  m _i  ≤ 100) is the number of jobs in option i . The next m _i numbers t _ij (1 ≤  t _ij  ≤ 100) - the time that Kolya will spend on solving the j- th task of the i- th option.

Output format

For each option, print on a new line one integer - the number of tasks that Kolya will have time to solve if he comes across this option.

Examples

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

Output
5
4
2
1

Solution

Let’s go through the prefix of the tasks that Kolya will solve. We will find the time that he will spend if he will solve all the tasks himself, and the maximum time that he will spend on one task in this case. It is clear that if he writes off, then he must write off the very longest task of those that he does. Then the time that Kolya will spend is S  - max (0,  M  -  t ₀ ). Now we find the largest prefix for which this time does not exceed t .

Problem B. Millipede

Condition

Time limit 2 seconds
Memory limit 256 megabytes

In childhood, a little millipede lived at home with a boy Fili. In total, the millipede had n legs, some of them right and some left. Every day, the millipede used only some of its legs, but always at least one left and at least one right.

Every day, Phil wrote down two numbers on his notebook — how many left and how many right legs the millipede used on that day.

Filia wants to understand from her notes how many left and how many right legs his centipede had. Unfortunately, Phil is not perfect and could make mistakes in several entries. Filya considers record l _i ,  r _icorrect if the millipede 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 entries as possible are correct.

Input format

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

The next m lines contain two numbers l _i and r _i (1 ≤  l _i ,  r _i  ≤  n ) - the number of left and right legs used by the millipede on the i- th day according to the records of Fili, 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 of the millipede, so that the largest possible number of records is correct.

Examples

Input
3
4
3
1 2
1 3
1 4
2
2
2 2
1 2
5
4
1 4
2 3
3 2
4 1

Output
1 3
1 1
1 4

Solution

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

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

It was also necessary to pay attention that the sum of numbers in the answer should be equal to n , and correctly handle the case where all entries may be incorrect.

Problem C. Binary Tree

Condition

Time limit 4 seconds
Memory limit 256 megabytes

A student of Vasya needs to grow a complete binary tree for all tests in bioinformatics, all leaves of which have the same distance to the root.

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

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

Vasya wants to find out if he can complete the task at all, what vertex he needs to choose the root for, 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 leaves of which have the same distance to the root, for a minimum number of days, then he needs a vertex with a minimum number.

When displaying the number of days that he needs, Vasya wants to see only the remainder of dividing this number by 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 dividing it at 10 ⁹  + 7, the remainder must be taken immediately before withdrawal.

Input format

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

Each of the following t tests is described as follows: the first line of the test description contains a single integer n (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 ribs form a tree.

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

Output format

Output the answer for each test on a separate line.

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

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

Examples

Input
3
3
1 3
3 2
4
4 2
3 2
3 1
5
1 2
1 3
1 4
1 5

Output
3 0
2 3
-1

Solution

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

Note that if there is a vertex of degree greater than 3 in the tree, then the task cannot be completed - in a complete 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, it is necessary to sort out the root - a vertex of degree no more than 2 - and choose a vertex such that the maximum of the distances from it to all the others is minimal. This will be the height of the resulting tree.

Task D. Test tubes and reagents

Condition

Time limit 2 seconds
Memory limit 256 megabytes

Today, a chemistry teacher gave Petya a very important task - to pour 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 that 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 Petya has. The teacher asks Petya to pour all the reagents so that in the i- th test tube at least p _i percent of all the liquid in it is occupied by the reagent c _i , and also that the restrictions on min _i and max _i are satisfied in each test tube . All reagents must be completely spilled. We assume that no chemical reactions and changes in the volume of reagents occur.

Help Petya complete the teacher’s task or say that no matter how he tries, he won’t be able to do it.

For example, in the first test case from the example, the following answer will work:

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

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

Input format

Input data contains several test suites. 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 next 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) - minimum and maximum total number of milliliters of liquid that can be poured into i-th test tube, reagent number and its minimum percentage in vitro, 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 Petya.

It is guaranteed that the sum of n and the sum of 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 print YES, and in the i- th of the next n lines print first the number k - the number of different reagents ini- th test tube, and then k pairs of positive numbers id , v - reagent number and its quantity in the test tube. If there are several answers, it is allowed to print any.

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

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

Examples

Input
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

Solution

We present a constructive algorithm in several stages:

• If sum (min _i )> sum (v _i ) - the answer is NO.
• If sum (max _i ) <sum (v _i ) - the answer is NO.
• Pour min _i • p _i  / 100 milliliters of reagent c _i into each tube .
• After that, for each reagent i, we sort the tubes, for which c _j  =  i , in ascending order p _j and we will in turn pour the remaining reagent number i into them .
• Pour in each tube (max _j  - min _j ) p _j  / 100 milliliters of the i- th reagent or less if it runs out.
• We’ll pour the rest of the reagents into the tubes in any way: in the ith tube, you can add any amount of liquid that does not exceed summary _i • 100 /  p _i (summary _i is the total amount of liquid in it at the 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 liquid.
• To correct this, in test tube i, first transfer from all the other test tubes j reagents other than c _j into the i- th test tube, so that at least min _{j of} liquid remains in the j- test tube .
• If that was not enough of the other tubes perelom j fluid number c _j (now it will not spoil the condition on the percentage).

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

Task E. Change money

Condition

Time limit 4 seconds
Memory limit 256 megabytes

Over his long life, Borya has collected a collection of n coins. He laid all these coins in a row. In this case, the i- th coin in the row has the face value a _i .

Borya is going on another trip, but he has very little time left for training camps. Therefore, he wants to take some segment of the coins lying in a row and hopes that he has enough of them.

Borya wants to answer a few inquiries. In each request, Borya wants to know what minimum amount he will not be able to pay without change if he takes all the coins from l _i to r _i-Yu. More formally, he wants to find such a minimal positive integer z that one cannot choose a subset of coins with numbers from l _i to r _i , whose total denomination is z .

Input data format

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

In the following mthe lines are given two numbers l _i and r _i (1 ≤  l _i  ≤  r _i  ≤  n ) - a description of the queries.

Output format

For each of m requests print the minimum amount that cannot be paid without change using coins from l _i to r _i .

Examples

Input
5 5
2 1 5 3 1
1 5
1 3
1 1
2 4
2 5

Output
13
4
1
2
11

Solution

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

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

Note that the value of the maximum coin that we examined grows at least as fast as the Fibonacci numbers. So this process will end in O (log Answer) iterations.

To solve the original problem, you need to learn how to find the sum of numbers less than X on a segment. If we do this in O (log n), then we can solve the problem in total in O (m log n log Answer) .

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

Task f

Condition

Time limit 5 seconds
Memory limit 256 megabytes

Gnome Pasha writes the qualifying round of the Gnome Math Cup. The following is proposed as a problem F.

Given n natural numbers a ₁ ,  a ₂ , ...,  a _n and a natural number d , you need 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 numbers d , a _i do not exceed 10 ⁶ , and the numbers x _i must be from –10 ⁶ to 10 ⁶ , but not equal 0.

Help Pasha find at least one set x _i , which satisfies the conditions of the task, or let him know that the organizers did poor 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 of n for all tests does not exceed 10 ⁵ .

Output format

Output the answer to each test. If the desired set x _iexists, then in the first line print YES and in the second print any suitable set. Otherwise, in the single line of the answer to the test print NO.

Examples

Input
2
2 1
2 3
3 3
2 3 1000

Output
YES
2 -1
YES
503 -1 -1

Solution The

answer NO is only in one case when d is not divisible by the largest divisor of all numbers a _i . In any other case, the answer always exists. To begin with, we will learn how to get at least some answer without limiting the values, after dividing all a _i and d by gcd ( a ₁, ...,  a _n ). If n  = 1, then x ₁  =  d / a ₁ . In other cases, we will choose for each prefix [1,  p ] such 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 extended Euclidean algorithm, we finds 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 received 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 does not fit the restrictions. To reduce the time of work, we choose among a _{i the} subset whose greatest common factor is the same as the whole set, and such that it cannot be reduced. To do this, we will iterate from a ₁ to a _nand take a number in a subset if it reduces the number of different prime divisors. Thus, the selected subset contains no more than 7 elements, since the maximum number of prime divisors of 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 satisfied that x _i modulo do not exceed 10 ⁶ and there should not be zeros among them. To do this, we describe the normalization procedure. First we satisfy the first condition for x _i . First we do all x_i for i  > 1 non-negative and less than a ₁ . This is done by a simple operation of equivalent change: 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 we will go through all x _i , starting from the second one, 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 exists i such that after applying the operation to x ₁ , ...,  x _i it _turns out 0 ≥  x ₁  ≥ –10 ⁶ . Suppose that there is no such i , then all x _ibecame negative, which could not happen, since a ₁  x ₁  + ... a _n  x _n gives d , that is, a positive number. After we learned how to get | x _i | ≤ 10 ⁶ , it remains to make them nonzero. We break all the zeros into pairs, possibly except one. In each pair i and j, we assign x _i  =  a _j and x _j  =  –a _i . We may have the only index p for which x _p = 0. We will consider several cases:

• If there exists x _j , which modulo is not equal 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 such x _j does not exist, but a _p  ≤ 5 • 10 ⁵ , then the operation can be applied 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 must be a _q such that a _q  ≠ a _p . If this does not exist, then all a _i  = a ₁ , and therefore, due to normalization to the greatest common factor a _i  =  a ₁  = 1, the second case should have been fulfilled. We carry out the operation: subtract sign (x _j ) a _p from x _q and add sign (x _j ) a _q to x _p . After that, x _q is zero. But now, if n > 2, for q the first case holds, and if n  = 2, then for q the second case holds, 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, so that the numbers fit in a 64-bit data type. For further details, you can refer to the jury decision code laid out along with the tests.

***
The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at developing the Russian IT industry and united by the IT.Mail.Ru resource. The IT.Mail.Ru platform was created for those who are interested in IT and strive to develop professionally in this field. The project combines the championships of the Russian AI Cup, Russian Code Cup and Russian Developers Cup, educational projects at the Technopark MSTU. Bauman, Technosphere at Moscow State University M.V. Lomonosov and Technotrek at MIPT. In addition, at IT.Mail.Ru you can use the tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from relevant events and lectures on IT topics.