2017 ACM Amman Collegiate Programming Contest
A. Watching TV
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmed spends most of his day watching TV. His father noticed that his academic performance is degrading and decided to help him get back on track, for that he will allow him to choose only one frequency and watch the channels that share the same frequency band.

Can you help Ahmed choose the best frequency which is the one that displays the largest number of channels?

Input

The first line of the input contains an integer T (1  ≤  T  ≤  100), where T is the number of test cases. Then T test cases follow.

The first line of each test case contains an integer N (1  ≤  N  ≤  104), where N is the total number of channels.

Then N lines follow, each line contains a string S and an integer F (11111  ≤  F  ≤  99999), where S is the name of the channel and F is its frequency.

All strings are non-empty consisting of lowercase English letters. The length of each of these strings does not exceed 50 characters.

It is possible that two different channels have the same name and frequency.

Output

Print T lines, each line contains a single integer that represents the frequency Ahmed will choose. If there are several solutions, print the one with the minimum frequency.

Example
Input
3
3
mbcone 12015
mbctwo 12015
mbcthree 12014
2
channelone 11112
channelyou 21112
1
watchme 12345
Output
12015
11112
12345

B. Longest Prefix
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two strings a and b. Find the longest common prefix between them after performing zero or more operation on string b. In each operation you can swap any two letters.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 500), where T is the number of the test cases.

Each case has one line that contains two space separated strings a and b.

All strings are non-empty consisting of lowercase English letters only. The length of each of these strings does not exceed 105 characters.

Output

Print T lines, each line contains a single integer that represents the length of the longest common prefix between a and b.

Example
Input
3
hello hey
here there
you me
Output
2
4
0

C. Lunch Break
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hasan decided to invite his colleagues and buy them lunch from his favorite restaurant. As usual, he got carried away and forgot to order early, for that he decided to help the delivery guy.

There are 3 different roads that the delivery guy can choose from. Given the length of each road, what is the best one that he can choose to deliver the food as soon as possible?

Input

The first line of the input contains an integer T (1 ≤ T ≤ 105), where T is the number of the test cases.

Each test case has one line that contains three distinct integers a, b and c (1 ≤ a, b, c ≤ 109), the lengths of the three different roads from the restaurant to Hasan's company.

Output

For each test case, print "First" (without quotations) if the delivery guy should choose the first road, "Second" (without quotations) if he should choose the second road, "Third" (without quotations) if he should choose the third way.

Example
Input
3
5 10 7
20 3 9
8 15 2
Output
First
Second
Third

D. Counting Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Consider an infinite binary tree with each node has exactly two children, and two given integers a and b, count the number of paths in the infinite binary tree that satisfy the following rules:

  • The path starts from the root of the tree.
  • The length of the path is equal to a (The length of a path is the total number of edges from the root to the final node on that path).
  • The number of change of direction along the path is equal to b. Change of direction means, going to your right child if you are the left child of your parent or vise versa.

As the number of paths can be too large, print it (modulo 109 + 7).

Input

The first line of the input contains an integer T (1 ≤ T ≤ 105), where T is the number of the test cases.

Each test case has one line that contains two integers a and b (0 ≤ b < a ≤ 105), the length of the path and the number of change of direction along it.

Output

For each test case, print a single integer that represents the number of paths that satisfy the mentioned rules (modulo 109 + 7).

Example
Input
2
2 1
4 3
Output
2
2

E. Car Factory
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a car factory each car needs to go through k stages in order to be ready for sale, and each stage needs one day to be completed.

The process in the factory goes as follows. On the first day a car enters the first stage. On the second day a car moves from the first stage to the second stage, and a new car enters the first stage. On the third day a car moves from the second stage to the third stage, a car moves from the first stage to the second stage, and a new car enters the first stage, and so on. After k days (i.e. k stages) the car will be ready for sale.

Your task is simple, given the number of stages for each car to be ready, and the number of cars to be manufactured. How many days are needed to finish manufacturing all the cars?

Input

The first line of the input contains an integer T (1  ≤  T  ≤  1000), where T is the number of the test cases.

Each test case has one line that contains two integers n and k (1  ≤  n, k  ≤  109), the number of cars to be manufactured and the number of stages each car requires.

Output

For each test case, print a single integer that represents the number of required days to manufacture all the cars.

Examples
Input
4
1 1
2 3
4 3
14526 78965
Output
1
4
6
93490
Note

