Description

Given a string S, output the reverse of S.

Case 1: |S|<=100
Case 2: |S|<=1000
Case 3: |S|<=10000
Case 4: |S|<=1000000

Input

The input consists of multiple lines. Each line is a string S with length <= 1000000. The number of test case is less than 100.
Each string consists of "a-z", "A-Z", "0-9", "+ - * / ^ %" and " "(spaces).

Output

Output the reverse of S.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.

Input

First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10^8.

9324 : a,b are smaller than 100.
9325 - 9327 : a,b are smaller than 10^8.

Output

For each case, output the GCD of a and b in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You need to write a program to simulate a queue of names.  Each name is a string consisting of English letters only.  There are three operations:

1.         “Push [name]”, which means to enque name in the queue.

2.         “Pop”, which means to deque. If the queue is empty, this operation takes no effect.

3.         “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).

Input

There will be at most 10⁷ operations.  Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 20.
Case 1 : at most 10³ operations
Case 2 : at most 10⁵ operations
Case 3 : at most 10⁷ operations
Case 4 : at most 10⁷ operations

Output

For each “Front” operation, print out the name in the front of the queue.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an article, find the number of appearance for queried strings.

Input

The input includes multiple test cases. In each test case, the first line contains two integers, N and M (1 <= N <= 10, 1 <= M <= 100). N indicates the number of lines in the article, and M indicates the number of strings needs to search. The next N lines are for the article, and the length of each line <= 1000. The followed M lines contains M queries, one per line, the length of each query <= 20. The alphabet of query is (a-z, A-Z) and digit (0-9).

case 1: line length <= 100, query length <= 12
case 2: line length <= 100, query length <= 20
case 3: line length <= 500, query length <= 20
case 4: line length <= 1000, query length <= 20

Output

For each string, output the string and the number of appearance in the article, separate by ‘:’. Uppercase and lowercase are treated as the same alphabet.
Print a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You will be given an IC design graph with several connected chips components. In order to improve the design, your job is to find out the component with the largest number of chips. A connected chips component is a subset of chips in which any two chips are connected to each other by paths, and which is connected to no additional chips.

Input

There will be several test cases. In each test case, the first line will be an integer N representing the number of chips. The second line contains an integer K which is the number of wires. In the next K lines, each line contains two integers, A and B (0 <= A, B < N), which denotes that there is a wire between chip #A and chip #B. If N = 0, the input ends. Chips are numbered from 0~N-1.
Case 1: 1<=N<=10, 1<=K<=N^2
Case 2: 1<=N<=100, 1<=K<=N^2
Case 3: 1<=N<=1000, 1<=K<=min {N^2, 100000}
Case 4: 1<=N<=200000, 1<=K<=min {N^2, 200000}

Output

For each design graph, print the number of chips for the largest connected chips component.

Sample Input  Download

Sample Output  Download

Tags

Discuss