2018 Chinese Multi-University Training, BeihangU Contest
A. Always Online
time limit per test
4 s
memory limit per test
256 mebibytes
input
standard input
output
standard output

Wayne is an administrator of some metropolitan area network. The network he managed can be formed into a simple connected graph with n vertices and m edges, which means the graph does not contain any self-loop and there is at most one edge and at least one path between every two vertices. Furthermore, the network also meets the condition there are at most two non-intersect paths, which share no common edges, between every two vertices.

Wayne knows the bandwidth of each edge in that network but it is not enough for him. He needs plenty of statistic data to display, for example, he wants to know what the maximum data rate between every two vertices is. For the sake of clarity, vertices in that are numbered from 1 to n and the maximum bits each edge could transmit per second will be given. Your task is assisting him to calculate the value of the following formula:

where means the bitwise exclusive-OR operator and means the maximum bits that could be transmitted per second between vertex s and vertex t.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains two integers n and m.

Each of the following m lines contains three integers u, v and w, indicating a bidirectional edge between vertex u and vertex v that can transmit at most w bits per second in each direction.

1 ≤ T ≤ 100, 1 ≤ n ≤ 105, , 1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w < 109.

It is guaranteed that the sum of n in all test cases does not exceed 106 and the size of the standard input file does not exceed 26 MiB.

Output

For each test case, print the answer in one line.

Example
Input
2
3 3
1 2 5
2 3 6
3 1 5
5 6
1 2 5
2 3 6
3 1 5
3 4 6
4 5 5
5 3 6
Output
27
116
Note

For the first sample, , .

B. Beautiful Now
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits.

Let the decimal representation of n as (x1x2... xm)10 satisfying that 1 ≤ x1 ≤ 9, 0 ≤ xi ≤ 9 (2 ≤ i ≤ m), which means . In each swap, Anton can select two digits xi and xj (1 ≤ i ≤ j ≤ m) and then swap them if the integer after this swap has no leading zero.

Could you please tell him the minimum integer and the maximum integer he can obtain after k swaps?

Input

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains two space-separated integers n and k.

1 ≤ T ≤ 100, 1 ≤ n, k ≤ 109.

Output

For each test case, print in one line the minimum integer and the maximum integer which are separated by one space.

Example
Input
5
12 1
213 2
998244353 1
998244353 2
998244353 3
Output
12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332
C. Call It What You Want
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

As a stereotyped math fanatic, Taylor is expert on utilizing scientific computing tools but he is poor at programming infrastructures, which brings him endless powerlessness.

Recently he worked on factoring polynomials of the form (xn - 1) over the integers, which aims to express any polynomial of that form as some product of irreducible factors whose coefficients are all in the integers.

With knowledge of the cyclotomic polynomial, he has known that where each factor of that is just an irreducible polynomial over the integers. Moreover, , where is the unit complex root of degree n and is the greatest common divisor of n and k.

Although he found such a conclusion, he couldn't obtain the result of some high-degree polynomial in a few seconds. Could you please help him accomplish some factorizations of (xn - 1)?

Here are some examples:

  • Φ1(x) = x - 1;
  • Φ2(x) = x + 1, x2 - 1 = (x - 1)(x + 1);
  • Φ3(x) = x2 + x + 1, x3 - 1 = (x - 1)(x2 + x + 1);
  • Φ4(x) = x2 + 1, x4 - 1 = (x - 1)(x + 1)(x2 + 1);
  • Φ6(x) = x2 - x + 1, x6 - 1 = (x - 1)(x + 1)(x2 - x + 1)(x2 + x + 1);
  • Φ12(x) = x4 - x2 + 1, x12 - 1 = (x - 1)(x + 1)(x2 - x + 1)(x2 + 1)(x2 + x + 1)(x4 - x2 + 1).

Oops! You might have some observations such as the degree of Φn(x) equals to φ(n), coefficients of Φn(x) are the same back-to-front as front-to-back except for Φ1(x), when p is prime, etc. , but they might be worthless for solving.

