2018 JUST Programming Contest 1.0
A. Will he Die?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Unfortunately, Conan is in a real danger! Conan discovered who is the killer after searching for the evidence in a dangerous cave. Now, he is standing in front of a bomb that about to explode. The bomb will explode after m seconds.

The cave is represented as an infinite horizontal line that runs from  - ∞ to ∞, as shown in the picture below:

Initially, Conan stands at position 0. At each second, he will move either one step to the left (i.e. from position y to y - 1) or one step to the right (i.e. from position y to y + 1) with an equal probability (i.e. 0.50). Conan will be safe if he reached position n.

Conan is wondering what is the probability that he will be at position n after m seconds. Can you help Conan in calculating his chances of surviving?

Input

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

Then T lines follow, each line contains two integers n and m ( - 2 × 105 ≤ n ≤ 2 × 105) (0 ≤ m ≤ 2 × 105), as described in the problem statement.

Output

For each test case, print a single line containing z, in which z is the sought probability computed module 109 + 7.

The answer z is defined precisely as follows. Represent the probability that Conan will be at position n after m seconds as an irreducible fraction p / q. The number z then must satisfy the modular equation , and be between 0 and 109 + 6, inclusive. It can be shown that under the constraints of this problem such a number z always exists and is uniquely determined.

Example
Input
3
0 0
1 1
-3 3
Output
1
500000004
125000001
Note

In the second test case, Conan wants to know what is the probability that he will be at postilion 1 after 1 second of moving. The probability is 1 / 2, and the answer is 500000004, since .

B. Ran and the Lock Code
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two days ago, a woman called Fumiyo Edogawa knocked the door of Kogoro Mouri home and claimed that she is Conan's mom. Fumiyo introduced herself as Conan's mother and used fake documents to prove this. Conan, Kogoro Mouri, and his daughter Ran believed her. So, Conan went with her.

Ran was worried about Conan. After investigations, Ran discovered that Conan has been kidnapped! Ran called the police and they helped her to find Conan's location. When they arrived at that location, Ran shocked because she discovered that Conan is detained inside a locked coffin.

After examining the coffin, Ran discovered that it is locked using a modern electronic lock. Ran can open the lock only by solving T mysteries. In each mystery, Ran is giving two numbers n and a, and she needs to find the maximum number of distinct elements that can exist in a list of n positive elements with an average equals to a.

Ran knows that time is running out of her, and she must expedite in solving the mysteries to get Conan out of the coffin before his breath stopped. Ran asked you to help her in solving the mysteries. Will you leave Conan to die smothered or will you help Ran solving the mysteries?

Input

The first line contains an integer T (1 ≤ T ≤ 105), in which T is the number of mysteries.

Then T lines follow, giving the mysteries. Each line contains two integers n and a (1 ≤ n, a ≤ 109), in which n is the number of elements in the list, and a is the required average of that list.

Output

For each test case, print a single line containing the maximum number of distinct elements that can exist in a list of n positive elements with an average equals to a.

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

The average of a list of n elements x1, x2, ..., xn is defined as the ratio between the sum of the n elements and n. More formally:

In the first test case, Ran is asked to find the maximum number of distinct elements that can exist in a list of 2 positive elements with an average equals to 4. Ran can choose a list such as [3, 5]. So, the number of distinct elements is 2.

C. Professor Agasa Lab
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Agasa always tries to help Conan solve the crimes and he has invented all Conan's special gadgets.

Currently, Professor Agasa is solving a complex murder case, so he is performing a series of tests in his laboratory. After two months of searching, Professor Agasa figured that all the evidence he needs to solve the case can be found in a safe inside one of the suspect's house. Professor Agasa is so close to open the safe, he only needs to solve one more puzzle and all the secrets inside the safe will be for him. The final puzzle is as follows:

If you have the following equation

If you know the values of y, a, b, and m, then you can calculate the value of x as follows:
Where a - 1 is the multiplicative inverse of a number a, such that a - 1 exists only if gcd(a, m) ≡ 1.

You are given m, count how many different pairs (a, b) (1 ≤ a, b < m) exist, such that you can use them to calculate y and x under the given modules m.

Professor Agasa is so tired of solving puzzles all the day in order to open the safe. Can you help him by solving the last puzzle?

Input

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

Then T lines follow, each line contains an integer m (1 ≤ m ≤ 106), in which m is the described modulus in the problem statement.

Output

For each test case, print a single line containing how many different pairs (a, b) (1 ≤ a, b < m) exist, such that Professor Agasa can use them to calculate y and x under the given modules m.

Example
Input
2
6
10
Output
10
36
Note

