vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
While mostly known for the programs she wrote for Charles Babbage’s Analytic Engine, Augusta Ada King-Noel, Countess of Lovelace, described how the method of finite differences could be used to solve all types of problems involving number sequences and series. These techniques were implemented in Babbage’s Difference Engine.

The algorithm: If we compute the difference between consecutive values in a numeric sequence, we will obtain a new sequence which is related to the derivative of the function implied by the original sequence. For sequences generated from first-order polynomials (linear functions) the successive differences will be a list of identical values, (i.e., a constant difference). For second-order polynomial functions the lists of differences will be a new sequence whose values change linearly. In turn, the list of differences of the values in this generated list (i.e., the finite differences of the list of differences) will be constant, and so on for higher-order polynomials. In general the $n^{\text {th}}$ row of differences will be constant for an $n^{\text {th}}$ degree polynomial.

For example, the first-order polynomial $3x + 3$ produces the sequence below at $x=0,1,2,3,4$, and the first differences are shown on the following line.

3     6     9    12    15   3     3     3     3

As another example, the polynomial $x^2$, if evaluated at inputs $x=3, 5, 7, 9,$ produces the sequence below.

9    25    49    81
  16    24    32 8     8

Furthermore, if we consider a minimum-order polynomial that produces the original sequence, its value at the next regularly spaced input can be predicted by extending the difference table.

-----Input-----
The input consists of a value $n$, designating the number of polynomial evaluations given with $2 \leq n \leq 10$, follwed by $n$ values $v_1, v_2, \ldots , v_{n}$ which represent the value of a polynomial when evaluated at $n$ regularly spaced input values. Each $v_ j$ will satisfy $-2000000 \leq v_ j \leq 2000000$ and at least two of those values will differ from each other.

-----Output-----
Output two integer values $d$ and $v_{n+1}$, separated by a space. The value $d$ must be the degree of a minimal-degree polynomial producing the original sequence, and $v_{n+1}$ must be the value of the polynomial if evaluated at the next regularly spaced input value.

-----Examples-----
Sample Input 1:
5 3 6 9 12 15
Sample Output 1:
1 18

Sample Input 2:
4 9 25 49 81
Sample Output 2:
2 121

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Berland Army is preparing for a large military parade. It is already decided that the soldiers participating in it will be divided into k rows, and all rows will contain the same number of soldiers.

Of course, not every arrangement of soldiers into k rows is suitable. Heights of all soldiers in the same row should not differ by more than 1. The height of each soldier is an integer between 1 and n.

For each possible height, you know the number of soldiers having this height. To conduct a parade, you have to choose the soldiers participating in it, and then arrange all of the chosen soldiers into k rows so that both of the following conditions are met:

  * each row has the same number of soldiers, 
  * no row contains a pair of soldiers such that their heights differ by 2 or more. 



Calculate the maximum number of soldiers who can participate in the parade.

Input

The first line contains one integer t (1 ≤ t ≤ 10000) — the number of test cases. Then the test cases follow. 

Each test case begins with a line containing two integers n and k (1 ≤ n ≤ 30000, 1 ≤ k ≤ 10^{12}) — the number of different heights of soldiers and the number of rows of soldiers in the parade, respectively.

The second (and final) line of each test case contains n integers c_1, c_2, ..., c_n (0 ≤ c_i ≤ 10^{12}), where c_i is the number of soldiers having height i in the Berland Army.

It is guaranteed that the sum of n over all test cases does not exceed 30000.

Output

For each test case, print one integer — the maximum number of soldiers that can participate in the parade.

Example

Input


5
3 4
7 1 13
1 1
100
1 3
100
2 1
1000000000000 1000000000000
4 1
10 2 11 1


Output


16
100
99
2000000000000
13

Note

