Final round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Masha and Grisha like studying sets of positive integers.
One day Grisha has written a set A containing n different integers a_{i} on a blackboard. Now he asks Masha to create a set B containing n different integers b_{j} such that all n^{2} integers that can be obtained by summing up a_{i} and b_{j} for all possible pairs of i and j are different.
Both Masha and Grisha don't like big numbers, so all numbers in A are from 1 to 10^{6}, and all numbers in B must also be in the same range.
Help Masha to create the set B that satisfies Grisha's requirement.
Input format 
Input data contains multiple test cases. The first line contains an integer t — the number of test cases (1 ≤ t ≤ 100). Each test case is described in the following way: the first line of the description contains one integer n — the number of elements in A (1 ≤ n ≤ 100). The second line contains n integers a_{i} — the elements of A (1 ≤ a_{i} ≤ 10^{6}). 

Output format 
For each test first print the answer:

Examples 
Input data
3 3 1 10 100 1 1 2 2 4
Output data
YES 1 2 3 YES 1 YES 1 2 
Time limit  4 seconds 

Memory limit  512 megabytes 
Let us call a nonempty sequence of lowercase English letters a word. Prefix of a word x is a word y that can be obtained from x by removing zero or more last letters of x.
Let us call two words similar, if one of them can be obtained from the other by removing its first letter.
You are given a set S of words. Find the maximal possible size of set of nonempty words X such that they satisfy the following:
 each word of X is prefix of some word from S;
 X has no similar words.
Input format 
Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases. The descriptions of test cases follow. The first line of each description contains an integer n — the number of words in the set S (1 ≤ n ≤ 10^{6}). Each of the following n lines contains one nonempty word — elements of S. All words in S are different. It is guaranteed that the total length of all words in one input data doesn't exceed 10^{6}. 

Output format 
For each test case print one line that contains one integer m — the maximal number of words that X can contain. 
Examples 
Input data
2 3 aba baba aaab 2 aa a
Output data
6 1 
Time limit  4 seconds 

Memory limit  512 megabytes 
It is Borya's eleventh birthday, and he has got a great present: n cards with numbers. The ith card has the number a_{i} written on it. Borya wants to put his cards in a row to get one greater number. For example, if Borya has cards with numbers 1, 31, and 12, and he puts them in a row in this order, he would get a number 13112.
He is only 11, but he already knows that there are n! ways to put his cards in a row. But today is a special day, so he is only interested in such ways that the resulting big number is divisible by eleven. So, the way from the previous paragraph is good, because 13112 = 1192 × 11, but if he puts the cards in the following order: 31, 1, 12, he would get a number 31112, it is not divisible by 11, so this way is not good for Borya. Help Borya to find out how many good ways to put the cards are there.
Borya considers all cards different, even if some of them contain the same number. For example, if Borya has two cards with 1 on it, there are two good ways.
Help Borya, find the number of good ways to put the cards. This number can be large, so output it modulo 998244353.
Input format 
Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases (1 ≤ t ≤ 100). The descriptions of test cases follow. Each test is described by two lines. The first line contains an integer n (1 ≤ n ≤ 2000) — the number of cards in Borya's present. The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^{9}) — numbers written on the cards. It is guaranteed that the total number of cards in all tests of one input data doesn't exceed 2000. 

Output format 
For each test case output one line: the number of ways to put the cards to the table so that the resulting big number was divisible by 11, print the number modulo 998244353. 
Examples 
Input data
4 2 1 1 3 1 31 12 3 12345 67 84 9 1 2 3 4 5 6 7 8 9
Output data
2 2 2 31680 
Time limit  4 seconds 

Memory limit  256 megabytes 
Masha is fond of cacti. When she was a little girl, she decided to plant a tree. Now Masha wants to make a nice cactus out of her tree.
Recall that tree is a connected undirected graph that has no cycles. Cactus is a connected undirected graph such that each vertex belongs to at most one cycle.
Masha has some additional edges that she can add to a tree. For each edge she knows which vertices it would connect and the beauty of this edge. Masha can add some of these edges to the graph if the resulting graph is a cactus. Beauty of the resulting cactus is sum of beauties of all added edges.
Help Masha find out what maximum beauty of the resulting cactus she can achieve.
Input format 
The first line of the input data contains two integers n and m — the number of vertices in a tree, and the number of additional edges available (3 ≤ n ≤ 2·10^{5}; 0 ≤ m ≤ 2·10^{5}). Let us describe Masha's tree. It has a root at vertex 1. The second line contains n  1 integers: p_{2}, p_{3}, ..., p_{n}, here p_{i} — is the parent of a vertex i — the first vertex on a path from the vertex i to the root of the tree (1 ≤ p_{i} < i). The following m lines contain three integers u_{i}, v_{i} and c_{i} — pairs of vertices to be connected by the additional edges that Masha can add to the tree and beauty of edge (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}; 1 ≤ c_{i} ≤ 10^{4}). It is guaranteed that no additional edge coincides with the edge of the tree. 

