Final round completed

Tasks

Show one task per page / all tasks on one page

"A" Set Theory
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 ai on a blackboard. Now he asks Masha to create a set B containing n different integers bj such that all n2 integers that can be obtained by summing up ai and bj 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 106, 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 ai — the elements of A (1 ≤ ai ≤ 106).

Output format

For each test first print the answer:

  • NO, if Masha's task is impossible to solve, there is no way to create the required set B.
  • YES, if there is the way to create the required set. In this case the second line must contain n different positive integers bj — elements of B (1 ≤ bj ≤ 106). If there are several possible sets, output any of them.

Examples
Input data
3
3
1 10 100
1
1
2
2 4
Output data
YES
1 2 3 
YES
1 
YES
1 2 
"B" Similar Words
Time limit 4 seconds
Memory limit 512 megabytes

Let us call a non-empty 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 non-empty 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 ≤ 106). Each of the following n lines contains one non-empty 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 106.

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
"C" Eleventh Birthday
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 i-th card has the number ai 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 ai (1 ≤ ai ≤ 109) — 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
"D" Masha and Cactus
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·105; 0 ≤ m ≤ 2·105).

Let us describe Masha's tree. It has a root at vertex 1. The second line contains n - 1 integers: p2, p3, ..., pn, here pi — is the parent of a vertex i — the first vertex on a path from the vertex i to the root of the tree (1 ≤ pi < i).

The following m lines contain three integers ui, vi and ci — pairs of vertices to be connected by the additional edges that Masha can add to the tree and beauty of edge (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104).

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
"E" Satellites
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 half-planes 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 half-plane.

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. 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 i-th satellite in order of launching, starting from one.
  2. 2 i — remove satellite number i.
  3. 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 half-circle 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 ≤ 109, 1 ≤ n ≤ 5·105).

Each of the following n lines describe events in the specified format.

Satellite coordinates are integer, the satisfy the following constraints |x| ≤ 109, 0 < y ≤ 109. 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
"F" To Play or not to Play
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 [a1;b1], [a2;b2], ..., [an;bn], and Petya can only play during intervals [c1;d1], [c2;d2], ..., [cm;dm]. 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·105, 0 ≤ C ≤ 1018).

The following n lines contain two integers each: ai, bi — intervals when Vasya can play (0 ≤ ai < bi ≤ 1018, bi < ai + 1).

The following m lines contain two integers each: ci, di — intervals when Petya can play (0 ≤ ci < di ≤ 1018, di < ci + 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

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook It.Mail

Forgot password?

Registration

The instruction for password recovery
has been sent to your email