Explanations for the example test cases:

  1. the heights of soldiers in the rows can be: [3, 3, 3, 3], [1, 2, 1, 1], [1, 1, 1, 1], [3, 3, 3, 3] (each list represents a row); 
  2. all soldiers can march in the same row; 
  3. 33 soldiers with height 1 in each of 3 rows; 
  4. all soldiers can march in the same row; 
  5. all soldiers with height 2 and 3 can march in the same row. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr Keks is a typical white-collar in Byteland.

He has a bookshelf in his office with some books on it, each book has an integer positive price.

Mr Keks defines the value of a shelf as the sum of books prices on it. 

Miraculously, Mr Keks was promoted and now he is moving into a new office.

He learned that in the new office he will have not a single bookshelf, but exactly $k$ bookshelves. He decided that the beauty of the $k$ shelves is the bitwise AND of the values of all the shelves.

He also decided that he won't spend time on reordering the books, so he will place several first books on the first shelf, several next books on the next shelf and so on. Of course, he will place at least one book on each shelf. This way he will put all his books on $k$ shelves in such a way that the beauty of the shelves is as large as possible. Compute this maximum possible beauty.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 50$) — the number of books and the number of shelves in the new office.

The second line contains $n$ integers $a_1, a_2, \ldots a_n$, ($0 < a_i < 2^{50}$) — the prices of the books in the order they stand on the old shelf.


-----Output-----

Print the maximum possible beauty of $k$ shelves in the new office.


-----Examples-----
Input
10 4
9 14 28 1 7 13 15 29 2 31

Output
24

Input
7 3
3 14 15 92 65 35 89

Output
64



-----Note-----

In the first example you can split the books as follows:

$$(9 + 14 + 28 + 1 + 7) \& (13 + 15) \& (29 + 2) \& (31) = 24.$$

In the second example you can split the books as follows:

$$(3 + 14 + 15 + 92) \& (65) \& (35 + 89) = 64.$$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Help Farmer

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Once upon a time in the Kingdom of Far Far Away lived Sam the Farmer. Sam had a cow named Dawn and he was deeply attached to her. Sam would spend the whole summer stocking hay to feed Dawn in winter. Sam scythed hay and put it into haystack. As Sam was a bright farmer, he tried to make the process of storing hay simpler and more convenient to use. He collected the hay into cubical hay blocks of the same size. Then he stored the blocks in his barn. After a summer spent in hard toil Sam stored *A*·*B*·*C* hay blocks and stored them in a barn as a rectangular parallelepiped *A* layers high. Each layer had *B* rows and each row had *C* blocks.

At the end of the autumn Sam came into the barn to admire one more time the hay he'd been stacking during this hard summer. Unfortunately, Sam was horrified to see that the hay blocks had been carelessly scattered around the barn. The place was a complete mess. As it turned out, thieves had sneaked into the barn. They completely dissembled and took away a layer of blocks from the parallelepiped's front, back, top and sides. As a result, the barn only had a parallelepiped containing (*A*<=-<=1)<=×<=(*B*<=-<=2)<=×<=(*C*<=-<=2) hay blocks. To hide the evidence of the crime, the thieves had dissembled the parallelepiped into single 1<=×<=1<=×<=1 blocks and scattered them around the barn. After the theft Sam counted *n* hay blocks in the barn but he forgot numbers *A*, *B* и *C*.

Given number *n*, find the minimally possible and maximally possible number of stolen hay blocks.

Input Specification:
The only line contains integer *n* from the problem's statement (1<=≤<=*n*<=≤<=109).

Output Specification:
Print space-separated minimum and maximum number of hay blocks that could have been stolen by the thieves.

Note that the answer to the problem can be large enough, so you must use the 64-bit integer type for calculations. Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

Demo Input:
['4\n', '7\n', '12\n']

Demo Output:
['28 41\n', '47 65\n', '48 105\n']