Let's solve the third case to show how the process goes in the factory:

  • First day: The first car will enter the first stage.
  • Second day: The first car will move to the second stage, and the second car will enter the first stage.
  • Third day: The first car will move to the third stage, the second car will move to the second stage, and the third car will enter the first stage. At the end of this day the first car will be ready for sale.
  • Fourth day: The second car will move to the third stage, the third car will move to the second stage, and the fourth car will enter the first stage. At the end of this day the second car will be ready for sale.
  • Fifth day: The third car will move to the third stage, and the fourth car will move to the second stage. At the end of this day the third car will be ready for sale.
  • Sixth day: The fifth car will move to the third stage. At the end of this day the fourth car will be ready for sale.
F. Cooking Time
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While cooking your dinner, you will need n ingredients. Initially, all ingredients are in the refrigerator.

You are not allowed to keep more than k ingredients outside the refrigerator at the same time. If there are k ingredients outside the refrigerator, and you need to use another ingredient from it, then you must do the following:

  1. Open the refrigerator.
  2. Return an ingredient that is currently outside.
  3. Take the required ingredient.

Whenever you need an ingredient, you will open the refrigerator only if it's not outside. Each time you open the refrigerator you can take only one item. Your task is to minimize the number of times you will need to open the refrigerator.

Input

The first line contains an integer T (1  ≤  T  ≤  100), where T is the number of test cases.

Each case contains two lines. The first line contains two integers n and k (1  ≤  n, k  ≤  105), the number of ingredients needed, and the maximum allowed number of ingredients that can be kept outside the refrigerator at the same time.

The second line contains n integers a1, a2, ..., an (1  ≤  ai  ≤  109), where ai is the ID of the ith ingredient you will need. Ingredients must be used in the order given in the input.

Output

For each test case, print a single integer that represents the minimum number of times you will open the refrigerator.

Example
Input
2
5 3
2 4 5 2 1
7 3
1 2 3 4 3 2 1
Output
4
5
Note

In the first test case, you can keep up to 3 items outside the refrigerator. You must open the refrigerator 3 times to use the first three ingredients (2, 4, and 5), and then keep them outside the refrigerator. The fourth ingredient (2) is already outside the refrigerator, so you can use it directly. You cannot use the fifth item because there are 3 items outside the refrigerator, so you must open the refrigerator, return an item, and take the fifth ingredient from the refrigerator and use it.

G. Super Subarray
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this problem, subarray is defined as non-empty sequence of consecutive elements.

We define a subarray as Super Subarray if the summation of all elements in the subarray is divisible by each element in it.

Given an array a of size n, print the number of Super Subarrays in a.

Input

The first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 2000), the length of array a.

The second line of each test case contains the sequence of elements of the array a1, a2, ..., an (1 ≤ ai ≤ 109), ai is the i-th element of the array a.

Output

For each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.

Example
Input
2
5
1 2 3 4 5
5
2 3 4 3 6
Output
6
6

H. Palindrome Number
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A palindrome number is a number that can be read the same way from left to right and from right to left. For example: 961169, 111, 554455 are palindromes, while 856, 10180, 7226 are not.

Find the largest palindrome number that satisfies the following rules:

  • The number of its digits is equal to n, and must not contain leading zeros.
  • The sum of its digits is equal to s.

If there is no such number print  - 1.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 500), where T is the number of the test cases.

Each test case has one line that contains two integers n (1 ≤ n ≤ 106) number of digits, and s (1 ≤ s ≤ 9 × 106) sum of digits.

Output

For each test case, print a single integer that represents the largest palindrome number that satisfies the mentioned rules, if there is no such number print  - 1.

Example
Input
2
2 2
4 26
Output
11
9449

I. Rock Piles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hasan and Abdullah are lost in the desert, they are waiting for the rescue squad to help them. While they are waiting, they decided to invent a new game called Rock Piles.

In this game, there are two rock piles. The first pile contains N rocks, and the second one contains M rocks. Hasan and Abdullah take turns to play the game, Hasan starts first. In each turn, a player can choose to take one rock from a single pile, or take one rock from both piles. The player who cannot make any move, loses the game. Determine who will win if both of them play optimally.

Input

The first line of the input contains an integer T (1  ≤  T  ≤  104), where T is the number of the test cases.

