Third qualification round completed

Tasks

Show one task per page / all tasks on one page

"A" Spreadsheets
Time limit 1 second
Memory limit 256 megabytes

Petya is developing his own spreadsheet editor. His editor will use the following naiming for columns: the first 26 columns will be named by the letters of the alphabet: A, B, C, ..., Z. The following columns, starting from column 27, will be named using pairs of letters: AA, AB, ..., AZ, BA, BB, ..., BZ, ..., ZZ. Then triples of letters will be used: AAA, AAB, AAC, ..., then strings of four letters, and so on.

Now Petya needs to get the name of the column by its number. Help him to create the corresponding piece of code.

Input format

Input data contains several test cases. The first line of input contains an integer t — the number of test cases (1 ≤ t ≤ 1000).

The following t lines contain one integer k each (1 ≤ k ≤ 109).

Output format

For each test case output the name of the k-th column in the spreadsheet editor.

Examples
Input data
4
1
10
100
1000
Output data
A
J
CV
ALL
"B" Mortal Combat
Time limit 1 second
Memory limit 256 megabytes

Vasya has started playing a new video game. In the end of the first level he is taking a combat with the level boss. He needs to win the combat to continue playing. Vasya has a squad of n heroes, the i-th of them has hi hit points and ai attack points. The boss has H hit points and A attack points.

The combat goes as follows.

  • If Vasya has no more heroes, he loses the game.
  • If he still has at least one hero, he can choose any one and send it to fight against the boss;
  • If Vasya has chosen the i-th hero, the combat proceeds as follows:
    • The hero attacks the boss and reduces its hit points by ai;
    • If the boss is still alive — has strictly positive hit points — it attacks the hero and reduces its hit points by A;
    • While the hero and the boss are both still alive, the attacks are repeated.
  • If the boss is dead, the combat is over, Vasya wins. In the other case all of the actions are repeated.

Vasya doesn't want to lose many heroes at the very first level of the game. So he wants to plan the combat to lose the minimum possible number of heroes. Help him to find what is the minimal number of heroes that he can lose but still defeat the boss. If Vasya cannot defeat the boss even losing all of his heroes, output  - 1.

Let us consider sample test cases.

In the first test case the optimal plan is the following: first send hero 2 to the combat. It attacks the boss three times, reduce its hit points by 12, and then dies. After that Vasya must send hero 3 to the combat, it immediately reduces the hit points of the boss by 6, and the boss dies. Therefore Vasya loses one hero only.

In the second test case Vasya cannot kill the boss, no matter in which order he sends his heroes to the combat.

Input format

Input data contains multiple test cases. The first line contains one integer t — the number of test cases (1 ≤ t ≤ 1000).

Each of the t test cases is described in the following way. The first line of the description contains three integers n, H and A — the number of heroes Vasya has, the number of hit points of the boss, and the number of attack points of the boss (1 ≤ n ≤ 105, 1 ≤ H, A ≤ 109).

Each of the following n lines contains two integers hi, ai — number of hit points and attack points of the i-th hero (1 ≤ hi, ai ≤ 109).

The sum of values of n in all test cases of one input data doesn't exceed 105.

Output format

For each test case output either the minimal number of heroes that Vasya must lose to defeat the boss, or  - 1 if Vasya cannot defeat the boss.

Examples
Input data
2
4 18 4
4 5
9 4
1 6
3 3
4 27 4
4 5
9 4
1 6
3 3
Output data
1
-1
"C" A Bit Palindromic Numbers
Time limit 1 second
Memory limit 256 megabytes

Let us call the integer number a bit palindromic, if its first digit is the same as its last digit. We use decimal notation without leading zeroes. Your task is to count how many a bit palindromic numbers are there between l and r, inclusive.

The following numbers are a bit palindromic in the first sample test: 8, 9, 11, and 22.

The numbers in the second sample test — 1251 and 1261.

Input format

Input data contains multiple test cases. The first line contains one integer t — the number of test cases (1 ≤ t ≤ 5·104).

Each test case is described by a single line that contains two integers: l and r (1 ≤ l ≤ r ≤ 1018).

Output format