Output format 
Output one integer — the maximum beauty of a cactus Masha can achieve. 
Examples 
Input data
7 3 1 1 2 2 3 3 4 5 1 6 7 1 2 3 1
Output data
2 
Time limit  4 seconds 

Memory limit  256 megabytes 
Real Cosmic Communications is the largest telecommunication company on a far far away planet, located at the very edge of the universe. RCC launches communication satellites.
The planet is at the very edge of the universe, so its form is half of a circle. Its radius is r, the ends of its diameter are points A and B. The line AB is the edge of the universe, so one of the halfplanes contains nothing, neither the planet, nor RCC satellites, nor anything else. Let us introduce coordinates in the following way: the origin is at the center of AB segment, OX axis coincides with line AB, the planet is completely in y > 0 halfplane.
The satellite can be in any point of the universe, except the planet points. Satellites are never located beyond the edge of the universe, nor on the edge itself — that is, they have coordinate y > 0. Satellite antennas are directed in such way that they cover the angle with the vertex in the satellite, and edges directed to points A and B. Let us call this area the satellite coverage area.
The picture below shows coordinate system and coverage area of a satellite.
When RCC was founded there were no satellites around the planet. Since then there have been several events of one of the following types:
 1 x y — launch the new satellite and put it to the point (x, y). Satellites never move and stay at the point they were launched. Let us assign the number i to the ith satellite in order of launching, starting from one.
 2 i — remove satellite number i.
 3 i j — make an attempt to create a communication channel between satellites i and j. To create a communication channel a repeater is required. It must not be located inside the planet, but can be located at its halfcircle border, or above it. Repeater must be in coverage area of both satellites i and j. To avoid signal interference, it must not be located in coverage area of any other satellite. Of course, the repeater must be within the universe, it must have a coordinate y > 0.
For each attempt to create a communication channel you must find out whether it is possible.
Sample test has the following satellites locations:
Input format 
The first line of input data contains integers r and n — radius of the planet and the number of events (1 ≤ r ≤ 10^{9}, 1 ≤ n ≤ 5·10^{5}). Each of the following n lines describe events in the specified format. Satellite coordinates are integer, the satisfy the following constraints x ≤ 10^{9}, 0 < y ≤ 10^{9}. No two satellites that simultaneously exist can occupy the same point. Distance from each satellite to the center of the planet is strictly greater than r. It is guaranteed that events of types 2 and 3 only refer to satellites that exist at the moment. For all events of type 3 the inequality i ≠ j is satisfied. 

Output format 
For each event of type 3 print «YES» on a separate line, if it is possible to create a communication channel, or «NO» if it is impossible. 
Examples 
Input data
5 8 1 5 8 1 4 8 1 3 8 1 2 7 3 1 3 2 2 3 1 3 3 3 4
Output data
NO YES YES 
Time limit  4 seconds 

Memory limit  256 megabytes 
Vasya and Petya are playing an online game. As most online games, it has hero progress system that allows players to gain experience that make their heroes stronger. Of course, Vasya would like to get as many experience points as possible. After careful study of experience points allocation, he found out that if he plays the game alone, he gets one experience point each second. However, if two players are playing together, and their current experience values differ by at most C points, they can boost their progress, and each of them gets 2 experience points each second.
Since Vasya and Petya are middle school students, their parents don't allow them to play all the day around. Each of the friends has his own schedule: Vasya can only play during intervals [a_{1};b_{1}], [a_{2};b_{2}], ..., [a_{n};b_{n}], and Petya can only play during intervals [c_{1};d_{1}], [c_{2};d_{2}], ..., [c_{m};d_{m}]. All time periods are given in seconds from the current moment. Vasya is good in math, so he has noticed that sometimes it can be profitable not to play alone, because experience difference could become too big, and progress would not be boosted even when played together.
Now they would like to create such schedule of playing that Vasya's final experience was greatest possible. The current players experience is the same. Petya is not so concerned about his experience, so he is ready to cooperate and play when needed to maximize Vasya's experience.
Input format 
The first line of input data contains integers n, m and C — the number of intervals when Vasya can play, the number of intervals when Petya can play, and the maximal difference in experience level when playing together still gives a progress boost (1 ≤ n, m ≤ 2·10^{5}, 0 ≤ C ≤ 10^{18}). The following n lines contain two integers each: a_{i}, b_{i} — intervals when Vasya can play (0 ≤ a_{i} < b_{i} ≤ 10^{18}, b_{i} < a_{i + 1}). The following m lines contain two integers each: c_{i}, d_{i} — intervals when Petya can play (0 ≤ c_{i} < d_{i} ≤ 10^{18}, d_{i} < c_{i + 1}). 

Output format 
Output one integer — the maximal experience that Vasya can have in the end, if both players try to maximize this value. 
Examples 
Input data
2 1 5 1 7 10 20 10 20
Output data
25 
Input data
1 2 5 0 100 20 60 85 90
Output data
125 