In the first test case, there are 10 different pairs that satisfy the problem conditions, which are: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (5, 1), (5, 2), (5, 3), (5, 4), and (5, 5)

D. Help Conan
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Conan is tired of his current job, so he decided to get a new job and applied for an engineering position in one of the largest technology companies in the Silicon Valley. Conan is currently in the last interview. Unfortunately, this interview is very tough, so that Conan is currently struggling with a very hard question!

Conan is given an undirected connected graph of n nodes and m edges. This graph has a special property where it contains k important nodes. Conan task is to find a sub-graph in the given graph such that it contains all the important nodes (but may include additional unimportant nodes) such that its length is as minimal as possible. The length of a sub-graph is defined to be the sum of the lengths of all its edges.

Conan has no idea how he can solve this question, but he is determined not to return to his previous job. Therefore, Conan used his special gadgets to leak the question to you so that you can help him. Conan will give you his first salary if you helped him. Can you?

Input

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

The first line of each test case contains three integers n, m, and k (2 ≤ n ≤ 15) () (1 ≤ k ≤ n), where n is the number of nodes, m is the number of edges, and k is the number of important nodes.

Then m lines follow, each line contains three integers u, v, and c (1 ≤ u, v ≤ n) (0 ≤ c ≤ 106), giving an edge of length c between nodes u and v. It is guaranteed that there are no self-loops and multiple edges.

Then a line follows containing k distinct integers x1, x2, ..., xk (1 ≤ xi ≤ n), giving the indices of the important nodes. Nodes are numbed from 1 to n.

Output

For each test case, print a single line containing the minimum length of a sub-graph in the given graph such that it contains all the important nodes (but may include additional unimportant nodes)

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

E. Rescue Haibara
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Haibara is one of Conan's best friends. Conan sent her as a spy in order to discover the killer in one of his investigations. Haibara was on her first mission as a spy. Unfortunately, her mission did not go as planned, and she has been compromised. Haibara got panicked and she forgot what she learned from Conan. So, it is your time to help her to avoid arrest. Your task is to help Haibara find the best safe house for her based on her current situation. There are n safe houses around Haibara's location. The ith house is di kilometers away from Haibara, and it contains mi coins.

According to the manual, the best safe house must be at distance no more than x and must contain at least y coins. If there is more than one safe house satisfying these conditions, you must choose the nearest one. If there is more than one safe house at the same distance, you must choose the one that contains the biggest amount of coins. Finally, if there is more than one safe house satisfying all the previous conditions, you must choose the one with minimum index.

Do not forget that Haibara is in a real danger, so you must find the best safe house for her as soon as possible. Conan will be very happy if you rescue Haibara. Can you do this?

Input

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

The first line of each test case contains three integers n, x, and y (1 ≤ n ≤ 500) (1 ≤ x, y ≤ 1000), in which n is the number of safe houses, and x and y are the values from the manual as described in the statement.

Then n lines follow, each line contains two integers di and mi (1 ≤ di, mi ≤ 1000), in which di is the distance to the ith safe house, and mi is the amount of coins it contains. Safe houses are numbered from 1 to n in the order given in the input.

Output

For each test case, print a single line containing  - 1 if there is no suitable safe house for Haibara. Otherwise, print the index of the safe house you have chosen for her.

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

In the second test case, you need to find a safe house at distance no more than 4 and must contain at least 6 coins. You can choose the 1st or 2nd safe houses, but according to the manual, the 2nd safe house is the most suitable.

F. Median and Queries
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a grid 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 cell is identified by a pair (x, y), which means that the cell is located in the row x and column y. All cells in the grid contain positive integers.

Also, q queries are given, such that each query consists of four integers a, b, c and d. For each query, the task is to find the median of a sub-matrix (a, b) (c, d) in the given grid.

A sub-matrix (a, b) (c, d) is defined as all cells whose satisfying the following conditions: (a ≤ x ≤ c) and (b ≤ y ≤ d). The following picture describes a grid of 4 rows and 5 columns. The shaded part shows the sub-matrix (2, 2) (3, 4).

Sarah needs your help to find the answer to each query. Can you help her?

Input

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

The first line of each test case contains three integers n, m, and q (1 ≤ n, m ≤ 100) (1 ≤ q ≤ 105), in which n is the number of rows in the grid, m is the number of columns in the grid, and q is the number of queries.

Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 500 (inclusive).

Then q lines follow, each line contains four integers a, b, c, and d (1 ≤ a ≤ c ≤ n) (1 ≤ b ≤ d ≤ m), giving the queries.

The sum of n × m overall test cases does not exceed 3 × 105, and the sum of q overall test cases does not exceed 106.

Output

For each query, print a single line containing the median value.

