ACM International Collegiate Programming Contest, Amman Collegiate Programming Contest (2018)
A. Careful Thief
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are consecutive buildings numbered from 1 to 109 each of which has an amount of money in it. The money is given in the form of m non-overlapping segments, in which each segment i has 3 values: li, ri, and vi, meaning that each building with number x (li ≤ x ≤ ri) has vi amount of money.

A thief came to rob the city, however, this thief does not want to get caught, so he can only rob at most k consecutive buildings, such that if he starts robbing buildings from building z, he can rob all buildings in the range inclusive.

Your task is to find the maximum amount of money the thief can collect. Can you?

Input

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

The first line of each test case contains two integers m and k (1 ≤ m ≤ 105, 1 ≤ k ≤ 109), in which m is the number money segments, and k is the maximum number of consecutive buildings the thief can rob.

Then m lines follow, giving the description of money segments. Each segment i is represented by 3 integers li, ri and vi (1 ≤ li ≤ ri ≤ 109, 1 ≤ vi ≤ 109), in which li and ri are the boundaries of the segment, and vi is the amount of money in each building in that segment.

The sum of m overall test cases does not exceed 2 × 106.

Output

For each test case, print a single line containing the maximum amount of money the thief can collect by robbing at most k consecutive buildings.

Example
Input
1
2 5
1 5 1
7 11 1
Output
5

B. Friends and Cookies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abood's birthday has come, and his n friends are aligned in a single line from 1 to n, waiting for their cookies, Abood has x cookies to give to his friends.

Here is an example to understand how Abood gives away the cookies. Suppose Abood has 4 friends and x cookies, then Abood will do the following:

  1. Give a cookie to the 1st friend.
  2. Give a cookie to the 2nd friend.
  3. Give a cookie to the 3rd friend.
  4. Give a cookie to the 4th friend.
  5. Give a cookie to the 3rd friend.
  6. Give a cookie to the 2nd friend.
  7. Give a cookie to the 1st friend.
  8. Give a cookie to the 2nd friend.
  9. And so on until all the x cookies are given away.

Your task is to find how many cookies each friend will get. Can you?

Input

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

Each test case consists of a single line containing two integers x and n (1 ≤ x ≤ 1018, 1 ≤ n ≤ 1000), in which x is the number of cookies Abood has, and n is the number of his friends.

Output

For each test case, print a single line containing n space-separated integers a1, ..., an, in which ai represents how many cookies the ith friend got.

Example
Input
1
5 3
Output
2 2 1

C. Flip the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer n. Your task is to build a number m by flipping the minimum number of bits in the binary representation of n such that m is less than n (m < n) and it is as maximal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.

Each test case consists of a single line containing one integer n (1 ≤ n ≤ 109), as described in the statement above.

Output

For each test case, print a single line containing the minimum number of bits you need to flip in the binary representation of n to build the number m.

Example
Input
2
5
10
Output
1
2

D. Magic Sticks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a n × m grid, your goal is to find a group of lines such that the following conditions are met:

  1. No two lines are touching.
  2. Each cell in the grid has one of its sides covered by at least one line in the group.

A line is a border of a cell in the grid with length 1. Each cell has 4 lines covering every side of it. Every pair of neighboring cells shares a line. Two lines are touching if they meet at their ends.

The size of a group of lines is the number of lines it contains. Your task is to find the minimum size of a group of lines that meet all the conditions above. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 128) specifying the number of test cases.

Each test case consists of a single line containing two integers n and m (1 ≤ n ≤ 109, 1 ≤ m ≤ 1024), giving a grid of size n × m.

Output

For each test case, print a single line containing the minimum size of a group of lines that meet all the conditions in the statement above.

Example
Input
1
4 4
Output
10

E. N-Dimensional Grid
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an n-dimensional grid in which the dimensions of the grid are a1 × a2 × ... × an. Each cell in the grid is represented as an n-tuple (x1, x2, ..., xn) (1 ≤ xi ≤ ai).

Two cells are considered to be adjacent if the Manhattan Distance between them is equal to 1. The Manhattan Distance between two cells X(x1, x2, ..., xn) and Y(y1, y2, ..., yn) is equal to: |x1 - y1| + |x2 - y2| + ... + |xn - yn|.

Your task is to count how many pairs of cells are adjacents. Can you? Two pairs of cells are considered the same if they include the same cells, i.e the pair (c1, c2) is the same as (c2, c1).

Input

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

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the number of dimensions of the grid. Then a line follows containing n integers a1, ..., an (1 ≤ ai ≤ 105), in which ai is the size of the ith dimension.

