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?
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.
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.
3
3
mbcone 12015
mbctwo 12015
mbcthree 12014
2
channelone 11112
channelyou 21112
1
watchme 12345
12015
11112
12345
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.
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.
Print T lines, each line contains a single integer that represents the length of the longest common prefix between a and b.
3
hello hey
here there
you me
2
4
0
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?
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.
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.
3
5 10 7
20 3 9
8 15 2
First
Second
Third
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:
As the number of paths can be too large, print it (modulo 109 + 7).
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.
For each test case, print a single integer that represents the number of paths that satisfy the mentioned rules (modulo 109 + 7).
2
2 1
4 3
2
2
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?
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.
For each test case, print a single integer that represents the number of required days to manufacture all the cars.
4
1 1
2 3
4 3
14526 78965
1
4
6
93490
Let's solve the third case to show how the process goes in the factory:
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:
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.
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.
For each test case, print a single integer that represents the minimum number of times you will open the refrigerator.
2
5 3
2 4 5 2 1
7 3
1 2 3 4 3 2 1
4
5
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.
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.
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.
For each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.
2
5
1 2 3 4 5
5
2 3 4 3 6
6
6
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:
If there is no such number print - 1.
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.
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.
2
2 2
4 26
11
9449
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.
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.
For each test case, print a single line with the winner's name. If Hasan wins print "hasan", otherwise print "abdullah" (without quotes).
2
2 3
4 0
hasan
abdullah
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).
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.
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).
2
acm arab collegiate programming contest
acm amman collegiate programming contest
YES
NO
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.
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.
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).
For each test case, print the maximum possible absolute difference on a single line.
3
4
0 1 2 100
6
-9 1 -3 5 4 2
5
4 3 2 3 4
101
22
5
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) = ∞.
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.
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.
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
-inf
-3
-6
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?
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.
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.
2
3
2 3 5
4
5 3 2 3 8 6
0 3 5
0 3 6 8