 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
First qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Volleyball match at Mars is played by two teams until one of the teams gets k points, with score at least 2 points more than the score of the other team. For each ball played exactly one of the teams gets 1 point.
Now the score of the first team if x, the score of the second team is y. What is the minimal number of balls that must be played until one of the teams wins the match?
Input format 
Input contains several test cases. The first line contains integer t — the number of cases (1 ≤ t ≤ 5000). Each test case is described using one line that contains three integers separated by spaces: k, x and y (1 ≤ k ≤ 100; 0 ≤ x, y ≤ 100). It is guaranteed that the score can be obtained in a correct unfinished game. 

Output format 
For each test case print one line — the minimal number of balls to be played, until the match is finished. 
Examples 
Input data
3 2 1 0 3 4 3 5 0 0
Output data
1 1 5 
Time limit  2 seconds 

Memory limit  256 megabytes 
Little girl Masha is looking at the wall in her room. The wall is tiled with square tiles, but some of the tiles are replaced with lamps. So it is possible to consider the wall to be a rectangle of n × m, some cells contain tiles, other cells contain lamps.
Masha has paints of k different colors. Consider continuous vertical or horizontal segments of tiles, having an edge of the wall or a lamp at each of its ends. Masha wants to paint all tiles in such way, that any such segment has all tiles painted in different colors. Masha will not paint lamps. She doesn't have to use all the colors.
Help Masha to paint the wall.
Input format 
Input contains several test cases. The first line contains the number of test cases t. Each test case is described by several lines. The first line contains three integers: n, m, k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ max(n, m)) — the size of the wall and the number of paints Masha has. The following n lines contain m integers a_{ij} each:
The total number of tiles and lamps in all test cases of one input doesn't exceed 10^{5}. 

Output format 
For each test case first print the answer:

Examples 
Input data
2 4 3 2 0 1 0 1 0 1 1 0 1 0 1 0 3 4 2 0 1 0 1 1 0 1 1 1 1 1 0
Output data
YES 0 2 0 2 0 2 1 0 1 0 1 0 NO 
Time limit  2 seconds 

Memory limit  256 megabytes 
Maxim is playing a video game. It has n levels, numbered from 1 to n. Levels can be completed in any order, it takes Maxim a_{i} seconds to complete the ith level.
Maxim can find a magic artifact at one of the levels. There is exactly one magic artifact in the game, and once found it will increase the speed of Maxim's hero and reduce the time needed to complete the level. However, it is not known where the artifact is, the probability that it is at the ith level is p_{i}. The time needed to complete the ith level after the artifact is found is b_{i} second (b_{i} ≤ a_{i}). Note that artifact doesn't reduce the time needed to complete the level where it is found.
Maxim wants to choose the order he completes the levels, to minimize the expected time to complete the game. Help him to find the minimal possible expected time. Maxim must choose the order to complete the levels before playing the game, the order must not depend on whether the artifact was found or not at some level.
Recall that the expectation of a random variable is the sum over all possible outcomes of a product of the probability of such outcome and the value of the variable. In this problem the outcome corresponds to the level where the artifact is, and the value is the total time needed if the artifact is at that level.
Input format 
Input data contains several test cases. The first line contains t — the number of test cases (1 ≤ t ≤ 1000). Each test case is described in the following way: the first line contains integer n — the number of levels (1 ≤ n ≤ 10^{5}). The following n lines describe levels. Each level is specified with three integers a_{i}, b_{i} and x_{i} — the time to complete the level before the artifact was found, the time to complete it after the artifact was found, and the value that helps to find the probability to find the artifact at that level. The probability is calculated using the formula p_{i} = x_{i} / 10^{7} (1 ≤ b_{i} ≤ a_{i} ≤ 10^{5}; 0 ≤ x_{i} ≤ 10^{7}; the sum of all x_{i} is 10^{7}). The sum of values of n in all test cases of one input data is at most 5·10^{5}. 

Output format 
For each test case output one floating point value — the expected time to complete the game if the optimal order was chosen. The answer must have an absolute or relative error of at most 10^{  6}. 
Examples 
Input data
2 3 10 5 10000000 5 3 0 7 3 0 4 3 1 2500000 4 1 2500000 10 1 2500000 2 1 2500000
Output data
16 10.25 
Time limit  3 seconds 

