Description

Please compute the sum of two given n-bit binary numbers.

Input

The first line of the input file contains a positive integer t indicating the number of test cases. The first line of each test case is a positive integer n denoting the length of bits. The second and third lines are the two n-bit binary numbers. The first bit of each binary number is always 0, which guarantees that the sum of the two binary numbers can still be expressed as an n-bit binary number.

Case1 : t<=100, n<=100
Case2 : t<=200, n<=1000
Case3 : t<=300, n<=5000
Case4 : t<=400, n<=10000

Output

For each test case, your program should print the sum in the same format as the binary numbers given in input.

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).

Hint: We have a very large input. Please use scanf and printf.

Input

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 10.

Case 1: 0 < #operations <= 10^4

Case 2: 0 < #operations <= 10^5

Case 3: 0 < #operations <= 10^6

Case 4: 0 < #operations <= 10^7

Output

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

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

A calendar is a system for measuring time, from hours and minutes, to months and days, and finally to years and centuries. The terms of hour, day, month, year and century are all units of time measurements of a calender system. 
According to the Gregorian calendar, which is the civil calendar in use today, years evenly divisible by 4 are leap years, with the exception of centurial years that are not evenly divisible by 400. Therefore, the years 1700, 1800, 1900 and 2100 are not leap years, but 1600, 2000, and 2400 are leap years. 
Given the number of days that have elapsed since Saturday, January 1, 2000 A.D, your mission is to find the date and the day of the week.

Reference: Shanghai 2004 Preliminary

Input

The input consists of lines each containing a positive integer, which is the number of days that have elapsed since January 1, 2000 A.D. The last line contains an integer −1, which should not be processed. 
You may assume that the resulting date won’t be after the year 9999.

Output

For each test case, output one line containing the date and the day of the week in the format of "YYYY-MM-DD DayOfWeek", where "DayOfWeek" must be one of "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday" and "Saturday".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a number sequence S = {S₁, S₂, S₃, …, S_n}, we called (i,j) an “inversion pair” when S_i > S_j and i < j.  Given S, calculate the number of inversion pair in this sequence.

Input

There are several numbers of test cases. Each case begins with an integer N in a line, and then N integers N₁~N_nfollow, each in a single line. The input is terminated by the number zero.
For case 1, 1<=N<=10, 0<=N_i<=100, the answer <2³¹.
For case 2, 1<=N<=100, 0<=N_i<=10⁶, the answer <2³¹.
For case 3, 1<=N<=1000, -2³¹<=N_i<2³¹, the answer <2³¹.
For case 4, 1<=N<=10⁶ , -2³¹<=N_i<2³¹, the answer <2⁶³.

Output

For each test case, print a number of inversion pairs in the given sequence.
Hint: merge sort

Sample Input  Download

Sample Output  Download

Tags

Discuss