The sum of n overall test cases does not exceed 6 × 106.

Output

For each test case, print a single line containing the number of pairs of adjacent cells modulo 109 + 7.

Example
Input
1
3
1 2 3
Output
7
Note

The absolute value |x| of a real number x is the non-negative value of x without regard to its sign. Namely, |x| = x for a positive x, |x| =  - x for a negative x (in which case  - x is positive), and |0| = 0. For example, the absolute value of 3 is 3, and the absolute value of  - 3 is also 3. The absolute value of a number may be thought of as its distance from zero.

F. Minimum Sum of Array
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a consisting of n integers a1, ..., an. In one operation, you can choose 2 elements ai and aj in which ai is divisible by aj and transform ai to aj.

A number x is said to be divisible by a number y if x can be divided by y and the result is an exact whole number. For example, 15 is divisible by 3, because 15÷ 3 = 5 exactly, but 9 is not divisible by 2 because 9÷ 2 is 4 with 1 left over.

Your task is to find the minimum sum of the array a that can be obtained by making as many transform operations as you want. Can you?

Input

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

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of array a. Then a line follows containing n integers a1, ..., an (1 ≤ ai ≤ 106), giving array a.

The sum of n overall test cases does not exceed 3 × 106.

Output

For each test case, print a single line containing the minimum sum of the array a that can be obtained after making as many transform operations as you want.

Example
Input
1
5
2 2 3 6 6
Output
11

G. Power of String
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yosef Darwish is participating this year in the ACM International Collegiate Programming Contest (ACM ICPC). Unfortunately, Yosef had an argument with his team because he wanted to name the team "yosefdarwish" but his team refused because the power of this name was too low.

Let the power of a string S of length n be defined as P(S), in which:

in which Ni is the number of indices j (i < j ≤ n) such that Si ≡ Sj, and Vi is the ASCII value in decimal of character Si.

You are given a string s of length n consisting of lowercase English letters, and an integer k. You are allowed to make at most k change operations, such that at each operation you can change any letter si to any other lowercase English letter. Your task is to use the change operations to maximize the power of string s. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 10) specifying the number of test cases.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5000), in which n is the length of string s, and k is the number of allowed change operations. Then a line follows containing string s of length n consisting of lowercase English letters.

Output

For each test case, print a single line containing the maximum power of string s after making at most k change operations.

Example
Input
2
12 1
yosefdarwish
5 1
aaaaz
Output
345
970
Note

American Standard Code for Information Interchange (ASCII) is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Lowercase 'a' has ASCII value 97 in decimal, lowercase 'b' has ASCII value 98 in decimal, and so on. Lowercase 'z' has ASCII value 122 in decimal.

H. Making Friends
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ali is trying to make his friends happier by matching them into pairs together. In the beginning, Ali has 2 × n friends standing in a row and numbered from 1 to 2 × n. Each friend i will be matched with the friend numbered (2 × n - i + 1).

Each friend i has a happiness level equal to hi. The happiness level of a matched pair of friends i and (2 × n - i + 1) is equal to hi + h2 × n - i + 1.

Your task is to find the maximum happiness level of a pair among all matched pairs. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 50) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000), giving that Ali has 2 × n friends. Then a line follows containing 2 × n integers h1, ..., h2 × n (1 ≤ hi ≤ 1000), in which hi represents the happiness level of the ith friend.

Output

For each test case, print a single line containing the maximum happiness level of a pair among all matched pairs.

Example
Input
1
3
2 4 5 6 7 8
Output
11

I. Split the Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer x. Your task is to split the number x into exactly n strictly positive integers such that the difference between the largest and smallest integer among them is as minimal as possible. Can you?

Input

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

Each test case consists of a single line containing two integers x and n (1 ≤ x ≤ 109, 1 ≤ n ≤ 1000), as described in the statement above.

Output

For each test case, print a single line containing n space-separated integers sorted in a non-decreasing order. If there is no answer, print  - 1.

Example
Input
1
5 3
Output
1 2 2
Note

The strictly positive integers are the set defined as: . That is, all the integers that are strictly greater than zero: .

J. T-Shirts Dilemma
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The-Legend needs to buy new t-shirts, so, he goes shopping and finds a special offer given by the ACM shop (Aloha Customer Market). ACM shop has b - a + 1 t-shirts sorted by there costs, with costs a, a + 1, a + 2, ..., b - 1, b, respectively. The offer is that The-Legend can choose some consecutive t-shirts and buy them such that the cost of them is the bitwise OR of their costs. For example, if The-Legend buys three t-shirts with costs: 2, 3, and 4, then their total cost will be 2 OR 3 OR 4 = 7.