Note:
Let's consider the first sample test. If initially Sam has a parallelepiped consisting of 32 = 2 × 4 × 4 hay blocks in his barn, then after the theft the barn has 4 = (2 - 1) × (4 - 2) × (4 - 2) hay blocks left. Thus, the thieves could have stolen 32 - 4 = 28 hay blocks. If Sam initially had a parallelepiped consisting of 45 = 5 × 3 × 3 hay blocks in his barn, then after the theft the barn has 4 = (5 - 1) × (3 - 2) × (3 - 2) hay blocks left. Thus, the thieves could have stolen 45 - 4 = 41 hay blocks. No other variants of the blocks' initial arrangement (that leave Sam with exactly 4 blocks after the theft) can permit the thieves to steal less than 28 or more than 41 blocks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Luba And The Ticket

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Luba has a ticket consisting of 6 digits. In one move she can choose digit in any position and replace it with arbitrary digit. She wants to know the minimum number of digits she needs to replace in order to make the ticket lucky.

The ticket is considered lucky if the sum of first three digits equals to the sum of last three digits.

Input Specification:
You are given a string consisting of 6 characters (all characters are digits from 0 to 9) — this string denotes Luba's ticket. The ticket can start with the digit 0.

Output Specification:
Print one number — the minimum possible number of digits Luba needs to replace to make the ticket lucky.

Demo Input:
['000000\n', '123456\n', '111000\n']

Demo Output:
['0\n', '2\n', '1\n']

Note:
In the first example the ticket is already lucky, so the answer is 0.

In the second example Luba can replace 4 and 5 with zeroes, and the ticket will become lucky. It's easy to see that at least two replacements are required.

In the third example Luba can replace any zero with 3. It's easy to see that at least one replacement is required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem.

You are given a weighted directed graph with n vertices and m edges. You need to find a path (perhaps, non-simple) with maximum number of edges, such that the weights of the edges increase along the path. In other words, each edge of the path must have strictly greater weight than the previous edge in the path.

Help Pashmak, print the number of edges in the required path.


-----Input-----

The first line contains two integers n, m (2 ≤ n ≤ 3·10^5; 1 ≤ m ≤ min(n·(n - 1), 3·10^5)). Then, m lines follows. The i-th line contains three space separated integers: u_{i}, v_{i}, w_{i} (1 ≤ u_{i}, v_{i} ≤ n; 1 ≤ w_{i} ≤ 10^5) which indicates that there's a directed edge with weight w_{i} from vertex u_{i} to vertex v_{i}.

It's guaranteed that the graph doesn't contain self-loops and multiple edges.


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
3 3
1 2 1
2 3 1
3 1 1

Output
1

Input
3 3
1 2 1
2 3 2
3 1 3

Output
3

Input
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4

Output
6



-----Note-----

In the first sample the maximum trail can be any of this trails: $1 \rightarrow 2,2 \rightarrow 3,3 \rightarrow 1$.

In the second sample the maximum trail is $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$.

In the third sample the maximum trail is $1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integer sequences, each of length N: a_1, ..., a_N and b_1, ..., b_N.
There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N. For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper.
That is, we will write N^2 integers in total.
Compute the XOR of these N^2 integers.
Definition of XOR
The XOR of integers c_1, c_2, ..., c_m is defined as follows:
 - Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.
For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

-----Constraints-----
 - All input values are integers.
 - 1 \leq N \leq 200,000
 - 0 \leq a_i, b_i < 2^{28}

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

-----Output-----
Print the result of the computation.

-----Sample Input-----
2
1 2
3 4

-----Sample Output-----
2