Input

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains only one integer n.

1 ≤ T ≤ 100, 2 ≤ n ≤ 105.

It is guaranteed that the sum of n in all test cases does not exceed 5·106.

Output

For each test case, output the factorization as a string without any space in one line, where the polynomials should be sorted in a particular order and each polynomial should be printed in a particular format and enclosed in a pair of parentheses.

Order of polynomials: The order of polynomial f(x) is lower than that of polynomial g(x) if and only if there exists a non-negative integer m such that the coefficient of xk (k = m + 1, m + 2, ...) in f(x) equals to that of g(x) but the coefficient of xm in f(x) is less than that of g(x).

Output format of one polynomial: Output all the terms of the polynomial from high-degree to low-degree, each of which should be formed as  ± ckxk. Additionally,

  1. One term should be omitted if its coefficient is zero.
  2. The sign of the first term ( ± ) should be omitted if the coefficient of that item is positive.
  3. When ck = 1, ck should be omitted unless k = 0.
  4. x0 should be omitted while x1 should be written as a simple x.

It is guaranteed that the size of the standard output file does not exceed 26 MiB.

Example
Input
5
2
3
4
6
12
Output
(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+1)(x^2+x+1)(x^4-x^2+1)
D. Daylight
time limit per test
13 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Noah owns an unrooted tree with n vertices which are numbered from 1 to n. Every morning Noah would like to pick two vertices u and v to get influence from daylight and then the influence spreads through edges, but the influence will be disappeared if it has passed through more than w edges.

Your task is to calculate the number of vertices influenced by the daylight for each day. In addition, input data will be encrypted to make sure your solution is online.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains two integers n and m.

Each of the following (n - 1) lines contains two integers u and v, indicating an edge between vertex u and vertex v.

Let be the last answer before each day. At the beginning day of each test case, is initialized as 0.

Each of the following m lines contains three integers u', v' and w', satifying , , , which means one day Noah will pick vertices u and v to get influence and the influence will be disappeared if it has passed through more than w edges.

1 ≤ T ≤ 100, 1 ≤ n, m ≤ 105, 1 ≤ u, v, u', v' ≤ n, 0 ≤ w' < n.

It is guaranteed that no more than 10 test cases do not satisfy n, m ≤ 103 and the size of the standard input file does not exceed 32 MiB.

Output

For each day, print the answer in one line.

It is guaranteed that the size of the standard output file does not exceed 7 MiB.

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

The decrypted information is the following:

  • Day 1: u = 1, v = 2, w = 0;
  • Day 2: u = 1, v = 2, w = 1;
  • Day 3: u = 1, v = 2, w = 2;
  • Day 4: u = 1, v = 2, w = 3;
  • Day 5: u = 1, v = 2, w = 4.
E. Everything Has Changed
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

Edward is a worker for Aluminum Cyclic Machinery. His work is operating mechanical arms to cut out designed models. Here is a brief introduction to his work.

Assume the operating plane as a two-dimensional coordinate system. At first, there is a disc with center coordinates (0, 0) and radius R. Then, m mechanical arms will cut and erase everything within its area of influence simultaneously, the i-th area of which is a circle with center coordinates (xi, yi) and radius ri (i = 1, 2, ..., m). In order to obtain considerable models, it is guaranteed that every two cutting areas have no intersection and no cutting area contains the whole disc.

Your task is to determine the perimeter of the remaining area of the disc excluding internal perimeter.

Here is an illustration of the sample, in which the red curve is counted but the green curve is not.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains two integers m and R.

The i-th line of the following m lines contains three integers xi, yi and ri, indicating a cutting area.

1 ≤ T ≤ 1000, 1 ≤ m ≤ 100,  - 1000 ≤ xi, yi ≤ 1000, 1 ≤ R, ri ≤ 1000 (i = 1, 2, ..., m).

Output

For each test case, print the perimeter of the remaining area in one line. Your answer is considered correct if its absolute or relative error does not exceed 10 - 6.

Formally, let your answer be a and the jury's answer be b. Your answer is considered correct if .

Example
Input
1
4 10
6 3 5
10 -4 3
-2 -4 4
0 9 1
Output
81.62198908430238475376
F. Fireflies
time limit per test
3 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Randal is a master of high-dimensional space. All the species living in his space are regarded as fireflies for him. One day he came up with a problem but failed to solve it. Are you the one who can solve that?

There is one n-dimensional hypercubic subspace that he wants to cover by the minimal number of fireflies. The side lengths of the space are p1, p2, ..., pn, which means this space can be formed into hypercubic units.

One unit is considered as covered if there exists a firefly that has visited it. Each firefly is able to cover several units through its own traveling. Assuming a firefly is located at the coordinate (x1, x2, ..., xn) with 1 ≤ xi ≤ pi (i = 1, 2, ..., n), it can move to another coordinate (y1, y2, ..., yn) if 1 ≤ xi ≤ yi ≤ pi (i = 1, 2, ..., n) and . In addition, The travel of one firefly can start or end at any location and might have any times of moves but one firefly could only travel once.

Your task is to determine the minimum number of fireflies that should be involved and print the answer in modulo (109 + 7).

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains one integer n, indicating the dimension of the space.

The second line contains n space-separated integers, indicating the side lengths of the space.

1 ≤ T ≤ 2000, 1 ≤ n ≤ 32, 1 ≤ pi ≤ 109 (i = 1, 2, ..., n).

It is guaranteed that no more than 200 test cases satisfy n > 8, no more than 20 test cases satisfy n > 16 and no more than 2 test cases satisfy n > 24.

Output

For each test case, print the answer modulo (109 + 7) in one line.

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

For the first sample, one firefly could cover all the units.

For the second sample, one possible best way is that each firefly covers all the units with the same second coordinate, which involves three fireflies.

G. Glad You Came
time limit per test
4 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Steve has an integer array a of length n (1-based). He assigned all the elements as zero at the beginning. After that, he made m operations, each of which is to update an interval of a with some value. You need to figure out after all his operations are finished, where means the bitwise exclusive-OR operator.

In order to avoid huge input data, these operations are encrypted through some particular approach.

There are three unsigned 32-bit integers X, Y and Z which have initial values given by the input. A random number generator function is described as following, where means the bitwise exclusive-OR operator,  <  <  means the bitwise left shift operator and  >  >  means the bitwise right shift operator. Note that function would change the values of X, Y and Z after calling.

Let the i-th result value of calling the above function as fi (i = 1, 2, ..., 3m). The i-th operation of Steve is to update aj as vi if aj < vi (j = li, li + 1, ..., ri), where

Input

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains five space-separated integers n, m, X, Y and Z.

1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 1 ≤ m ≤ 5·106, 0 ≤ X, Y, Z < 230.

It is guaranteed that the sum of n in all the test cases does not exceed 106 and the sum of m in all the test cases does not exceed 5·107.

Output

For each test case, output the answer in one line.

Example
Input
4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000
Output
1031463378
1446334207
351511856
47320301347
Note

In the first sample, a = [1031463378] after all the operations.

In the second sample, a = [1036205629,  1064909195,  1044643689,  1062944339,  1062944339,  1062944339,  1062944339,  1057472915,  1057472915,  1030626924] after all the operations.

H. Hills And Valleys
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

Tauren has an integer sequence A of length n (1-based). He wants you to invert an interval [l, r] (1 ≤ l ≤ r ≤ n) of A (that is, replace Al, Al + 1, ..., Ar with Ar, Ar - 1, ..., Al) to maximize the length of the longest non-decreasing subsequence of A. Find that maximal length and any inverting way to accomplish that mission.

