vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array nums of integers, return how many of them contain an even number of digits.
 
Example 1:
Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:
Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

 
Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a big staircase with $N$ steps (numbered $1$ through $N$) in ChefLand. Let's denote the height of the top of step $i$ by $h_i$. Chef Ada is currently under the staircase at height $0$ and she wants to reach the top of the staircase (the top of the last step). However, she can only jump from height $h_i$ to the top of a step at height $h_f$ if $h_f-h_i \le K$. To help Ada, we are going to construct some intermediate steps; each of them may be constructed between any two steps, or before the first step, and have any height. What is the minimum number of steps that need to be added to the staircase so that Ada could reach the top?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-seperated integers $h_1, h_2, \dots, h_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of steps.

-----Constraints-----
- $1 \le T \le 64$
- $1 \le N \le 128$
- $1 \le K \le 1,024$
- $1 \le h_i \le 1,024$ for each valid $i$
- $h_i < h_{i+1}$ for each valid $i$

-----Example Input-----
1
4 3
2 4 8 16

-----Example Output-----
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are M males and F females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure F times, there are no females left in the circle.
Given M, F and K, your task is to print what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.

Input - First line consist of no. of test cases and each test case contains M,F,K.

Output - Print the string representing the initial arrangement.

SAMPLE INPUT
3
5 3 2
1 0 245
5 5 3

SAMPLE OUTPUT
MFMFMFMM
M
MFFMMFFMFM

Explanation

TC #1 - On the first round you remove the second person - M_MFMFMM. Your new circle looks like MFMFMMM from your new starting point. Then you remove the second person again etc.

TC #3 - 
Here we mark the removed people with '_', and the starting position with lower-case:
Number of  Rounds | People Remaining in initial order)
---+------------------------------
 0             | mFFMMFFMFM
 1             | MF_mMFFMFM
 2             | MF_MM_fMFM
 3             | MF_MM_FM_m
 4             | M__mM_FM_M
 5             | M__MM__m_M

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are storing an integer array of length m in a database. To maintain internal integrity and protect data, the database stores n copies of this array.

Unfortunately, the recent incident may have altered the stored information in every copy in the database.

It's believed, that the incident altered at most two elements in every copy. You need to recover the original array based on the current state of the database.

In case there are multiple ways to restore the array, report any. If there is no array that differs from every copy in no more than two positions, report that as well.

Input

The first line contains integers n and m (2 ≤ n; 1 ≤ m; n ⋅ m ≤ 250 000) — the number of copies and the size of the array.

Each of the following n lines describes one of the currently stored copies in the database, it consists of m integers s_{i, 1}, s_{i, 2}, ..., s_{i, m} (1 ≤ s_{i, j} ≤ 10^9).

Output

If there is an array consistent with all given copies, print "Yes" and then the array itself. The array must have length m and contain integers between 1 and 10^9 only.

Otherwise, print "No".

If there are multiple possible arrays, print any of them.

Examples

Input


3 4
1 10 10 100
1 1 1 100
10 100 1 100


Output


Yes
1 10 1 100


Input


10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1


Output


Yes
1 1 1 1 1 1 1


Input


2 5
2 2 1 1 1
1 1 2 2 2


Output


No

Note

In the first example, the array [1, 10, 1, 100] differs from first and second copies in just one position, and from the third copy in two positions.

In the second example, array [1, 1, 1, 1, 1, 1, 1] is the same as the first copy and differs from all other copies in at most two positions.

In the third example, there is no array differing in at most two positions from every database's copy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ford Prefect got a job as a web developer for a small company that makes towels. His current work task is to create a search engine for the website of the company. During the development process, he needs to write a subroutine for comparing strings S and T of equal length to be "similar". After a brief search on the Internet, he learned about the Hamming distance between two strings S and T of the same length, which is defined as the number of positions in which S and T have different characters. For example, the Hamming distance between words "permanent" and "pergament" is two, as these words differ in the fourth and sixth letters.

Moreover, as he was searching for information, he also noticed that modern search engines have powerful mechanisms to correct errors in the request to improve the quality of search. Ford doesn't know much about human beings, so he assumed that the most common mistake in a request is swapping two arbitrary letters of the string (not necessarily adjacent). Now he wants to write a function that determines which two letters should be swapped in string S, so that the Hamming distance between a new string S and string T would be as small as possible, or otherwise, determine that such a replacement cannot reduce the distance between the strings.

Help him do this!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 200 000) — the length of strings S and T.