Example
Input
1
4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 2
1 2 3 3
1 3 4 3
Output
2
6
7
Note

The median of a set of numbers is the middle element in the sorted list of the given set. If the set has two middle elements, then we choose the first one. For example, the median of {2, 1, 3} is 2 and the median of {4, 2, 3, 1} is 2.

G. Preparing for Exams
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ran Mouri and Sonoko Suzuki are preparing for the final exams. They decided to study mathematics as it is the hardest subject for them. While they are solving mathematical problems, they faced troubles with some questions, including the following question:

You are given a drawing for a sensor and some measurements about it. You have to find the rest of measurements. Sensor's design is as follow:

The data you have is the length of , the length of , the area of oda, and the area of obc. Your task is to calculate x and y, where x is the length of and y is the length of .

Can you help Ran and Sonoko Suzuki by solving this question?

Input

The first line contains an integer T (1 ≤ T ≤ 2 × 105), in which T is the number of test cases.

Then T lines follow, each line contains four integers k, l, m, and n (1 ≤ k, l, m, n ≤ 1012), in which k is the length of , l is the length of , m is the area of oda, and n is the area of obc.

Output

For each test case, print a single line containing two numbers x and y, where x is the length of and y is the length of . Your output will be considered correct if the absolute or relative error of every number in your output does not exceed 10 - 6.

Example
Input
1
18 16 72 288
Output
20 14

H. Genta Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kojima Genta is one of the best friends of Conan, and the fattest one!

Everyone believes that Genta is just thinking about food. So, he wants to prove the opposite. So, his friends challenged him in a game. Genta's friends will give him a string s of length n, and m update operations. At each update operation, an integer p (1 ≤ p ≤ n) and a lowercase English letter c will be given to Genta, and he is asked to change the pth letter in the string s to the letter c.

Conan explained to Genta that an update operation is said to be beautiful if the string s was a palindrome string after the update operation has been executed.

Genta task is to count the number of beautiful update operations. Genta wants to win in this game no matter what this will cost because his friends promised him that the food will be at their expense throughout the week if he solved the task. Can you help Genta by solving his task?

Input

The first line contains an integer T (1 ≤ T ≤ 50), in which T is the number of test cases.

The first line of each test cases contains two integers n and m (1 ≤ n, m ≤ 105), in which n is the length of the string s and m is the number of update operations. The second line of each test cases contains a string s of length n consisting of lowercase English letters only. Then m lines follow, each line contains an integer p and a lowercase English letter c (1 ≤ p ≤ n), giving the update operations.

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

Output

For each test case, print a single line containing the number of beautiful update operations.

Example
Input
1
10 7
abcdefdcba
5 x
6 x
4 d
2 d
3 y
8 y
9 d
Output
3
Note

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".

In the first test case, the string s will be updated as follow:

abcdefdcba abcdxfdcba abcdxxdcba abcdxxdcba adcdxxdcba adydxxdcba adydxxdyba adydxxdyda.

There are 3 beautiful update operations, which are the 2rd, 3th, and 7th operations.

I. UEFA Champions League
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Conan is always busy investigating murders, and he rarely finds an opportunity to enjoy his time. His friend Ran told him that this lifestyle harms his health, and this may lead to premature death. So, Conan decided taking a break to enjoy his time.

At the night, Ran told Conan that he can enjoy by watching the UEFA Champions League matches. Conan does not know anything about this competition and its rules, so, Ran starts explaining to him what are the rules of the knockout stage that will start today.

In the knockout stage, two teams play two matches against each other, such that the first match will hold on first team's stadium and the second match will hold on second team's stadium. The winning team who will qualify for the next stage is the team who score more goals than its opponent. If the two teams score the same number of goals over the two matches, the team which scores more goals in the opponent stadium qualifies for the next stage. If this procedure does not produce a result (i.e. if both teams score the same number of goals at each other stadiums), two 15-minute periods of extra time are played at the end of the second match. (See notes for more clarification)

Ran is not sure if Conan understood her explanation or not, so she decides to give him a test. Ran will give Conan the results of two matches and he must determine the winner. Can you help Conan in his test so he can continue watching the match?

Input

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

Each test case consists of a line containing four integers a, b, c, and d (0 ≤ a, b, c, d ≤ 10), in which a is the number of goals the first team scored in the first match, b is the number of goals the second team scored in the first match, c is the number of goals the first team scored in the second match, and d is the number of goals the second team scored in the second match.

Output

For each test case, print a single line containing 1 if the first team won, 2 if the second team won, or  - 1 if the winner cannot be determined and the two teams will play an extra time.

Example
Input
3
1 2 4 1
4 0 1 6
2 0 0 2
Output
1
2
-1
Note