Memory limit  256 megabytes 
Peter is developing memory manager MEM 2.0 for his offline storage that uses special magnetic 7D blocks. But he has a problem of accessing data in the optimal way.
Peter's memory manager stores n blocks of data, numbered from 1 to n, and he has q queries of accessing one or several of the blocks. Queries must be processed in order they are listed.
To access the data Peter's memory manager has k pointers, each of them points to some block. Initially Peter can position his pointers at any desired blocks.
MEM 2.0 can immediately access data from any number blocks if each of them is currently has some pointer at it. If it is not the case, the manager must first move the pointers, this operation for the ith query takes s_{i} milliseconds total to move any number of pointers.
Peter wants to move pointers in such way that the total time of answering all queries was minimal possible. Queries must be processed in order they are listed, changing the order is not allowed. Help him!
Consider sample test cases.
In the first sample test Peter can initially position pointers at blocks 1, 2 and 4 — after that the first two queries are accessed immediately. Before the third query the pointers must be moved to blocks 2, 3 and 5, it takes s_{3} = 1 milliseconds, and moving pointers to blocks 1, 3, and 5 before the fourth query takes another s_{4} = 1 milliseconds. The total time is s_{3} + s_{4} = 2 milliseconds.
The second sample test shows that it is sometimes not optimal to make a greedy choice. It is best not to perform two first queries immediately by positioning pointers at 1, 2 and 4 initially, because moving the pointers before the third query would then take 10 milliseconds. The optimal strategy is to first position pointers at blocks 1, 2 and 3, before the second query move them to blocks 1, 3 and 4 in s_{2} = 1 milliseconds, and then move them to 1, 3 and 5 in s_{4} = 3 milliseconds before the fourth query. The total time is s_{2} + s_{4} = 4 milliseconds.
Input format 
Input data contains several test cases. The first line contains one integer t — the number of test cases (1 ≤ t ≤ 1000). Each of the following t test cases is described in the following way. The first line of the description contains three integers: n, k, q — the number of blocks, the number of pointers and the number of queries (1 ≤ k ≤ n ≤ 10^{5}, 1 ≤ q ≤ 10^{6}). The following line contains q integers s_{i} — time needed to move pointers if it is performed before the ith query (1 ≤ s_{i} ≤ 10^{4}). The following q lines contain queries in order they must be processed, the ith query is described by a line that first contains c_{i} — the number of blocks requested, (1 ≤ c_{i} ≤ k), followed by c_{i} integers b_{i, j} — the numbers of these blocks, given in ascending order (1 ≤ b_{i, j} ≤ n). It is guranteed that the sum of all n of one input data doesn't exceed 10^{5}, and the sum of all c_{i} in all test cases of one input data doesn't exceed 10^{6}. 

Output format 
For each test case print one integer — the minimal total time to answer all queries. 
Examples 
Input data
2 5 3 4 1 1 1 1 1 2 2 1 4 2 2 3 3 1 3 5 5 3 4 1 1 10 3 1 2 2 1 4 2 1 3 3 1 3 5
Output data
2 4 
Time limit  3 seconds 

Memory limit  256 megabytes 
Ilya is working for Laboratory of Investigation of String Algorithms (LISA). Now he is trying to solve the following problem.
You are given an array of strings s_{1}, s_{2}, ..., s_{n}, and q queries. Each query is specified by two integers: l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n). To answer the query you must do the following. Let us call a string representable if it is possible to obtain it using the following method: take two strings s_{x} and s_{y}, where l_{i} ≤ x, y ≤ r_{i}, take nonempty prefix of s_{x} and nonempty suffix of s_{y}, concatenate them. The answer to the query is the number of different representable strings for given l_{i} and r_{i}.
For example, consider s = [abc, ab, ac, bcac], take l_{i} = 2, r_{i} = 3. The following strings are representable:
x = 2, y = 2: ab = a + b, aab = a + ab, abb = ab + b, abab = ab + ab.
x = 2, y = 3: ac = a + c, aac = a + ac, abc = ab + c, abac = ab + ac.
x = 3, y = 2: ab = a + b, aab = a + ab, acb = ac + b, acab = ac + ab.
x = 3, y = 3: ac = a + c, aac = a + ac, acc = ac + c, acac = ac + ac.
So there are 12 different representable strings.
Help Ilya to solve the problem as fast as you can.
Input format 
The first line of input contains two integers: n and q — the number of strings and the number of queries (1 ≤ n, q ≤ 10^{5}). Each of the following n string contains nonempty words s_{i}, that consist of lowercase English letters. The sum of their lengths doesn't exceed 10^{5}. The following q lines contain queries: each line contains two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — parameters of the ith query. 

Output format 
Output q lines, the ith of them must contain one integer — the answer to the ith query. 
Examples 
Input data
4 3 abc ab ac bcac 3 4 1 3 2 3
Output data
20 23 12 