The second line contains string S.

The third line contains string T.

Each of the lines only contains lowercase Latin letters.


-----Output-----

In the first line, print number x — the minimum possible Hamming distance between strings S and T if you swap at most one pair of letters in S.

In the second line, either print the indexes i and j (1 ≤ i, j ≤ n, i ≠ j), if reaching the minimum possible distance is possible by swapping letters on positions i and j, or print "-1 -1", if it is not necessary to swap characters.

If there are multiple possible answers, print any of them.


-----Examples-----
Input
9
pergament
permanent

Output
1
4 6

Input
6
wookie
cookie

Output
1
-1 -1

Input
4
petr
egor

Output
2
1 2

Input
6
double
bundle

Output
2
4 1



-----Note-----

In the second test it is acceptable to print i = 2, j = 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You want to build a temple for snakes. The temple will be built on a mountain range, which can be thought of as n blocks, where height of i-th block is given by hi. The temple will be made on a consecutive section of the blocks and its height should start from 1 and increase by exactly 1 each time till some height and then decrease by exactly 1 each time to height 1, 
i.e. a consecutive section of 1, 2, 3, .. x-1, x, x-1, x-2, .., 1 can correspond to a temple. Also, heights of all the blocks other than of the temple should have zero height, so that the temple is visible to people who view it from the left side or right side.
You want to construct a temple. For that, you can reduce the heights of some of the blocks. In a single operation, you can reduce the height of a block by 1 unit. Find out minimum number of operations required to build a temple.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer n.
The next line contains n integers, where the i-th integer denotes hi

-----Output-----
For each test case, output a new line with an integer corresponding to the answer of that testcase.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 105
- 1 ≤ hi ≤ 109

-----Example-----
Input
3
3
1 2 1
4
1 1 2 1
5
1 2 6 2 1

Output
0
1
3

-----Explanation-----
Example 1. The entire mountain range is already a temple. So, there is no need to make any operation.
Example 2. If you reduce the height of the first block to 0. You get 0 1 2 1. The blocks 1, 2, 1 form a temple. So, the answer is 1.
Example 3. One possible temple can be 1 2 3 2 1. It requires 3 operations to build. This is the minimum amount you have to spend in order to build a temple.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence of integers a1, ..., an and q queries x1, ..., xq on it. For each query xi you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, ..., ar) = xi.

<image> is a greatest common divisor of v1, v2, ..., vn, that is equal to a largest positive integer that divides all vi.

Input

The first line of the input contains integer n, (1 ≤ n ≤ 105), denoting the length of the sequence. The next line contains n space separated integers a1, ..., an, (1 ≤ ai ≤ 109).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105), denoting the number of queries. Then follows q lines, each contain an integer xi, (1 ≤ xi ≤ 109).

Output

For each query print the result in a separate line.

Examples

Input

3
2 6 3
5
1
2
3
4
6


Output

1
2
2
0
1


Input

7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000


Output

14
0
2
2
2
0
2
2
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chandler has a list of non zero positive integers with him. He made a very interesting observation about the list. He noticed that the number of unique integers in an array of size $N$ is in the range $L$ to $R$ (both inclusive) and every element was either 1 or an even number x, in which case x/2 was also definitely present in the array. 
Chandler has misplaced the list of integers but he wants to impress Monica with his problem solving skills by finding out the minimum and maximum possible sum of all elements of the list of integers.
Can you also help him solve the problem so that he can win over Monica?

-----Input:-----
- First line will contain $T$, the number of testcases. 
- The first line of each test case contains integers $N$, $L$, and $R$. 

-----Output:-----
For each test case print 2 space-separated integers, the minimum and the maximum possible sum of N elements based on the above facts.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 1000$
- $1 \leq L \leq R \leq min(N,20)$

-----Sample Input:-----
2

4 2 2

5 1 5

-----Sample Output:-----
5 7

5 31

-----EXPLANATION:-----
- 
Example 1: For an array of size 4, with minimum 2 unique integers and maximum 2 unique integers, the possible arrays are (1,1,1,2), (1,1,2,2), (1,2,2,2)
Out of these, the minimum possible sum of elements is 5(1+1+1+2) and maximum possible sum is 7(1+2+2+2)
- 
Example 2: For an array of size 5, with minimum 1 unique integer and maximum 5 unique integers, minimum possible sum of elements is 5(1+1+1+1+1) and maximum possible sum is 31(1+2+4+8+16)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of non-negative integers $A_1, A_2, \ldots, A_N$. At most once, you may choose a non-negative integer $X$ and for each valid $i$, change $A_i$ to $A_i \oplus X$ ($\oplus$ denotes bitwise XOR).
Find the minimum possible value of the sum of all elements of the resulting sequence.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of the input contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum possible sum.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le N \le 10^3$
- $1 \le A_i \le 10^3$ for each valid $i$
Subtask #2 (50 points): original constraints

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