In the first test case, the aggregate score of the two matches is (First Team 5-3 Second Team). So, the first team won since it scored more goals.

In the second test case, the aggregate score of the two matches is (First Team 5-6 Second Team). So, the second team won since it scored more goals.

In the third test case, the aggregate score of the two matches is (First Team 2-2 Second Team). The two teams will play the extra time since the winner cannot be determined.

J. Gin Passwords
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Gin is a high-ranking member of the Black Organization. During the last period, Gin made many thefts and collected a huge wealth. Now, Gin wants to hide his wealth in a secret safe, and he must choose a very strong password for it.

Every time Gin wants to pick a new password he chooses two numbers l and r, then the new password will be the largest number x (l ≤ x ≤ r) that its decimal representation can be divided into two non-zero halves (of the same length) and the two halves are relatively prime. Two numbers are relatively prime if the only positive integer (factor) that divides both of them is 1.

In case a number x have odd number of digits (2r + 1), the first half will have the first r + 1 digits in the decimal representation of x (from the left), and the second half will contain the remaining r digits in the decimal representation of x.

Can you help Gin in choosing his new passwords?

Input

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

Each test case contains two numbers l and r (1 ≤ l ≤ r ≤ 1018), as described in the statement.

Output

For each test case, print the largest number x (l ≤ x ≤ r) that its decimal representation can be divided into two non-zero halves and the two halves are relatively prime. If a number x does not exist in the given range, print  - 1.

Example
Input
2
21 25
110 186
Output
25
185
Note

In the first test case, there are 3 numbers in the range [21, 25] that can be chosen as a password. These numbers are 21, 23, and 25. Gin will choose the largest one of them as a password, which is 25.

K. Conan and Scoreboard
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Wow, what a contest! You helped Conan and his friends many times during this contest, and now it is time to give back.

Conan knows you have an exam directly after the contest. So, he decided to help the judges in calculating the results when the contest finish so they can announce it as soon as possible. Conan task is to find the name of students who will get the following awards:

  • First to Solve Problem x Award. This award is given to a student for being the first to solve a problem x in the contest.
  • Extreme Programmers Award. This award is given to the student who submitted the first correct solution in the contest.
  • Steadfast Gurus Award. This award is given to the student who submitted the last correct solution in the contest.
  • Solid Programmers Award. This award is given to the student who solved the maximum number of problems from the first attempt.
  • Relentless Programmers Award. This award is given to the student who made the largest number of incorrect submissions on a problem before solving it.

Conan shocked when he sees the submission's list due to its large size. So, Conan will need help to calculate the results. Of course, who can help Conan rather than you? Conan will give you the submission's list and you need to calculate the results for him. Remember you need to calculate the results as fast as possible because you do not want to miss your exam. Can you?

Input

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

The first line of each test case contains three integers n, m, and k (6 ≤ n, m ≤ 30) (1 ≤ k ≤ 10000), in which n is the number of problems in the contest, m is the number of students who participated in the contest, and k is the number of submissions. Problems are numbered from 1 to n, and students are numbered from 1 to m.

Then k lines follow, giving the details of the submissions. Each submission consists of three integers x, y and z, and a string t (1 ≤ x ≤ n) (1 ≤ y ≤ m) (), in which x is the problem's ID, y is the student's ID, z is 1 if the submission was correct and 0 otherwise. The time t is giving in the format mmm:ss, which means the submission was made mmm minutes and ss seconds after the start of the contest. Teams can start making submissions from 000:00, and no submission will be made after 299:59. No team will make a submission on a problem after solving it.

It is guaranteed that no two submissions were made at the same time. Also, it is guaranteed that at least one team solved at least one problem during the contest.

The sum of k overall test cases does not exceed 6 × 105.

Output

For each test case, print two lines. The first line must contain n integers in which the ith integers is the number of the first team to solve problem i or  - 1 if this problem has not been solved during the contest. The second line must contain four integers a, b, c, and d, in which a is the ID of the team who won the Extreme Programmers Award, b is the ID of the team who won the Steadfast Gurus Award, c is the ID of the team who won the Solid Programmers Award, and d is the ID of the team who won the Relentless Programmers Award.

If there is more than one team satisfying the condition of an award, this award will go to the team with the lowest ID.

Example
Input
1
6 6 13
1 1 1 005:23
1 4 1 007:49
1 5 1 008:21
1 2 1 010:32
3 1 0 012:18
3 1 1 013:20
1 6 1 016:20
1 3 1 018:46
2 3 0 029:14
2 3 1 037:14
5 1 0 042:37
2 2 1 044:35
5 1 1 055:29
Output
1 3 1 -1 1 -1
1 1 2 1