A non-decreasing subsequence of A with length m could be represented as Ax1, Ax2, ..., Axm with 1 ≤ x1 < x2 < ... < xm ≤ n and Ax1 ≤ Ax2 ≤ ... ≤ Axm.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains one integer n.

The second line contains n integers A1, A2, ..., An without any space.

1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 0 ≤ Ai ≤ 9 (i = 1, 2, ..., n).

It is guaranteed that the sum of n in all test cases does not exceed 2·105.

Output

For each test case, print three space-separated integers m, l and r in one line, where m indicates the maximal length and [l, r] indicates the relevant interval to invert.

Example
Input
2
9
864852302
9
203258468
Output
5 1 8
6 1 2
Note

In the first example, 864852302 after inverting [1, 8] is 032584682, one of the longest non-decreasing subsequences of which is 03588.

In the second example, 203258468 after inverting [1, 2] is 023258468, one of the longest non-decreasing subsequences of which is 023588.

I. Innocence
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

David is a young child. He likes playing combinatorial games, for example, the Nim game. He is just an amateur but he is sophisticated with game theory. This time he has prepared a problem for you.

Given integers N, L, R and K, you are asked to count in how many ways one can arrange an integer array of length N such that all its elements are ranged from L to R (inclusive) and the bitwise exclusive-OR of them equals to K. To avoid calculations of huge integers, print the number of ways in modulo (109 + 7).

In addition, David would like you to answer with several integers K in order to ensure your solution is completely correct.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains four space-separated integers N, L, R and Q, indicating there are Q queries with the same N, L, R but different K.

The second line contains Q space-separated integers, indicating several integers K.

1 ≤ T ≤ 1000, 1 ≤ N ≤ 109, 0 ≤ L ≤ R < 230, 1 ≤ Q ≤ 100, 0 ≤ K < 230.

It is guaranteed that no more than 100 test cases do not satisfy 1 ≤ N ≤ 15, 0 ≤ L, R, K < 215.

Output

For each query, print the answer modulo (109 + 7) in one line.

Example
Input
3
2 3 4 2
0 7
3 3 4 2
3 4
5 5 7 4
5 6 7 8
Output
2
2
4
4
61
61
61
0
Note

In the first sample, there are two ways to select one number 3 and one number 4 such that the exclusive-OR of them is 7.

In the second sample, there are three ways to select one number 3 and two numbers 4 and one way to select three numbers 3 such that the exclusive-OR of them is 3.

J. Just So You Know
time limit per test
3 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Matthew is a wise man and Jesse is his best friend. One day, Jesse gave Matthew an integer sequence A of length n and marked one continuous subsequence B of A privately. Matthew didn't know the sequence B at first, but he can guess out the sequence by conjectures. That is, once he claims some conjecture, Jesse will immediately tell him whether the conjecture is true or not.

Matthew has known the sequence B is an interval selected from the sequence A with equal probability. A wise man is never confused, so Matthew will minimize the expected number of conjectures he needs to figure out the sequence B. Could you please determine that expected value? Your answer should be an irreducible fraction p / q, which means p and q are coprime.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains one integer n.

The second line contains n space-separated integers A1, A2, ..., An.

1 ≤ T ≤ 1000, 1 ≤ n ≤ 106, 0 ≤ Ai < 100 (i = 1, 2, ..., n).

It is guaranteed that the sum of n in all test cases does not exceed 107 and the size of the standard input file does not exceed 24 MiB.

Output

For each test case, print in one line the answer as an irreducible fraction p / q if q ≠ 1 or a simple p otherwise.

Example
Input
3
2
1 1
4
1 2 1 1
6
1 1 4 5 1 4
Output
1
29/10
85/21
Note

