Description

Given the grades of N people. Please output the sorted result. (Increasing order)

Input

The input includes multiple test cases.

In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.

1 <= |Si| <= 10
0 <= Gi <= 100 (Gi is an integer.)

Test Case 1 : 1 <= N <= 10²
Test Case 2 : 1 <= N <= 10⁴
Test Case 3 : 1 <= N <= 10⁵
Test Case 4 : 1 <= N <= 10⁶

Output

For every test case, output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a simple, undirected weighted graph G = (V, E, W), output the weight of its minimum spanning tree.

Input

The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node N and the number of the edges M. In the following M lines, each line contains three integers (s_i, e_i, c_i), 1 <= s_i, e_i <= N, 1 <= c_i <= 100, representing the indices of end vertices of an edge and the weight of the edge.

Case 1: 2 <= N <= 10², 1 <= M <= 10³
Case 2: 2 <= N <= 10³, 1 <= M <= 10³
Case 3: 2 <= N <= 10³, 1 <= M <= 10⁴
Case 4: 2 <= N <= 10³, 1 <= M <= 10⁵

Output

For each case, output a single line that indicates the weight of the minimum spanning tree of the graph.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. A group of n students are arranged to sit in a circular table.
We assume that student j (mod n) is sitting on the
right of student j+1 (mod n).

2. Each student is given some amount of candies initially.
In particular, let A[1...n] be an array such that A[j] denotes
the candies of student j have, and the value A[j] is set to
a certain number at the beginning.

3. Then we repeat the following procedures until all students have the
same number of candies:

(i) [everyone-gets-even-candies]
If a student has odd number of candies, the student receives
one extra candy from the teacher. Else, no change.
(ii) [everyone-passes-half]
Each student passes half of his/her candies to the student on
its right.

Example: n = 3, A[1] = 2, A[2] = 4, A[3] = 8.

In the first round:
student 1 passes one candy to student 3;
student 2 passes two candies to student 1;
student 3 passes four candies to student 2.

After the first round, the array A is updated to:
A[1] = 3, A[2] = 6, A[3] = 5;

In the second round:
We first make the entries of A even:
A[1] = 4, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes two candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the second round, the array A is updated to:
A[1] = 5, A[2] = 6, A[3] = 5;

In the third round:
We first make the entries of A even:
A[1] = 6, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes three candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the third round, the array A is updated to:
A[1] = 6, A[2] = 6, A[3] = 6;

Now everyone gets the same number of candies, and we stop.

Input

The first line contains the number t of test cases.
Each test case is described by
(i) the number n of students and
(ii) a sequence of n integers for A[1...n].

Case 1. 1<=t<=3, 1<=n<=10, 1<=A[j]<=10
Case 2. 2<=t<=6, 1<=n<=20, 1<=A[j]<=20
Case 3. 3<=t<=9, 1<=n<=50, 1<=A[j]<=50
Case 4. 4<=t<=10, 1<=n<=100, 1<=A[j]<=100

Output

The output contains t lines.
Each line prints the number of candies of student 1 (A[1]) when we stop.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

For case 1,2 : 1<N<100. 0<=length<100

For case 3,4 : 1<N<1000. 0<=length<1000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two sets of numbers, output their intersection set.

Input

There are multiple test cases.

Each case contains four lines.

The first line begins with an integer N.

The second line contains N integers, representing the numbers in the first set.

The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.

All the numbers are 32 bit signed integers.

The input is terminated if N = 0.

For case 1, 1 <= N, M <= 10³
For case 2, 1 <= N, M <= 10⁴
For case 3, 1 <= N, M <= 10⁵
For case 4, 1 <= N, M <= 10⁶

Output

For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print 「empty」 (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss