vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Iahub is training for the IOI. What is a better way to train than playing a Zuma-like game? 

There are n balls put in a row. Each ball is colored in one of k colors. Initially the row doesn't contain three or more contiguous balls with the same color. Iahub has a single ball of color x. He can insert his ball at any position in the row (probably, between two other balls). If at any moment there are three or more contiguous balls of the same color in the row, they are destroyed immediately. This rule is applied multiple times, until there are no more sets of 3 or more contiguous balls of the same color. 

For example, if Iahub has the row of balls [black, black, white, white, black, black] and a white ball, he can insert the ball between two white balls. Thus three white balls are destroyed, and then four black balls become contiguous, so all four balls are destroyed. The row will not contain any ball in the end, so Iahub can destroy all 6 balls.

Iahub wants to destroy as many balls as possible. You are given the description of the row of balls, and the color of Iahub's ball. Help Iahub train for the IOI by telling him the maximum number of balls from the row he can destroy.


-----Input-----

The first line of input contains three integers: n (1 ≤ n ≤ 100), k (1 ≤ k ≤ 100) and x (1 ≤ x ≤ k). The next line contains n space-separated integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ k). Number c_{i} means that the i-th ball in the row has color c_{i}.

It is guaranteed that the initial row of balls will never contain three or more contiguous balls of the same color. 


-----Output-----

Print a single integer — the maximum number of balls Iahub can destroy.


-----Examples-----
Input
6 2 2
1 1 2 2 1 1

Output
6

Input
1 1 1
1

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xynazog was playing a game. He needed to score k points and he could play at most N moves and at least 1 move. In each move, he could get [0,k] points. Note: the number of points gained is always an integer.

Xynazog's friend PowerShell challenged Xenny to find the number of ways in which he could score k points in exactly N moves as per the given rules.

Input Format:

First line contains a natural no. T, denoting the no. of testcases.
Each of the following T lines contains 2 space-separated integers N and k.

Output Format:

Output the answer to each testcase on a new line.

Constraints:

1 ≤ T ≤ 100000

1 ≤ N,k ≤ 19

SAMPLE INPUT
1
2 2

SAMPLE OUTPUT
3

Explanation

Given k=2

k = 2 + 0
k = 0 + 2
k = 1 + 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In "The Man in the High Castle" world, there are m different film endings. 

Abendsen owns a storage and a shelf. At first, he has n ordered films on the shelf. In the i-th month he will do:

  1. Empty the storage.
  2. Put k_i ⋅ m films into the storage, k_i films for each ending.
  3. He will think about a question: if he puts all the films from the shelf into the storage, then randomly picks n films (from all the films in the storage) and rearranges them on the shelf, what is the probability that sequence of endings in [l_i, r_i] on the shelf will not be changed? Notice, he just thinks about this question, so the shelf will not actually be changed.



Answer all Abendsen's questions.

Let the probability be fraction P_i. Let's say that the total number of ways to take n films from the storage for i-th month is A_i, so P_i ⋅ A_i is always an integer. Print for each month P_i ⋅ A_i \pmod {998244353}.

998244353 is a prime number and it is equal to 119 ⋅ 2^{23} + 1.

It is guaranteed that there will be only no more than 100 different k values.

Input

The first line contains three integers n, m, and q (1 ≤ n, m, q ≤ 10^5, n+q≤ 10^5) — the number of films on the shelf initially, the number of endings, and the number of months.

The second line contains n integers e_1, e_2, …, e_n (1≤ e_i≤ m) — the ending of the i-th film on the shelf.

Each of the next q lines contains three integers l_i, r_i, and k_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ k_i ≤ 10^5) — the i-th query.

It is guaranteed that there will be only no more than 100 different k values.

Output

Print the answer for each question in a separate line.

Examples

Input

6 4 4
1 2 3 4 4 4
1 4 0
1 3 2
1 4 2
1 5 2


Output

6
26730
12150
4860


Input

5 5 3
1 2 3 4 5
1 2 100000
1 4 4
3 5 5


Output

494942218
13125
151632

Note

In the first sample in the second query, after adding 2 ⋅ m films into the storage, the storage will look like this: \{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4\}.

There are 26730 total ways of choosing the films so that e_l, e_{l+1}, …, e_r will not be changed, for example, [1, 2, 3, 2, 2] and [1, 2, 3, 4, 3] are such ways.

There are 2162160 total ways of choosing the films, so you're asked to print (26730/2162160 ⋅ 2162160) mod 998244353 = 26730.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Below we will define what and n-interesting polygon is and your task is to find its area for a given n.

 A 1-interesting polygon is just a square with a side of length 1. An n-interesting polygon is obtained by taking the n - 1-interesting polygon and appending 1-interesting polygons to its rim side by side. You can see the 1-, 2- and 3-interesting polygons in the picture below.

 ![](https://files.gitter.im/myjinxin2015/Gwsw/blob)

# Example

 For `n = 1`, the output should be `1`;
 
 For `n = 2`, the output should be `5`;
 
 For `n = 3`, the output should be `13`.

# Input/Output


 - `[input]` integer `n`

    Constraints: `1 ≤ n < 10000.`
    

 - `[output]` an integer

   The area of the n-interesting polygon.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two numbers A and B along with an integer X. In one operation you can do one of the following:
Set A = A + X and B = B - X
Set A = A - X and B = B + X

Determine if you can make A and B equal after applying the operation any number of times (possibly zero).

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers A, B and X — the parameters mentioned in the statement.

------ Output Format ------ 

For each test case, output YES if you can make A and B equal after applying the operation any number of times (possibly zero). Otherwise, output NO.

You can output each letter in any case i.e. YES, yes, yEs are all considered the same.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ A, B, X ≤ 10^{9}$

----- Sample Input 1 ------ 
4
5 7 1
3 4 2
4 4 6
2 5 3

----- Sample Output 1 ------ 
YES
NO
YES
NO

----- explanation 1 ------ 
Test Case 1: The initial values of $(A, B)$ is $(5, 7)$. We can perform the following operation: $(5,7) \xrightarrow{A = A + X, B = B - X} (6,6)$.

Test Case 2: It can be proven that we can not make $A$ equal to $B$ using the given operations.

Test Case 3: $A$ and $B$ are already equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers N \ ( N ≥ 2) and S. You have to construct an array A containing N integers such that:
0 ≤ A_{i} ≤ S for each 1 ≤ i ≤ N
A_{1} + A_{2} + \ldots + A_{N} = S
A_{1} \mathbin{\&} A_{2} \mathbin{\&} \ldots \mathbin{\&} A_{N} = 0, where \mathbin{\&} denotes [bitwise AND] operator.
The maximum element of the array is minimized.

Find the maximum element of the array A.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and S — the length of array and sum of array elements respectively.

------ Output Format ------ 

For each test case, output on a new line the maximum element of the array A.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{9}$
$1 ≤ S ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2 7
3 6
5 21
100 256455

----- Sample Output 1 ------ 
4
3
5
2570

----- explanation 1 ------ 
Test case $1$: One possible array is $A = [4,3]$. Here $4 +3=7$ and $4 \mathbin{\&} 3=0$. 

Test case $2$: One possible array is $[1, 2, 3]$. Here $1+2+3=6$ and $1 \mathbin{\&} 2 \mathbin{\&} 3=0$. 

Test case $3$: One possible array is $[2, 4, 5,5,5]$. Here $2+4+5+5+5=21$ and $2 \mathbin{\&} 4 \mathbin{\&} 5 \mathbin{\&} 5 \mathbin{\&} 5=0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Efim just received his grade for the last test. He studies in a special school and his grade can be equal to any positive decimal fraction. First he got disappointed, as he expected a way more pleasant result. Then, he developed a tricky plan. Each second, he can ask his teacher to round the grade at any place after the decimal point (also, he can ask to round to the nearest integer). 

There are t seconds left till the end of the break, so Efim has to act fast. Help him find what is the maximum grade he can get in no more than t seconds. Note, that he can choose to not use all t seconds. Moreover, he can even choose to not round the grade at all.

In this problem, classic rounding rules are used: while rounding number to the n-th digit one has to take a look at the digit n + 1. If it is less than 5 than the n-th digit remain unchanged while all subsequent digits are replaced with 0. Otherwise, if the n + 1 digit is greater or equal to 5, the digit at the position n is increased by 1 (this might also change some other digits, if this one was equal to 9) and all subsequent digits are replaced with 0. At the end, all trailing zeroes are thrown away.

For example, if the number 1.14 is rounded to the first decimal place, the result is 1.1, while if we round 1.5 to the nearest integer, the result is 2. Rounding number 1.299996121 in the fifth decimal place will result in number 1.3.


-----Input-----

The first line of the input contains two integers n and t (1 ≤ n ≤ 200 000, 1 ≤ t ≤ 10^9) — the length of Efim's grade and the number of seconds till the end of the break respectively.

The second line contains the grade itself. It's guaranteed that the grade is a positive number, containing at least one digit after the decimal points, and it's representation doesn't finish with 0.


-----Output-----

Print the maximum grade that Efim can get in t seconds. Do not print trailing zeroes.


-----Examples-----
Input
6 1
10.245

Output
10.25

Input
6 2
10.245

Output
10.3

Input
3 100
9.2

Output
9.2



-----Note-----

In the first two samples Efim initially has grade 10.245. 

During the first second Efim can obtain grade 10.25, and then 10.3 during the next second. Note, that the answer 10.30 will be considered incorrect.

In the third sample the optimal strategy is to not perform any rounding at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a grid with N rows and M columns of squares. Each integer from 1 to NM is written in this grid once. The number written in the square at the i-th row from the top and the j-th column from the left is A_{ij}.

You need to rearrange these numbers as follows:

1. First, for each of the N rows, rearrange the numbers written in it as you like.
2. Second, for each of the M columns, rearrange the numbers written in it as you like.
3. Finally, for each of the N rows, rearrange the numbers written in it as you like.



After rearranging the numbers, you want the number written in the square at the i-th row from the top and the j-th column from the left to be M\times (i-1)+j. Construct one such way to rearrange the numbers. The constraints guarantee that it is always possible to achieve the objective.

Constraints

* 1 \leq N,M \leq 100
* 1 \leq A_{ij} \leq NM
* A_{ij} are distinct.

Input

Input is given from Standard Input in the following format:


N M
A_{11} A_{12} ... A_{1M}
:
A_{N1} A_{N2} ... A_{NM}


Output

Print one way to rearrange the numbers in the following format:


B_{11} B_{12} ... B_{1M}
:
B_{N1} B_{N2} ... B_{NM}
C_{11} C_{12} ... C_{1M}
:
C_{N1} C_{N2} ... C_{NM}


Here B_{ij} is the number written in the square at the i-th row from the top and the j-th column from the left after Step 1, and C_{ij} is the number written in that square after Step 2.

Examples

Input

3 2
2 6
4 3
1 5


Output

2 6
4 3
5 1
2 1
4 3
5 6


Input

3 4
1 4 7 10
2 5 8 11
3 6 9 12


Output

1 4 7 10
5 8 11 2
9 12 3 6
1 4 3 2
5 8 7 6
9 12 11 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Square Town, where many people who love squares live, a festival is held to color the town with illuminations that combine square lightning boards. This electric board emits light when electricity is applied, and the plate in contact with the light emitting plate also emits light. Therefore, no matter how many electric boards you use, if all of them are in contact with each other, you only need one power supply.

The festival executive committee will solicit designs that combine squares from the townspeople and create a large number of illuminations. For each illumination, the number of power supplies required varies depending on the arrangement of the squares that make up the design, so it takes a lot of time and effort to figure out the number of power supplies required. So you decided to look at the arrangement of the rectangles and write a program to help the executive committee calculate the number of power supplies needed.


<image>


Create a program that inputs the number of illuminations and the information of the rectangles that make up each illumination, and outputs the number of power supplies required for each illumination. Think of the overlapping and touching rectangles as a group, and count the number of power supplies as one for each group.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


N
M1
xa1 ya1 xb1 yb1 xc1 yc1 xd1 yd1
xa2 ya2 xb2 yb2 xc2 yc2 xd2 yd2
::
xaM1 yaM1 xbM1 ybM1 xcM1 ycM1 xdM1 ydM1
M2
::
::
MN
::
::


The number of illuminations N (1 ≤ N ≤ 100) is given on the first line. Then, information on N illuminations is given. As the i-th illumination information, the number of rectangles Mi (1 ≤ Mi ≤ 100) that make up the illumination is given in one line. The following Mi line is given the jth quadrangle vertex xaj, yaj, xbj, ybj, xcj, ycj, xdj, ydj (integer between -1000 and 1000).

The coordinates of the vertices of the rectangle entered are entered in a clockwise order. However, all the input data rectangles are convex rectangles.

The number of datasets does not exceed 10.

Output

Outputs the number of power supplies required for each illumination for each input dataset. Follow the order in which each illumination was input for the number of power supplies to be output.

Example

Input

3
1
0 0 0 1 1 1 1 0
2
0 0 0 1 1 1 1 0
100 100 100 200 200 200 200 100
2
0 0 0 100 100 100 100 0
10 10 10 20 20 20 20 10
2
1
30 40 40 50 40 20 20 10
1
30 40 40 50 40 20 20 10
0


Output

1
2
1
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To defeat Lord Voldemort, Harry needs to destroy all horcruxes first. The last horcrux is an array a of n integers, which also needs to be destroyed. The array is considered destroyed if all its elements are zeroes. To destroy the array, Harry can perform two types of operations:

  1. choose an index i (1 ≤ i ≤ n), an integer x, and subtract x from a_i.
  2. choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), an integer x, and subtract x from a_i and x + 1 from a_j. 



Note that x does not have to be positive.

<image>

Harry is in a hurry, please help him to find the minimum number of operations required to destroy the array and exterminate Lord Voldemort.

Input

The first line contains a single integer n — the size of the array a (1 ≤ n ≤ 20). 

The following line contains n integers a_1, a_2, …, a_n — array elements (-10^{15} ≤ a_i ≤ 10^{15}).

Output

Output a single integer — the minimum number of operations required to destroy the array a.

Examples

Input


3
1 10 100


Output


3


Input


3
5 3 -2


Output


2


Input


1
0


Output


0

Note

In the first example one can just apply the operation of the first kind three times.

In the second example, one can apply the operation of the second kind two times: first, choose i = 2, j = 1, x = 4, it transforms the array into (0, -1, -2), and then choose i = 3, j = 2, x = -2 to destroy the array.

In the third example, there is nothing to be done, since the array is already destroyed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Balls and Boxes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Vasya had *n* boxes with balls in the room. The boxes stood in a row and were numbered with numbers from 1 to *n* from left to right.

Once Vasya chose one of the boxes, let's assume that its number is *i*, took all balls out from it (it is guaranteed that this box originally had at least one ball), and began putting balls (one at a time) to the boxes with numbers *i*<=+<=1, *i*<=+<=2, *i*<=+<=3 and so on. If Vasya puts a ball into the box number *n*, then the next ball goes to box 1, the next one goes to box 2 and so on. He did it until he had no balls left in his hands. It is possible that Vasya puts multiple balls to the same box, and it is also possible that one or more balls will go to the box number *i*. If *i*<==<=*n*, Vasya puts the first ball into the box number 1, then the next ball goes to box 2 and so on. 

