International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2018)
A. Zeros and Ones
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
zeros.in
output
standard output

Given four integers x, y, M and K. You need to count the number of integers d that satisfy the following rules:

  1. The binary representation of d should consist of x ones and y zeroes without leading zeros.
  2. d modulo M is greater than or equal to K.
Input

The first line of the input is the number of test cases T. Each test case consists of four integers x, y, M and K, where 1 ≤ M ≤ 109, 1 ≤ x + y ≤ 42, x ≥ 1, y ≥ 0 and 0 ≤ K < M.

Output

For each test case output a single line with the number of integers d that satisfy the rules.

Example
Input
1
2 2 8 2
Output
2

B. The first task
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
task.in
output
standard output

After being accepted as an intern in one of the biggest companies, Yasser's first task was to come up with a strategy to encrypt a huge amount of data into some permutation of integers. Here is the definition of a permutation that can be accepted by Yasser's supervisor:

  1. The maximum number in the permutation should be greater than or equal to 1.
  2. If the maximum number is $$$M$$$, it should contain all numbers from 1 to $$$M$$$.
  3. Each number should appear exactly once.
  4. The numbers can appear in any order.
  5. The permutation can't be empty.

His supervisor gave him a week to finish the task. After days of hard work he finally managed to finish the task at the night of the deadline, he was so happy and looking forward to seeing how much his supervisor will be impressed by his hard work.

Since Yasser was very tired, he fell asleep without turning off his computer, and while he was asleep dreaming about all the nice words that people are going to say about him, his little brother was messing up his result. In the morning, he discovered this disaster and found out that his brother has changed the resulting sequence and that he may have added some arbitrary integers to it or deleted some integers from it and the sequence may not be a valid permutation anymore.

Yasser now can't remember how the original permutation was like and what its length was. There is no time for him to repeat the work, but instead of punishing his brother for what he did, he decided to apply the minimum number of operations on the current sequence to make it a valid permutation again.

Each operation is either inserting or removing a number. This way he may be able to survive the meeting without being a joke and after the meeting he will have time to reconstruct the original sequence.

Input

The first line of the input contains the number of test cases $$$T$$$. Each test case starts with a line that contains a single integer $$$N$$$ the length of the current sequence, where $$$1 \leq N \leq 10^5$$$.

The following line contains $$$N$$$ space-separated integers representing the sequence. Each integer is between 1 and $$$10^9$$$ inclusive.

Output

For each test case output a single line contains the minimum number of operations.

Example
Input
1
4
1 1 3 4
Output
2
Note

Please note that Yasser can make a permutation of any length even of length 1. The only thing that matters is to reach a valid permutation accepted by his supervisor by using the minimum number of operations.

C. Array transformation
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
transform.in
output
standard output

Given two arrays A and B. You need to transform the array A to B by deleting zero or more elements from A. However, you are only allowed to delete an element if it satisfies at least one of the two following conditions:

  • There doesn't exist a non-deleted element to its left with the same value.
  • There doesn't exist a non-deleted element to its right with the same value.
After removing an element which was intitally at position i, a value of Ci will be added to your score. If your score is initially zero, what is the minimum score that you can have after transforming A to B?
Input

The first line of the input is the number of test cases T.

Each test case starts with a line containing two space-seperated integers N and M the length of the array A and the length of the array B respectively, where 1 ≤ M ≤ N ≤ 2000. The following three lines represent arrays A, B and C respectively, where |Ai|, |Bi|, |Ci| ≤ 109.

It's guaranteed that the length of A equals the length of C.

Output

For each test case output a single line containing the minimum score or 'No' without the quotes if you can't transform A to B.

Example
Input
3
6 3
1 2 2 1 2 1
1 2 1
1 100 2 1 -1 50
3 1
1 1 1
1
-100 0 1
2 1
1 1
-2
-100 1
Output
51
-100
No
Note

Here is the explanation of the first test case: You can transform A to B as follows:

  1. Delete '2' at the 5th position and add -1 to your score.
  2. Delete '1' at the 6th position and add 50 to your score.
  3. Delete '2' at the 3rd position and add 2 to you score (we can do this now because we removed all the elements with value 2 to its right).

Note : You couldn't have started by deleting the '2' at the third position as the first operation because it doesn't initially satisfy any of the mentioned conditions.

D. The Millennium Prize Problems
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
lcm.in
output
standard output

Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problems results in a million dollar prize being awarded by the institute to the discoverer(s).

Soliman, one of the ECPC judges came up with a new mathematics problem and claimed that it should be the eighth Millennium Prize Problem as he is pretty sure no one could solve it. Here's the problem:

Given an array $$$A$$$ of length $$$N$$$ (the array can have duplicate values). What is the sum of all least common multiple (LCM) values for every pair of the array? More formally you need to calculate the following: $$$$$$ \sum_{i=1}^N \sum_{j=1}^N \text{LCM}(A_i, A_j)$$$$$$

