Description

Palindrome is a string that is identical to its reverse, like "level" or "aba". Check whether a given string is a palindrome or not.

Input

The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000. The number of test case is less than 1000.

Problem size for the four testcases
0 < length of each string < 1000
0 < length of each string < 10000
0 < length of each string < 100000
0 < length of each string < 100000

Output

For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mode means the most frequent value in a data set. Given a sequence of integers, find out their mode.

Input

There are several numbers of test cases. Each case begins with an integer N. The next line contains N integers separated by a blank space. Each number is less than 1000 and greater than 0. The input is terminated if N = 0.

Problem size for the four testcases
1 <= N <= 1000 (1 second)
1 <= N <= 10000 (1 second)
1 <= N <= 1000000 (1 second)
1 <= N <= 10000000 (3 seconds)

Output

For each test case, print the mode of the sequence. If the mode is not unique, print the smallest one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Maintain a doubly linked list, which supports the following operations:

(1) IH i : Insert a new integer i to the head of the list.

(2) IT i : Insert a new integer i to the tail of the list.

(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.

(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.

(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.

To improve the performance, it is suggested that three pointers be maintained: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.

Input

There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains no more than 500000 operations, and it is terminated by end-of-file (EOF). You may assume that i will fit in a 32-bit signed integer. The list is initially empty.

Output

For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Mid-Square hash function works as follows.

(1) The number of hash values is 65536, which are numbered from 0 to 65535.

(2) To obtain the hash value for an integer, the hash function squares the key and return 16 bits from the middle of the square; key is considered as a 32-bit unsigned integer.

Input will contain these commands:

(1) INSERT i – Insert the integer i into the hash.

(2) DELETE i – Delete the integer i from the hash, i will be in the hash table.

(3) PRINT i – Print the elements that have the same address as integer i in the hash table.

Input

There is only one data set in the input. Each line contains a single command. The range of the given integer is considered as a 32-bit unsigned integer, and the number of commands will be no more than 200000. The input is terminated by end-of-file (EOF), and the hash table is initially empty.

Output

For each “PRINT” command, output a line which contains integers of the same address as the given integer i in ascending order, including i. Each distinct integer should appear exactly once, and a single space character should be printed to separate two successive integers. In case that i is not found in the hash, print “Null” instead, even there are other integers in the same address of the hash table.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a tree, and the distance between two vertices is the minimum number of edges to traverse from one to the other. Then, the diameter of a tree is defined to be the maximum distance between any two vertices. Please find the diameter of the tree.

The diameter can be found by the following steps:
1. Pick any vertex v and perform BFS starting from v.
2. Let u be one of the vertex that is farthest away from v.
3. Perform BFS starting from u.
4. Let w be one of the vertex that is farthest away from u.
5. Output the distance between u and w as the answer.

Input

The first line of input is an integer T (T <= 40) denoting the number of cases following.
For each case, the first line contains an integer N, denoting the number of nodes. Nodes are numbered from 1 to N. Then N-1 lines follows, each line contains two numbers of node which are connected by an edge.
Cases are separated by a blank line.

Problem size for the four testcases
1 < N < 10
1 < N < 100
1 < N < 1000
1 < N < 200000

Output

For each case a line, output the diameter.

Sample Input  Download

Sample Output  Download

Tags

Discuss