For example, let's suppose that initially Vasya had four boxes, and the first box had 3 balls, the second one had 2, the third one had 5 and the fourth one had 4 balls. Then, if *i*<==<=3, then Vasya will take all five balls out of the third box and put them in the boxes with numbers: 4,<=1,<=2,<=3,<=4. After all Vasya's actions the balls will lie in the boxes as follows: in the first box there are 4 balls, 3 in the second one, 1 in the third one and 6 in the fourth one.

At this point Vasya has completely forgotten the original arrangement of the balls in the boxes, but he knows how they are arranged now, and the number *x* — the number of the box, where he put the last of the taken out balls.

He asks you to help to find the initial arrangement of the balls in the boxes.

Input Specification:
The first line of the input contains two integers *n* and *x* (2<=≤<=*n*<=≤<=105, 1<=≤<=*x*<=≤<=*n*), that represent the number of the boxes and the index of the box that got the last ball from Vasya, correspondingly. The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n*, where integer *a**i* (0<=≤<=*a**i*<=≤<=109, *a**x*<=≠<=0) represents the number of balls in the box with index *i* after Vasya completes all the actions. 

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output Specification:
Print *n* integers, where the *i*-th one represents the number of balls in the box number *i* before Vasya starts acting. Separate the numbers in the output by spaces. If there are multiple correct solutions, you are allowed to print any of them.