Tefa, one of the ECPC judges suggested that we can add it in the problem set to see if someone can come up with a solution, so can you do it?

Input

The first line of the input contains a single integer $$$T$$$ the number of test cases, each test case consists of one line containing $$$N + 1$$$ space-separated integers, the first integer is the number $$$N$$$ the size of the array and the remaining integers are the elements of the array $$$A$$$, where $$$1 \leq N \leq 10^5$$$ and $$$1 \leq A_i \leq 10^5$$$.

Output

For each test case output the answer to the problem modulo $$$10^9+7$$$.

Example
Input
2
4 2 6 12 15
5 2 3 7 11 12
Output
335
861

E. Count permutations
time limit per test
15 s
memory limit per test
1024 megabytes
input
permutations.in
output
standard output

We heard you like problems with short statements and no stories, this one is for you!

Count the number of permutations of length N where the maximum length of an increasing subarray is exactly K.

Input

The first line of input is the number of test cases T.

Each test case consists of a single line containing two integers N and K, where 1 ≤ K ≤ N ≤ 200.

Output

For each test case output a single line containing the answer to the problem modulo 109 + 7.

Example
Input
4
9 4
9 3
7 1
7 7
Output
60875
189524
1
1
Note
  • A permutation of length N is a sequence of all integers between 1 and N, where each integer appears exactly once and the numbers can appear in any order.
  • A subarray of array A is an array equals to [Ai, Ai + 1, Ai + 2, ..Aj] where 1 ≤ i ≤ j ≤ |A|.

  • For a permutation to be counted, it should have at least one increasing subarray of length K and there is no any increasing subarray with length greater than K.

F. MO Salah running down the wing
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
mosalah.in
output
standard output

The ECPC judges were discussing Salah's performance this season. Some of them think that it is lower than his level in the last season, but others think that it is too early to judge him. They all agreed that if he ended this season with the same average number of goals as the last season, then there is no need to worry.

Given four integers, $$$N$$$, $$$M$$$, $$$X$$$ and $$$Y$$$ representing his average number of goals per match in the last season, the number of goals he scored so far in the current season, the number of matches that were already played and the number of remaining matches respectively.

What is the minimum number of goals he needs to score in the remaining matches to have at least the same average number of goals as the last season ?

Input

The first line of the input is the number of test cases $$$T$$$. Each test case consists of four integers $$$N$$$, $$$M$$$, $$$X$$$, and $$$Y$$$, where $$$0 \leq N, M, X, Y \leq 100$$$ and $$$X + Y \gt 0$$$.

Output

For each test case output a single line containing the minimum number of goals or $$$-1$$$ if Salah can't make it.

Example
Input
4
1 1 37 1
5 1 1 37
1 0 1 0
2 6 1 2
Output
37
189
-1
0

G. Robots race
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
robot.in
output
standard output

The Yousry brothers are participating in a robots competition. The competition arena can be represented as a weighted connected undirected graph with no self-loops or multiple edges containing $$$N$$$ nodes and $$$M$$$ edges. A robot's memory can be illustrated as a stack. For a robot to be ready for the competition it needs to execute $$$Q$$$ commands of three types very efficiently.

  1. Clear the robot's memory.
  2. Push node $$$u$$$ to the top of the robot's memory.
  3. Pop the node at the top from the robot's memory. If the memory is empty just ignore the command.

After each command of type 2 a robot should report whether the sequence of nodes in its memory is valid or not according to the following rules:

  1. If the sequence consists of a single node, then it is valid.
  2. If there is a node that appears more than once, then the sequence is not valid .
  3. If there is a consecutive pair of nodes in the sequence that don't have an edge between them in the graph representing the arena, then the sequence is not valid .
  4. If the set of edges between each two consecutive nodes in the sequence can't be a subset of the edges of some minimum spanning tree of the graph, then the sequence is not valid .
  5. If non of the above three cases happen, then the sequence is valid .

Since the speed of a robot in the race depends on how fast these commands are executed, the two brothers asked you to use your algorithmic and competitive programming skills to help them win this race.

Input

The first line of the input contains a single integer $$$T$$$ the number of test cases.

Each test case starts with a line containing three integers $$$N$$$, $$$M$$$, and $$$Q$$$, where $$$2 \leq N \leq 10^5$$$, $$$1 \leq M \leq 10^5$$$ and $$$1 \leq Q \leq 10^5$$$.

The next $$$M$$$ lines represent the edges in the graph where each line contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ to indicate an edge with weight $$$w$$$ between nodes $$$u$$$ and $$$v$$$, where $$$1 \leq u \leq N$$$, $$$1 \leq v \leq N$$$, $$$1 \leq w \leq 10^4$$$ and $$$u \neq v$$$.