On the sheet, the following four integers will be written: 4(1+3), 5(1+4), 5(2+3) and 6(2+4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some viruses replicate by replacing a piece of DNA in a living cell with a piece of DNA that the virus carries with it. This makes the cell start to produce viruses identical to the original one that infected the cell. A group of biologists is interested in knowing how much DNA a certain virus inserts into the host genome. To find this out they have sequenced the full genome of a healthy cell as well as that of an identical cell infected by a virus.

The genome turned out to be pretty big, so now they need your help in the data processing step. Given the DNA sequence before and after the virus infection, determine the length of the smallest single, consecutive piece of DNA that can have been inserted into the first sequence to turn it into the second one. A single, consecutive piece of DNA might also have been removed from the same position in the sequence as DNA was inserted. Small changes in the DNA can have large effects, so the virus might insert only a few bases, or even nothing at all.

-----Input-----
The input consists of two lines containing the DNA sequence before and after virus infection respectively. A DNA sequence is given as a string containing between 1 and $10^5$ upper-case letters from the alphabet {A, G, C, T}.

-----Output-----
Output one integer, the minimum length of DNA inserted by the virus.

-----Examples-----
Sample Input:
AAAAA
AGCGAA
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This weekend John is headed to visit the new fun city in town. A very popular game is called the "Ladder of odds".

In this game, you have to climb up the ladder of height h, using only odd number of steps. But you don't progress to the next level unless you climb down as well..!!!

For example: If we have a ladder of height 4 we can go up in 3 ways (1 + 1 + 1 + 1, 3 + 1, 1 + 3) .

Being the curious kid that John is, he would like to know the total number of ways to do so. 

Moreover, the entire place contains these game ladders of varying heights up to N.

So, the 1st game has h = 1, the 2nd game has h = 2, and so on upto the Nth game.

Determine the summation of number of ways to complete each game if a new game can only be started after completion of previous game.

Input:

The first line contains number of test cases, T. Each of the following T lines contain an integer N, as defined above.

Output:

Each line of output should contain exactly one number indicating answer of corresponding test case. Output may be too large so print it modulo 10^9+9.

Constraints:

1 ≤ T ≤ 100000 
1 ≤ N ≤ 10^15

SAMPLE INPUT
3
1
2
3

SAMPLE OUTPUT
1
2
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected graph consisting of $n$ vertices and $n$ edges, where $n$ is divisible by $6$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $\frac{n}{3}$ triples of vertices, the first triple consisting of vertices $1, 2, 3$, the second triple consisting of vertices $4, 5, 6$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $\frac{n}{2}$ red vertices and $\frac{n}{2}$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $W$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $W$, and print it modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($6 \le n \le 3 \cdot 10^5$, $n$ is divisible by $6$).

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1000$) — the weights of the edges. Edge $1$ connects vertices $1$ and $2$, edge $2$ connects vertices $1$ and $3$, edge $3$ connects vertices $2$ and $3$, edge $4$ connects vertices $4$ and $5$, edge $5$ connects vertices $4$ and $6$, edge $6$ connects vertices $5$ and $6$, and so on.


-----Output-----

Print one integer — the number of valid colorings with maximum possible weight, taken modulo $998244353$.


-----Examples-----

Input
12
1 3 3 7 8 5 2 2 2 2 4 2
Output
36
Input
6
4 2 6 6 6 4
Output
2


-----Note-----

The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $31$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a permutation p_1, p_2, ... p_n of integers from 1 to n. We call a sub-segment p_l, p_{l+1}, ..., p_{r-1}, p_{r} of the permutation an interval if it is a reordering of some set of consecutive integers. For example, the permutation (6,7,1,8,5,3,2,4) has the intervals (6,7), (5,3,2,4), (3,2), and others. 

Each permutation has some trivial intervals — the full permutation itself and every single element. We call a permutation interval-free if it does not have non-trivial intervals. In other words, interval-free permutation does not have intervals of length between 2 and n - 1 inclusive. 

Your task is to count the number of interval-free permutations of length n modulo prime number p. 

Input

In the first line of the input there are two integers t (1 ≤ t ≤ 400) and p (10^8 ≤ p ≤ 10^9) — the number of test cases to solve and the prime modulo. In each of the next t lines there is one integer n (1 ≤ n ≤ 400) — the length of the permutation. 