Here is one possible best solution for the second sample. Claim Conjecture 1 firstly and others consequently following the instructions.

  • Conjecture 1: The number of 1 in B is odd. If true, go to Conjecture 2, else go to Conjecture 3.
  • Conjecture 2: The length of B is 1. If true, B is [1], else go to Conjecture 4.
  • Conjecture 3: The first element of B is 1. If true, go to Conjecture 5, else go to Conjecture 6.
  • Conjecture 4: The length of B is 4. If true, B is [1, 2, 1, 1], else go to Conjecture 7.
  • Conjecture 5: The length of B is 3. If true, B is [1, 2, 1], else B is [1, 1].
  • Conjecture 6: The length of B is 1. If true, B is [2], else B is [2, 1, 1].
  • Conjecture 7: The first element of B is 1. If true, B is [1, 2], else B is [2, 1].
K. Kaleidoscope
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

John loves colorful things such as kaleidoscope. When he started to take advantage of Wolfram Alpha, a scientific computing tool, he fell in love with its current logo, a rhombic hexecontahedron, immediately.

Wolfram|Alpha Computational Intelligence

The rhombic hexecontahedron is a beautiful polyhedron which has 60 congruent rhombic faces. A rhombic hexecontahedron can be constructed from a regular dodecahedron, by taking its vertices, its face centers and its edge centers and scaling them in or out from the body center to different extents. Also, a rhombic hexecontahedron can be constructed from a regular icosahedron, by appending three rhombuses to each of its faces such that each rhombus shares a vertex with it and every two rhombuses share an edge.

John wants to make some origami of rhombic hexecontahedron. Before getting started from scratch, he was wondering in how many different ways he can make origami of at most n types of colored paper. He has thought for a while and finally determined to leave this problem for you. Furthermore, he added some restriction such that a way of origami is counted if the number of faces colored by the i-th type of paper is at least ci (i = 1, 2, ..., n). Of course, the answer might be so large, so you just need to tell him the answer modulo some integer p.

Two ways are considered as the same if and only if there exists a way of rotation that can transform one to another so that each corresponding face has the same color. Here is an example of origami after coloring.

Picture from Wolfram Mathworld

In addition, he thought you might need a plane expansion for better understanding, however, because the plane expansion of a rhombic hexecontahedron is quite unreadable, he left here a modified plane expansion of a regular dodecahedron to illustrate approximately. Hope this image will help you solve this problem.

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains two space-separated integers n and p.

The second line contains n space-separated integers c1, c2, ..., cn.

1 ≤ T ≤ 1000, 1 ≤ n ≤ 60, 1 ≤ p < 230, 0 ≤ ci ≤ 60 (i = 1, 2, ..., n).

It is guaranteed that no more than 100 test cases satisfy n > 5.

Output

For each test case, print the answer modulo p in one line.

Example
Input
5
2 1000000007
0 0
2 1000000007
1 0
2 1000000007
0 2
2 1000000007
1 1
5 1000000007
1 1 1 1 1
Output
544393230
544393229
544393228
544393228
905148476
L. Lost In The Echo
time limit per test
8 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Charles enjoys learning. He often goes to the website Wikipedia to study computer science. Just now Charles seriously studied a series of expressions, in which algebraic expression has a great influence on him.

He is curious about how many different algebraic expressions that can be built up from n distinct variables, elementary arithmetic operations (addition, subtraction, multiplication and division), and brackets such that each variable appears exactly once and each operation is after a variable or a pair of brackets. Can you help him calculate the answer in modulo (109 + 7)?

Two algebraic expressions in this problem are considered as equivalent if and only if they can be simplified as the same rational expression. For example, assuming a, b, c and d are variables, (a - d) / (b - c) is equivalent to (d - a) / (c - b), a / (b - c) * d is equivalent to a / ((b - c) / d), but a / b + c / d is not equivalent to d / c + b / a.

Input

The first line contains one integer T, indicating the number of test cases.

Each of the following T lines describes a test case and contains only one integer n.

1 ≤ T, n ≤ 60 000.

Output

For each test case, output the answer modulo (109 + 7) in one line.

Example
Input
6
1
2
3
4
5
6
Output
1
6
68
1170
27142
793002