Demo Input:
['4 4\n4 3 1 6\n', '5 2\n3 2 0 2 7\n', '3 3\n2 3 1\n']

Demo Output:
['3 2 5 4 ', '2 1 4 1 6 ', '1 2 3 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rasta calls a number like a Tavas if and only if 1 ≤ a ≤ n and the sum of all primes (like p) that p | a is exactly equal to k.

He asks you to find the number of Tavases.

Input format
The first and only line of input contains two integers, n and k (1 ≤ n, k ≤ 10^6).

Output format
Print a single integer, the number of Tavases.

SAMPLE INPUT
20 7

SAMPLE OUTPUT
3

Explanation

The only Tavases are 7, 10 and 20.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Calvin the robot lies in an infinite rectangular grid. Calvin's source code contains a list of *n* commands, each either 'U', 'R', 'D', or 'L' — instructions to move a single square up, right, down, or left, respectively. How many ways can Calvin execute a non-empty contiguous substrings of commands and return to the same square he starts in? Two substrings are considered different if they have different starting or ending indices.

Input Specification:
The first line of the input contains a single positive integer, *n* (1<=≤<=*n*<=≤<=200) — the number of commands.

The next line contains *n* characters, each either 'U', 'R', 'D', or 'L' — Calvin's source code.

Output Specification:
Print a single integer — the number of contiguous substrings that Calvin can execute and return to his starting square.

Demo Input:
['6\nURLLDR\n', '4\nDLUU\n', '7\nRLRLRLR\n']

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

Note:
In the first case, the entire source code works, as well as the "RL" substring in the second and third characters.

Note that, in the third case, the substring "LR" appears three times, and is therefore counted three times to the total result.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The new £5 notes have been recently released in the UK and they've certainly became a sensation! Even those of us who haven't been carrying any cash around for a while, having given in to the convenience of cards, suddenly like to have some of these in their purses and pockets. But how many of them could you get with what's left from your salary after paying all bills? The programme that you're about to write will count this for you!

Given a salary and the array of bills, calculate your disposable income for a month and return it as a number of new £5 notes you can get with that amount. If the money you've got (or do not!) doesn't allow you to get any £5 notes return 0.

£££ GOOD LUCK! £££

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

Write a function that takes two hex strings as input and XORs them against each other. If the strings are different lengths the output should be the length of the shortest string.

Hint: The strings would first need to be converted to binary to be XOR'd. 

## Note:
If the two strings are of different lengths, the output string should be the same length as the smallest string. This means that the longer string will be cut down to the same size as the smaller string, then xor'd

### Further help

More information on the XOR operation can be found here https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-bitwise-operation

More information of the binary and hex bases can be found here https://www.khanacademy.org/math/algebra-home/alg-intro-to-algebra/algebra-alternate-number-bases/v/number-systems-introduction

Examples:

```python
fixed_xor("ab3f", "ac") == "07"
fixed_xor("aadf", "bce2") == "163d"
fixed_xor("1c0111001f010100061a024b53535009181c", "686974207468652062756c6c277320657965") == "746865206b696420646f6e277420706c6179"
```

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