The next $$$Q$$$ lines represent the commands. Each command starts with an integer $$$t$$$ the type of the command and if $$$t$$$ is 2, another integer $$$u$$$ will follow, where $$$1 \leq t \leq 3$$$ and $$$1 \leq u \leq N$$$.

Output

For each test case, for each command of type 2 print 'y' if the sequence of nodes is valid or 'n' otherwise.

Example
Input
1
4 5 9
1 2 1
2 3 2
1 4 2
2 4 1
3 4 2
2 1
2 2
2 2
3
2 3
2 4
1
2 1
2 4
Output
y
y
n
y
n
y
n
Note

Please note that the set of minimum spanning tree edges that determine the validity doesn't have to be the same for each command. You just need to check that if you added zero or more edges from the original graph to the set of edges between each two consecutive nodes in the sequence, you will obtain one of the minimum spanning trees of the graph.

H. Find the path
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
path.in
output
standard output

You are given a weighted connected undirected graph of N nodes and M edges (with no self-loops or multiple edges). Additionally, you have three integers u, L and K.

Your task is to find all paths of length L edges that start from node u, and for each path of them you need to sort the weights on its edges in an ascending order and report the weight in the Kth position, what is the maximum value among all the values you report?

Please note that an edge can appear in the same path multiple times, which means that paths don't have to be simple, read the 'Notes' section for more clarification.

Input

The first line of the input contains a single integer T the number of test cases. Each test case starts with a line containing five integers N, M, u, L and K, where 2 ≤ N ≤ 105, 1 ≤ M ≤ 105, 1 ≤ u ≤ N, 1 ≤ L ≤ 105 and 1 ≤ K ≤ L.

The next M lines represent the edges in the graph where each line contains three integers u, v and w to indicate an edge with weight w between nodes u and v, where 1 ≤ w ≤ 109, 1 ≤ u ≤ N, 1 ≤ v ≤ N and u ≠ v.

Output

For each test case output a single line with the maximum value.

Example
Input
2
5 5 2 7 2
2 1 71
2 3 88
2 4 50
1 5 95
4 3 104
2 1 2 100 70
2 1 7
Output
104
7
Note

In the paths you can visit the same edge or node more than one time.

I. A sky full of stars
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
points.in
output
standard output

Badry and the ECPC judges travelled to Wadi El-Hitan, a beautiful place in Egypt with clear view of the sky to enjoy looking at the stars, and have fun after working for many consecutive days on the contest.

The judges finally thought they could get a break, but given Mostafa's unconditional love for Mathematics, he couldn't spend the night without challenging them to count how many triplets of stars form a right angled triangle with an area in range [L, R].

To simplify the situation, he told them to consider the sky as a 2D plane where each star is a point.

Given N distinct stars, count the number of these triangles, and help the poor judges!

Input

The first line of the input is the number of test cases T.

Each test case starts with a line containing three integers N, L and R, where 1 ≤ N ≤ 1000, 1 ≤ L ≤ R ≤ 1018.

Each of the following N lines represent a point (star) and contains two integers xi and yi, where |xi|, |yi| ≤ 109.

Output

For each test case output a single integer in a separate line, the answer to the problem.

Example
Input
4
7 1 100
0 0
2 0
0 2
10 0
0 10
3 3
3 -3
7 5 15
0 0
2 0
0 2
10 0
0 10
3 3
3 -3
7 7 9
0 0
2 0
0 2
10 0
0 10
3 3
3 -3
7 10 15
0 0
2 0
0 2
10 0
0 10
3 3
3 -3
Output
5
3
1
2

J. The test cases
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
unique.in
output
standard output

You may think that generating test cases for problems is always an easy task, but sometimes creating tests for a problem is more interesting than the problem itself. The judges of the ECPC came up with a nice problem that needs a binary string with the following properties as its input.

  1. The string should be with an even length N.
  2. The decimal number represented by it should be divisible by N.
  3. All decimal numbers represented by its prefixes should give unique remainders after being divided by N.

The task of creating an input generator for this problem was assigned to Ayman, and after some work on the task, Ayman convinced the judges that his task is more interesting than the problem itself. That's why all of them decided to include this task in the problem set. So given a number N, can you print a binary string that satisfies the three properties?. If there are multiple answers print any. It can be proven that an answer always exists.

Input

The first line of the input is the number of test cases T. Each test case contains a single line with the integer N, where 2 ≤ N ≤ 105.

Output

For each test case output a single line with any valid binary string that satisfies the three mentioned properties.

Example
Input
2
4
10
Output
1100
1100010110
Note

In the first test case for N = 4, one of the possible answers is 1100, because the decimal number represented by 1100 is 12 which is divisible by 4. Also the prefixes of 1100 are 1, 11, 110 and 1100 and their decimal representations are 1, 3, 6, 12 respectively.