Output

For each of t test cases print a single integer — the number of interval-free permutations modulo p. 

Examples

Input


4 998244353
1
4
5
9


Output


1
2
6
28146


Input


1 437122297
20


Output


67777575

Note

For n = 1 the only permutation is interval-free. For n = 4 two interval-free permutations are (2,4,1,3) and (3,1,4,2). For n = 5 — (2,4,1,5,3), (2,5,3,1,4), (3,1,5,2,4), (3,5,1,4,2), (4,1,3,5,2), and (4,2,5,1,3). We will not list all 28146 for n = 9, but for example (4,7,9,5,1,8,2,6,3), (2,4,6,1,9,7,3,8,5), (3,6,9,4,1,5,8,2,7), and (8,4,9,1,3,6,2,7,5) are interval-free.

The exact value for n = 20 is 264111424634864638. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the questions children often ask is "How many stars are there in the sky?" Under ideal conditions, even with the naked eye, nearly eight thousands are observable in the northern hemisphere. With a decent telescope, you may find many more, but, as the sight field will be limited, you may find much less at a time.

Children may ask the same questions to their parents on a planet of some solar system billions of light-years away from the Earth. Their telescopes are similar to ours with circular sight fields, but alien kids have many eyes and can look into different directions at a time through many telescopes.

Given a set of positions of stars, a set of telescopes and the directions they are looking to, your task is to count up how many stars can be seen through these telescopes.



Input

The input consists of one or more datasets. The number of datasets is less than 50. Each dataset describes stars and the parameters of the telescopes used.

The first line of a dataset contains a positive integer n not exceeding 500, meaning the number of stars. Each of the n lines following it contains three decimal fractions, sx, sy, and sz. They give the position (sx, sy, sz) of the star described in Euclidean coordinates. You may assume -1000 ≤ sx ≤ 1000, -1000 ≤ sy ≤ 1000, -1000 ≤ sz ≤ 1000 and (sx, sy, sz) ≠ (0, 0, 0).

Then comes a line containing a positive integer m not exceeding 50, meaning the number of telescopes. Each of the following m lines contains four decimal fractions, tx, ty, tz, and φ, describing a telescope.

The first three numbers represent the direction of the telescope. All the telescopes are at the origin of the coordinate system (0, 0, 0) (we ignore the size of the planet). The three numbers give the point (tx, ty, tz) which can be seen in the center of the sight through the telescope. You may assume -1000 ≤ tx ≤ 1000, -1000 ≤ ty ≤ 1000, -1000 ≤ tz ≤ 1000 and (tx, ty, tz) ≠ (0, 0, 0).

The fourth number φ (0 ≤ φ ≤ π/2) gives the angular radius, in radians, of the sight field of the telescope.

Let us defie that θi,j is the angle between the direction of the i-th star and the center direction of the j-th telescope and φjis the angular radius of the sight field of the j-th telescope. The i-th star is observable through the j-th telescope if and only if θi,j is less than . You may assume that |θi,j - φj| > 0.00000001 for all pairs of i and j.

<image>


Figure 1: Direction and angular radius of a telescope

The end of the input is indicated with a line containing a single zero.

Output

For each dataset, one line containing an integer meaning the number of stars observable through the telescopes should be output. No other characters should be contained in the output. Note that stars that can be seen through more than one telescope should not be counted twice or more.

Example

Input

3
100 0 500
-500.243 -200.1 -300.5
0 300 200
2
1 1 1 0.65
-1 0 0 1.57
3
1 0 0
0 1 0
0 0 1
4
1 -1 -1 0.9553
-1 1 -1 0.9554
-1 -1 1 0.9553
-1 1 -1 0.9554
3
1 0 0
0 1 0
0 0 1
4
1 -1 -1 0.9553
-1 1 -1 0.9553
-1 -1 1 0.9553
-1 1 -1 0.9553
0


Output

2
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.