-----Example Output-----
14
0
2

-----Explanation-----
Example case 1: If we choose $X = 6$, the sequence becomes $(4, 5, 2, 3, 0)$.
Example case 2: We can choose $X = 7$ to make all elements of the resulting sequence equal to $0$.
Example case 3: We can choose $X = 1$. The sequence becomes $(0, 0, 2)$, with sum $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Game of the Rows

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Daenerys Targaryen has an army consisting of *k* groups of soldiers, the *i*-th group contains *a**i* soldiers. She wants to bring her army to the other side of the sea to get the Iron Throne. She has recently bought an airplane to carry her army through the sea. The airplane has *n* rows, each of them has 8 seats. We call two seats neighbor, if they are in the same row and in seats {1,<=2}, {3,<=4}, {4,<=5}, {5,<=6} or {7,<=8}.

Daenerys Targaryen wants to place her army in the plane so that there are no two soldiers from different groups sitting on neighboring seats.

Your task is to determine if there is a possible arranging of her army in the airplane such that the condition above is satisfied.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=10000, 1<=≤<=*k*<=≤<=100) — the number of rows and the number of groups of soldiers, respectively.

The second line contains *k* integers *a*1,<=*a*2,<=*a*3,<=...,<=*a**k* (1<=≤<=*a**i*<=≤<=10000), where *a**i* denotes the number of soldiers in the *i*-th group.

It is guaranteed that *a*1<=+<=*a*2<=+<=...<=+<=*a**k*<=≤<=8·*n*.

Output Specification:
If we can place the soldiers in the airplane print "YES" (without quotes). Otherwise print "NO" (without quotes).

You can choose the case (lower or upper) for each letter arbitrary.

Demo Input:
['2 2\n5 8\n', '1 2\n7 1\n', '1 2\n4 4\n', '1 4\n2 2 1 2\n']

Demo Output:
['YES\n', 'NO\n', 'YES\n', 'YES\n']

Note:
In the first sample, Daenerys can place the soldiers like in the figure below:

In the second sample, there is no way to place the soldiers in the plane since the second group soldier will always have a seat neighboring to someone from the first group.

In the third example Daenerys can place the first group on seats (1, 2, 7, 8), and the second group an all the remaining seats.

In the fourth example she can place the first two groups on seats (1, 2) and (7, 8), the third group on seats (3), and the fourth group on seats (5, 6).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers $a$ and $b$. In one move you can increase $a$ by $1$ (replace $a$ with $a+1$). Your task is to find the minimum number of moves you need to do in order to make $a$ divisible by $b$. It is possible, that you have to make $0$ moves, as $a$ is already divisible by $b$. You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).


-----Output-----

For each test case print the answer — the minimum number of moves you need to do in order to make $a$ divisible by $b$.


-----Example-----
Input
5
10 4
13 9
100 13
123 456
92 46

Output
2
5
4
333
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Hexadecimal virus loves playing with number sets — intersecting them, uniting them. One beautiful day she was surprised to find out that Scuzzy, her spherical pet cat, united all sets in one and ate the result! Something had to be done quickly and Hexadecimal rushed to the market.

The market has n sets of numbers on sale. The virus wants to buy the following collection of sets: the number of sets in the collection should be exactly the same as the number of numbers in the union of all bought sets. Moreover, Hexadecimal wants to buy the cheapest suitable collection of set.

Yet nothing's so easy! As Mainframe is a kingdom of pure rivalry markets, we know that the union of any k sets contains no less than k distinct numbers (for every positive integer k).

Help the virus choose the suitable collection of sets. The collection can be empty.

Input

The first line contains the only number n (1 ≤ n ≤ 300) — the number of sets available in the market.

Next n lines describe the goods: first we are given mi (1 ≤ mi ≤ n) — the number of distinct numbers in the i-th set, then follow mi numbers — the set's elements. We know that the set's elements are distinct positive integers and they do not exceed n.

The last line contains n integers whose absolute values do not exceed 106 — the price of each set.

Output