For each test case output one integer: how many a bit palindromic numbers are there in the given range.

Examples
Input data
3
8 25
1251 1266
12 21
Output data
4
2
0
"D" Tree and Polynomials
Time limit 2 seconds
Memory limit 256 megabytes

Nick is a freshman. He studies trees in his Algorithms class. He studies polynomials in his Algebra class. And he likes to create and combine. He has recently come up with a problem he cannot solve. Help him!

You are given a rooted tree with n vertices, numbered from 1 to n. There is a value in each vertex, initially all values are equal to 0. For a vertex v let us denote as d[v] the depth of the vertex v — the number of vertices on a path from the root of the tree to v, in particular the root itself has depth equal to 1.

You are also given k. You must process queries of two types.

  1. You are given a vertex v and a polynomial q(t) = q0 + q1t + q2t2 + ... + qktk. For each vertex u in a subtree of the vertex v you must add q(d[u]) to the value in that vertex.
  2. You are given a vertex v and a polynomial q(t) = q0 + q1t + q2t2 + ... + qktk. For each vertex u on a path from the root of the tree to v, inclusive, add q(d[u]) to the value in that vertex.

All arithmetic operations are performed modulo 109 + 7.

Help Nick to find the values in all vertices after all operations.

Input format

Input data contains multiple test cases. The first line of input data contains integer t — the number of test cases (1 ≤ t ≤ 105).

The description of test cases follow. Each description starts with two integers: n — the number of vertices in a tree, and k — the maximal degree of the polynomials (1 ≤ n ≤ 105, 1 ≤ k ≤ 20).

The following n integers p1, p2, ..., pn describe the tree, pi is the number of a parent of the vertex i, or 0, if i is the root. It is guaranteed, that pi describe the correct rooted tree.

The integer q follows — the number of queries (1 ≤ q ≤ 105). The following q lines contain queries, each query is specified by an integer t, equal to 1 or 2 — the type of the query, followed by v — the vertex in the query, and then k + 1 integers q0, q1, ..., qk — coefficients of the polynomial in the query (0 ≤ qi < 109 + 7).

It is guaranteed that the sum of values of n in all test cases of one input data doesn't exceed 105. Similarly, the sum of values of q in all test cases of one input data doesn't exceed 105.

Output format

For each test case output n integers, for each vertex print the value in this vertex after all queries. Remember to perform all operations modulo 109 + 7.

Examples
Input data
1
4 2
2 4 2 0
3
1 2 0 1 0
2 3 1 0 0
2 1 0 0 1
Output data
12 7 4 2
"E" Nice Report
Time limit 5 seconds
Memory limit 256 megabytes

Andrew is analyzing subscription graph in one social network. This graph is directed: if the user a is subscribed to the user b, it is not always the case that the user b is in turn subscribed to the user a.

Andrew's boss has asked him to find for each user x the number of users y such that it is possible to reach user y from user x in the subscription graph.

There is no reason to find the exact values, they look ugly and are non-relevant almost immediately, so Andrew wants to find approximate values. Find values that differ from the correct ones at most by a factor of two.

Input format

The first line of input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of users of the social network and the number of direct subscriptions.

The following m lines describe subscription graph, the i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), it means that the user ai is subscribed to the user bi. Each ordered pair (ai, bi) occurs at most once in the input data.

Output format

Output n integers qi — for each user print approximate number of users y such that it is possible to reach user y from user i in the subscription graph. If the correct number of such users is zi, the following inequalities must be satisfied to have the answer accepted: qi ≤ 2zi and zi ≤ 2qi. Moreover, you are allowed to bypass this restriction and output any qi for no more than 10 users.

Note: judges use exact values to check your answers. However, judges don't promise that it is possible to find exact values in each test case given time and memory constraints of this problem. They recommend to try to find approximate value.

In the given example it is possible to reach all five users from the user 1. But the given answer 7 is acceptable, it differs from 5 less than by a factor of two. Similarly, the answer 2 is acceptable for the user 4.

Examples
Input data
5 6
1 2
1 3
2 4
2 5
3 5
4 2
Output data
7
3
2
2
1

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