You can see that all of their decimal representations produce different remainders when divided by 4 which are 1, 3, 2 and 0 respectively.

K. Crazy queries
time limit per test
30 s
memory limit per test
1024 megabytes
input
string.in
output
standard output

Given two strings S and P, and Q queries, for each query you are given a range [L, R].

For each pair of integers i and j chosen with uniform probability among all pairs where 1 ≤ i ≤ L and R ≤ j ≤ |S|, create a new string S2 that is the result of concatenating S[1... i] and S[j... |S|]. You have to find the expected number of occurrences of P in S2.

Note that all occurrences of P must be counted even if they overlap. The queries are independent meaning that the string S is the same for all queries.

Input

The first line of the input contains a single integer T the number of test cases. Each test case starts with two lines. The first line contains string S and the second line contains P, where 2 ≤ |S| ≤ 105 and 1 ≤ |P| ≤ 100. Each string consists of lowercase English letters.

The third line contains an integer Q, where 1 ≤ Q ≤ 5·104. Each of the next Q lines represents a single query with two space-separated integers L and R, where 1 ≤ L < R ≤ |S|.

Output

For each test case output Q lines. where each line contains the answer of the corresponding query in the form p/q where p and q are the numerator and denominator of the expected value in its simplest form respectively.

Example
Input
4
abaabaxbba
aba
4
2 7
1 5
6 9
4 5
abbaabxabba
aba
4
2 7
1 5
6 9
4 5
abbababbxaabaxabababxxa
abba
5
10 20
11 12
5 21
12 20
15 18
aaaaaaaaaa
aa
4
1 2
2 5
2 9
5 8
Output
1/4
1/3
4/3
5/6
3/10
1/7
5/18
5/28
3/4
115/132
7/15
19/24
8/9
5/1
4/1
2/1
4/1

L. Reflection
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
reflection.in
output
standard output

You are given a line with equation x = y. you need to perform the following operation Q times.

  1. For the ith operation, you are given an integer x and you are requested to find and print the corresponding value of its y coordinate on the current graph (assume that it equals to yi ).
  2. After finding yi, you should reflect the right part of the current graph (with x coordinates greater than or equal to xi) on the horizontal line y = yi .

Note that each operation depends on all operations before it.

Input

The first line of the input is the number of test cases T, each test case starts with a line containing a single integer Q the number of operations, where 1 ≤ Q ≤ 105.

Each of the following Q lines represents a query with a single integer x, where 0 ≤ xi ≤ 105.

Output

For each test case output Q lines. Each of them contains the corresponding y value.

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

Here are some figures that illustrate the first 2 operations:

M. The business man
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
business.in
output
standard output

Badry is tired of programming, that is why he wanted to try his chances in business world. Badry opened a company that trades in antiques. The company owns $$$N$$$ different shops where the $$$i_{th}$$$ shop has its location $$$X_i$$$ on the $$$OX$$$ axis and its product has initial quality $$$Q_i$$$. Moreover, there are two more strange facts about these shops:

  • The first one is that the delivery cars of the $$$i_{th}$$$ shop can only deliver products to customers with locations in the range $$$[X_i, X_i + R_i]$$$.
  • The second fact is that the quality of a product increases by one for each unit distance, which means that if some shop with location $$$X$$$ and initial quality $$$Q$$$ delivered its product to a customer at location $$$Y$$$ the quality of the product will be considered as ($$$Q+Y-X$$$).

Currently, Badry has $$$M$$$ orders from $$$M$$$ different customers where the $$$i_{th}$$$ customer is located at position $$$Y_i$$$ and requesting his product to be with quality at least $$$D_i$$$.

Can you help Badry by determining the number of shops that can serve each customer ? You can assume that each shop has infinite number of products.

Input

The first line of input contains the number of test cases $$$T$$$. Each test case starts with a line containing two integers $$$N$$$ and $$$M$$$ the number of shops and the number of customers respectively, where $$$1\leq N, M \leq 10^5$$$.

Each of the next $$$N$$$ lines contains three integers $$$X_i$$$, $$$Q_i$$$ and $$$R_i$$$ representing the $$$i_{th}$$$ shop, where $$$1 \leq X_i, Q_i, R_i \leq 10^9$$$.

Each of the following $$$M$$$ lines contains two integers $$$Y_i$$$ and $$$D_i$$$ representing the $$$i_{th}$$$ customer, where $$$1 \leq Y_i, D_i \leq 10^9$$$. All the positions of the shops are given in a non-decreasing order. Also all positions of the customers are given in a non-decreasing order.

Output

For each test case output a single line containing $$$M$$$ space-separated integers, the number of possible serving shops for each customer.

Please output the answer for customers in the same order they appeared in input.

Example
Input
1
3 3
1 100 300
3 5 300
4 3 10
2 100
5 6
50 100
Output
1 2 1