Print a single number — the minimum price the virus will have to pay for such a collection of k sets that union of the collection's sets would have exactly k distinct numbers (<image>).

Examples

Input

3
1 1
2 2 3
1 3
10 20 -3


Output

-3


Input

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1


Output

0


Input

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1


Output

-1

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

Find the mean (average) of a list of numbers in an array.

## Information

To find the mean (average) of a set of numbers add all of the numbers together and divide by the number of values in the list.

For an example list of `1, 3, 5, 7`

1. Add all of the numbers

```
1+3+5+7 = 16
```

2. Divide by the number of values in the list. In this example there are 4 numbers in the list.

```
16/4 = 4
```

3. The mean (or average) of this list is 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is a competitive programmer. He wants to become red, and for that he needs a strict training regime. He went to the annual meeting of grandmasters and asked $n$ of them how much effort they needed to reach red.

"Oh, I just spent $x_i$ hours solving problems", said the $i$-th of them. 

Bob wants to train his math skills, so for each answer he wrote down the number of minutes ($60 \cdot x_i$), thanked the grandmasters and went home. Bob could write numbers with leading zeroes — for example, if some grandmaster answered that he had spent $2$ hours, Bob could write $000120$ instead of $120$.

Alice wanted to tease Bob and so she took the numbers Bob wrote down, and for each of them she did one of the following independently:   rearranged its digits, or  wrote a random number. 

This way, Alice generated $n$ numbers, denoted $y_1$, ..., $y_n$.

For each of the numbers, help Bob determine whether $y_i$ can be a permutation of a number divisible by $60$ (possibly with leading zeroes).


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 418$) — the number of grandmasters Bob asked.

Then $n$ lines follow, the $i$-th of which contains a single integer $y_i$ — the number that Alice wrote down.

Each of these numbers has between $2$ and $100$ digits '0' through '9'. They can contain leading zeroes.


-----Output-----

Output $n$ lines.

For each $i$, output the following. If it is possible to rearrange the digits of $y_i$ such that the resulting number is divisible by $60$, output "red" (quotes for clarity). Otherwise, output "cyan".


-----Example-----
Input
6
603
006
205
228
1053
0000000000000000000000000000000000000000000000

Output
red
red
cyan
cyan
cyan
red



-----Note-----

In the first example, there is one rearrangement that yields a number divisible by $60$, and that is $360$.

In the second example, there are two solutions. One is $060$ and the second is $600$.

In the third example, there are $6$ possible rearrangments: $025$, $052$, $205$, $250$, $502$, $520$. None of these numbers is divisible by $60$.

In the fourth example, there are $3$ rearrangements: $228$, $282$, $822$.

In the fifth example, none of the $24$ rearrangements result in a number divisible by $60$.

In the sixth example, note that $000\dots0$ is a valid solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a regular table tennis match, the player who serves changes every time after 2 points are scored, regardless of which players scored them.
Chef and Cook are playing a different match — they decided that the player who serves would change every time after $K$ points are scored instead (again regardless of which players scored them). When the game starts, it's Chef's turn to serve.
You are given the current number of points scored by Chef and Cook ($P_1$ and $P_2$ respectively). Find out whether Chef or Cook has to serve next.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains three space-separated integers $P_1$, $P_2$ and $K$.

-----Output-----
For each test case, print a single line containing the string "CHEF" if it is Chef's turn or "COOK" if it is Cook's turn.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le K \le 10^{9}$
- $0 \le P_1, P_2 \le 10^{9}$ 

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
1 3 2
0 3 2
34 55 2

-----Example Output-----
CHEF
COOK
CHEF

-----Explanation-----
Example case 1: Chef serves for the first two points, Cook serves for the next two, so Chef has to serve again now.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N children, numbered 1,2,\ldots,N. In the next K days, we will give them some cookies. In the i-th day, we will choose a_i children among the N with equal probability, and give one cookie to each child chosen. (We make these K choices independently.)

Let us define the happiness of the children as c_1 \times c_2 \times \ldots \times c_N, where c_i is the number of cookies received by Child i in the K days. Find the expected happiness multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (we can show that this value is an integer), modulo (10^{9}+7).

Constraints

* 1 \leq N \leq 1000
* 1 \leq K \leq 20
* 1 \leq a_i \leq N

Input

Input is given from Standard Input in the following format:


N K
a_1 a_2 \ldots a_K


Output

Print the answer.

Examples

Input

3 2
3 2


Output

12


Input

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63


Output

337587117

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