The-Legend is only carrying v dollars and he is wondering what is the maximum number of t-shirts he can buy, knowing that he can only choose one consecutive range of t-shirts between a and b inclusive. Can you help The-Legend to find the answer?

Input

The first line contains an integer T (1 ≤ T ≤ 106), specifying the number of test cases.

Each test case consists of a single line containing three integers a b and v (1 ≤ a ≤ b ≤ 1018, 1 ≤ v ≤ 1018), as desribed in the statement above.

Output

For each test case, print a single line containing the maximum number of t-shirts The-Legend can buy.

Example
Input
1
2 7 7
Output
6
Note

A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1. For example, the result of 10 OR 17 = 01010 OR 10001 = 11011 = 27.

K. League of Demacia
time limit per test
4 s
memory limit per test
256 megabytes
input
standard input
output
standard output

The war is about to start between Demacia and Noxus. Noxus's army has n soldiers. Noxus's soldiers are stronger than Demacia's soldiers, so Demacia's soldiers can win only if their number is larger than the number of Noxus's soldiers.

Lux is a magical girl from Demacia, she decided to help her city's army! Lux can shoot an infinite laser in a straight line with a width equal to z and can kill all the enemies in the path! Lux can send the laser only one time, so she needs to kill at least m soldiers to help Demacia's soldiers win the fight.

Lux stands at the point (0, 0) and she knows the positions of every soldier from Noxus, she wants to know if she can help Demacia's army to win the war. Can you help her?

Input

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

The first line of each test case contains two integers n and m, and a floating point number z (1 ≤ n, m ≤ 1000, 0 < z ≤ 30000), in which n is the number of soldiers in Noxus's army, m is the minimum number of soldiers Lux must kill, and z is the width of Lux's laser.

Then n lines follow describe each Noxus's Soldier, in which the ith line contains 2 integers xi, yi ( - 104 ≤ xi, yi ≤ 104), representing the coordinates of the ith soldier.

It is guaranteed that no two soldiers share the same pair of coordinates, neither with Lux's position.

Output

For each test case, print a single line containing "Yes" (without quotes) if Demacia's army can win. Otherwise, print "No" (without quotes).

Example
Input
1
5 3 2
1 1
1 2
2 -2
3 3
5 2
Output
Yes

L. Lazy Teacher
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a grid of desks consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each desk is identified by a pair (x, y), which means that the desk is located in the row x and column y. There is a student sitting at each desk.

Today is the exam date! The teacher has prepared k forms of the exam with infinite copies of each form. The lazy teacher will give each student one form randomly with an equal probability.

Two students are considered to be adjacent if their desks share a common edge either vertically or horizontally. Your task is to count in how many ways the teacher can give the forms to the students so that no two adjacent students have the same form. Can you?

Input

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

Each test case consists of a single line containing three integers n, m, and k (1 ≤ n ≤ 5, 1 ≤ m ≤ 104, 1 ≤ k ≤ 105), in which n and m are the number of rows and columns in the grid of desks, respectively, and k is the number of forms the teacher has prepared.

The sum of n × m overall test cases does not exceed 5 × 105.

Output

For each test case, print a single line containing the number of ways the teacher can give the forms to the students so that no two adjacent students have the same form module 109 + 7.

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

M. Greedy Pirate
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given n islands numbered from 1 to n and connected using n - 1 magical bridges. A greedy pirate wants to collect as many coins as possible by traveling through the bridges. Each bridge is a two-way bridge, but the pirate can only use the bridge at most twice. If a bridge connects islands u and v, then going from u to v gives c1 coins, and going from v to u gives c2.

Help the pirate to collect as many coins as he can knowing that he will start from some island x and finish at some island y.

Input

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

The first line of each test case contains one integer n (2 ≤ n ≤ 105), in which n is the number of islands. The n - 1 lines follow, giving the bridges. Each line contains four integers u, v, c1, and c2 (1 ≤ u, v ≤ n, 1 ≤ c1, c2 ≤ 104), as describing in the statement above.

The next line contains an integer q (1 ≤ q ≤ 105), in which q is the number of queries. Then q lines follow, giving queries. Each query consists of two integers x and y (1 ≤ x, y ≤ n), in which x and y are the starting and finish islands, respectively.

The sum of n and q overall test cases does not exceed 25 × 105 for each.

Output

For each query, print a single line containing the maximum amount of money the greedy pirate can collect by traveling through the bridges starting from island x and finishing at island y.

Example
Input
1
5
1 2 5 10
3 5 25 3
4 2 15 12
3 2 6 7
2
1 5
4 3
Output
64
65