Each test case has one line that contains two integers N and M (0  ≤  N, M  ≤  109), the number of rocks in the first and second pile respectively.

Output

For each test case, print a single line with the winner's name. If Hasan wins print "hasan", otherwise print "abdullah" (without quotes).

Example
Input
2
2 3
4 0
Output
hasan
abdullah

J. Spilt the String
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string s consisting of lowercase English letters and spaces, find a way to split the string s into multiple lines of the same length. Leading and trailing spaces are ignored while computing the length of the new lines.

Note that you cannot split words, for example if s contains the word "amman", the whole word must be on the same line.

If there is a way to split s into multiple lines print "YES" (without the quotes), otherwise print "NO" (without the quotes).

Input

The first line of the input contains an integer T (1  ≤  T  ≤  250), where T is the number of the test cases.

Each case has one line that contains a string s. All strings are non-empty and the length of each of these strings does not exceed 105 characters.

It is guaranteed that there is only one space between any two words, and there are no leading or trailing spaces in s.

Output

Print T lines, on each line print "YES" (without the quotes) if you can split the given string s into multiple lines of the same length. Otherwise, print "NO" (without the quotes).

Example
Input
2
acm arab collegiate programming contest
acm amman collegiate programming contest
Output
YES
NO
Note

In first test case, "acm arab collegiate programming contest", the only possible solution is:

acm arab collegiate

programming contest

In second test case, "acm amman collegiate programming contest", there is no solution.

K. Two Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this problem, subarray is defined as non-empty sequence of consecutive elements of an array.

The strength of an array Z of size K is computed as follows:

Given an array A of size N, find the maximum possible absolute difference between the strengths of two non-intersecting subarrays of A.

Two subarrays intersect if they have common indices.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

Each case contains two lines. The first line contains an integer N (2 ≤ N ≤ 105), the size of the array A.

The second line contains N space-separated integers representing the elements of the array A ( - 109 ≤ Ai ≤ 109).

Output

For each test case, print the maximum possible absolute difference on a single line.

Example
Input
3
4
0 1 2 100
6
-9 1 -3 5 4 2
5
4 3 2 3 4
Output
101
22
5

L. The Shortest Path
time limit per test
3 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed weighted graph with N nodes and M edges. Your task is to find the minimum shortest path between any pair of nodes in the graph. As the weight of the edges can be negative, the path is allowed to visit the same node multiple times.

Formally, let F(u, v) be the shortest path between the two nodes u and v, find the minimum F(u, v) over all pairs (u, v) (1 ≤ u, v ≤ N) (u ≠ v). If there is no path between a pair of nodes u and v, then F(u, v) = ∞.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.

The first line of each test case contains two integers N and M (2 ≤ N ≤ 2000) (1 ≤ M ≤ 5000), where N is the number of nodes in the graph, and M is the number of edges.

Each of the following M lines contains three integers U, V and C (1 ≤ U, V ≤ N) (U ≠ V) ( - 106 ≤ C ≤ 106), representing that there is an edge from node U to node V with cost C.

Note that the graph may contain multiple edges between the same pair of nodes in the same direction.

Output

For each test case, print the minimum length of a shortest path in the graph, or "-inf" if the length of the shortest path is negative infinity.

Example
Input
3
3 3
1 2 -1
2 3 -3
3 1 -5
4 5
1 3 0
1 2 -2
2 3 3
3 4 1
4 1 -1
4 4
1 2 5
2 3 -3
3 4 -3
1 4 2
Output
-inf
-3
-6

M. Restore Points
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami has n points that lie on the non-negative part of the x-axis. One of the points is always at 0. He wrote down the distances between each pair of points in some arbitrary order.

Asem accidentally erased Rami's points, and he wants to restore them before Rami finds out. Can you help Asem restore the coordinates of the points?

Input

The first line of the input contains an integer T the number of the test cases.

Each case contains two lines. The first line contains an integer n (2  ≤  n  ≤  18), the number of points Rami has.

The second line contains m integers d1, d2, ..., dm (0  ≤  di  ≤  106), where m = , the distances between each pair of points.

Output

Print T lines. Each line contains n integers p1, p2, ..., pn which represent the coordinates of the points in ascending order.

It is guaranteed that an answer always exists. If there is more than one solution, you can print any of them.

Example
Input
2
3
2 3 5
4
5 3 2 3 8 6
Output
0 3 5
0 3 6 8