vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A circular array of length N is defined as follows: N integers A_{1},A_{2},…,A_{N} are placed in a circle in such a way that for each 1 ≤ i < N, A_{i} and A_{i+1} are adjacent, and A_{1} and A_{N} are also adjacent.

You are given a circular array A of length N. At the end of each second, the following changes are executed in the array: If A_{i} > 0 then the elements which are adjacent to A_{i}, will get incremented by 1, for all 1 ≤ i ≤ N.

For example, consider the array A = [0, 0, 0, 2, 0, 0, 0, 5]. 
Initially A_{4} and A_{8} are greater than zero. So after one second, A_{3}, A_{5}, A_{1} and A_{7} will get incremented by 1. Hence the array will become A = [1, 0, 1, 2, 1, 0, 1, 5].

After two seconds, the array becomes A = [2, 2, 2, 4, 2, 2, 2, 7]. Note that the value of A_{4} has become 4, because both, A_{3} and A_{5} were greater than zero after one second.

What will be the sum of elements present in the array A after K seconds?

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

- The first line will contain T, number of testcases. Then T testcases follow.
- The first line of each testcase contains 2 space separated integers N and K.
- The second line of each testcase line contains N integers A_{1}, A_{2}, \dots, A_{N}. 

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

For each testcase, output in a single line containing the sum of the all the elements present in the array A after K seconds.

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

$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{6}$
$0 ≤ K ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
4
6 1
0 1 0 1 0 0
3 0
0 1 2
8 2
0 0 0 2 0 0 0 5
3 10
1 2 3
----- Sample Output 1 ------ 
6
3
23
66
----- explanation 1 ------ 
Test Case 1: After one second, the array will become $A = [1, 1, 2, 1, 1, 0]$. So the sum of elements present in the array is = $1 + 1 + 2 + 1 + 1 + 0 = 6$.

Test Case 2: No change will be executed in the array as $K = 0$. So the required sum will be equal to 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let a be a matrix of size r × c containing positive integers, not necessarily distinct. Rows of the matrix are numbered from 1 to r, columns are numbered from 1 to c. We can construct an array b consisting of r + c integers as follows: for each i ∈ [1, r], let b_i be the greatest common divisor of integers in the i-th row, and for each j ∈ [1, c] let b_{r+j} be the greatest common divisor of integers in the j-th column. 

We call the matrix diverse if all r + c numbers b_k (k ∈ [1, r + c]) are pairwise distinct. 

The magnitude of a matrix equals to the maximum of b_k.

For example, suppose we have the following matrix:

\begin{pmatrix} 2 & 9 & 7\\\ 4 & 144 & 84 \end{pmatrix} 

We construct the array b:

  1. b_1 is the greatest common divisor of 2, 9, and 7, that is 1; 
  2. b_2 is the greatest common divisor of 4, 144, and 84, that is 4; 
  3. b_3 is the greatest common divisor of 2 and 4, that is 2; 
  4. b_4 is the greatest common divisor of 9 and 144, that is 9; 
  5. b_5 is the greatest common divisor of 7 and 84, that is 7. 



So b = [1, 4, 2, 9, 7]. All values in this array are distinct, so the matrix is diverse. The magnitude is equal to 9.

For a given r and c, find a diverse matrix that minimises the magnitude. If there are multiple solutions, you may output any of them. If there are no solutions, output a single integer 0. 

Input

The only line in the input contains two space separated integers r and c (1 ≤ r,c ≤ 500) — the number of rows and the number of columns of the matrix to be found.

Output

If there is no solution, output a single integer 0.

Otherwise, output r rows. The i-th of them should contain c space-separated integers, the j-th of which is a_{i,j} — the positive integer in the i-th row and j-th column of a diverse matrix minimizing the magnitude.

Furthermore, it must hold that 1 ≤ a_{i,j} ≤ 10^9. It can be shown that if a solution exists, there is also a solution with this additional constraint (still having minimum possible magnitude).

Examples

Input


2 2


Output


4 12
2 9

Input


1 1


Output


0

Note

In the first example, the GCDs of rows are b_1 = 4 and b_2 = 1, and the GCDs of columns are b_3 = 2 and b_4 = 3. All GCDs are pairwise distinct and the maximum of them is 4. Since the GCDs have to be distinct and at least 1, it is clear that there are no diverse matrices of size 2 × 2 with magnitude smaller than 4.

In the second example, no matter what a_{1,1} is, b_1 = b_2 will always hold, so there are no diverse matrices.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N positive integers a_1, a_2, ..., a_N.
For a non-negative integer m, let f(m) = (m\ mod\ a_1) + (m\ mod\ a_2) + ... + (m\ mod\ a_N).
Here, X\ mod\ Y denotes the remainder of the division of X by Y.
Find the maximum value of f.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 3000
 - 2 \leq a_i \leq 10^5

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

-----Output-----
Print the maximum value of f.

-----Sample Input-----
3
3 4 6

-----Sample Output-----
10

f(11) = (11\ mod\ 3) + (11\ mod\ 4) + (11\ mod\ 6) = 10 is the maximum value of f.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Harry Potter is on a mission to destroy You-Know-Who's Horcruxes. The first Horcrux that he encountered in the Chamber of Secrets is Tom Riddle's diary. The diary was with Ginny and it forced her to open the Chamber of Secrets. Harry wants to know the different people who had ever possessed the diary to make sure they are not under its influence.

He has names of n people who possessed the diary in order. You need to tell, for each person, if he/she possessed the diary at some point before or not.

Formally, for a name s_{i} in the i-th line, output "YES" (without quotes) if there exists an index j such that s_{i} = s_{j} and j < i, otherwise, output "NO" (without quotes).


-----Input-----

First line of input contains an integer n (1 ≤ n ≤ 100) — the number of names in the list.

Next n lines each contain a string s_{i}, consisting of lowercase English letters. The length of each string is between 1 and 100.


-----Output-----

Output n lines each containing either "YES" or "NO" (without quotes), depending on whether this string was already present in the stream or not.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
6
tom
lucius
ginny
harry
ginny
harry

Output
NO
NO
NO
NO
YES
YES

Input
3
a
a
a

Output
NO
YES
YES



-----Note-----

In test case 1, for i = 5 there exists j = 3 such that s_{i} = s_{j} and j < i, which means that answer for i = 5 is "YES".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to obtain 2 numbers $($ $A$ $and$ $B$ $)$ and an arithmetic operator $(C)$ and then design a $calculator$ depending upon the operator entered by the user.
So for example if C="+", you have to sum the two numbers.
If C="-", you have to subtract the two numbers.
If C=" * ", you have to print the product.
If C=" / ", you have to divide the two numbers.

-----Input:-----
- First line will contain the first number $A$.
- Second line will contain the second number $B$.
- Third line will contain the operator $C$, that is to be performed on A and B.

-----Output:-----
Output a single line containing the answer, obtained by, performing the operator on the numbers. Your output will be considered to be correct if the difference between your output and the actual answer is not more than $10^{-6}$.

-----Constraints-----
- $-1000 \leq A \leq 1000$
- $-1000 \leq B \leq 1000$ $and$ $B \neq 0$
- $C$ $can$ $only$ $be$ $one$ $of$ $these$ $4$ $operators$ {" + ", " - ", " * ", " / "}

-----Sample Input:-----
8
2
/

-----Sample Output:-----
4.0

-----Sample Input:-----
5
3
+

-----Sample Output:-----
8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has $n$ hotels, where the $i$-th hotel is located in the city with coordinate $x_i$. Sonya is a smart girl, so she does not open two or more hotels in the same city.

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to $d$. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel. 

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original $n$ hotels to the new one is equal to $d$.

Input Specification:
The first line contains two integers $n$ and $d$ ($1\leq n\leq 100$, $1\leq d\leq 10^9$) — the number of Sonya's hotels and the needed minimum distance from a new hotel to all others.

The second line contains $n$ different integers in strictly increasing order $x_1, x_2, \ldots, x_n$ ($-10^9\leq x_i\leq 10^9$) — coordinates of Sonya's hotels.

Output Specification:
Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to $d$.

Demo Input:
['4 3\n-3 2 9 16\n', '5 2\n4 8 11 18 19\n']

Demo Output:
['6\n', '5\n']

Note:
In the first example, there are $6$ possible cities where Sonya can build a hotel. These cities have coordinates $-6$, $5$, $6$, $12$, $13$, and $19$.

In the second example, there are $5$ possible cities where Sonya can build a hotel. These cities have coordinates $2$, $6$, $13$, $16$, and $21$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integer numbers, $n$ and $x$. You may perform several operations with the integer $x$.

Each operation you perform is the following one: choose any digit $y$ that occurs in the decimal representation of $x$ at least once, and replace $x$ by $x \cdot y$.

You want to make the length of decimal representation of $x$ (without leading zeroes) equal to $n$. What is the minimum number of operations required to do that?


-----Input-----

The only line of the input contains two integers $n$ and $x$ ($2 \le n \le 19$; $1 \le x < 10^{n-1}$).


-----Output-----

Print one integer — the minimum number of operations required to make the length of decimal representation of $x$ (without leading zeroes) equal to $n$, or $-1$ if it is impossible.


-----Examples-----

Input
2 1
Output
-1
Input
3 2
Output
4
Input
13 42
Output
12


-----Note-----

In the second example, the following sequence of operations achieves the goal:

multiply $x$ by $2$, so $x = 2 \cdot 2 = 4$;

multiply $x$ by $4$, so $x = 4 \cdot 4 = 16$;

multiply $x$ by $6$, so $x = 16 \cdot 6 = 96$;

multiply $x$ by $9$, so $x = 96 \cdot 9 = 864$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Toad Rash has a binary string $s$. A binary string consists only of zeros and ones.

Let $n$ be the length of $s$.

Rash needs to find the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x < x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.

Find this number of pairs for Rash.


-----Input-----

The first line contains the string $s$ ($1 \leq |s| \leq 300\,000$), consisting of zeros and ones.


-----Output-----

Output one integer: the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x < x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.


-----Examples-----
Input
010101

Output
3

Input
11001100

Output
0



-----Note-----

In the first example, there are three $l$, $r$ pairs we need to count: $1$, $6$; $2$, $6$; and $1$, $5$.

In the second example, there are no values $x$, $k$ for the initial string, so the answer is $0$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
"The Chamber of Secrets has been opened again" — this news has spread all around Hogwarts and some of the students have been petrified due to seeing the basilisk. Dumbledore got fired and now Harry is trying to enter the Chamber of Secrets. These aren't good news for Lord Voldemort. The problem is, he doesn't want anybody to be able to enter the chamber. The Dark Lord is going to be busy sucking life out of Ginny.

The Chamber of Secrets is an *n*<=×<=*m* rectangular grid in which some of the cells are columns. A light ray (and a basilisk's gaze) passes through the columns without changing its direction. But with some spell we can make a column magic to reflect the light ray (or the gaze) in all four directions when it receives the ray. This is shown in the figure below.

The basilisk is located at the right side of the lower right cell of the grid and is looking to the left (in the direction of the lower left cell). According to the legend, anyone who meets a basilisk's gaze directly dies immediately. But if someone meets a basilisk's gaze through a column, this person will get petrified. We know that the door to the Chamber is located on the left side of the upper left corner of the grid and anyone who wants to enter will look in the direction of its movement (in the direction of the upper right cell) from that position.

Given the dimensions of the chamber and the location of regular columns, Lord Voldemort has asked you to find the minimum number of columns that we need to make magic so that anyone who wants to enter the chamber would be petrified or just declare that it's impossible to secure the chamber.

Input Specification:
The first line of the input contains two integer numbers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=1000). Each of the next *n* lines contains *m* characters. Each character is either "." or "#" and represents one cell of the Chamber grid. It's "." if the corresponding cell is empty and "#" if it's a regular column.

Output Specification:
Print the minimum number of columns to make magic or -1 if it's impossible to do.

Demo Input:
['3 3\n.#.\n...\n.#.\n', '4 3\n##.\n...\n.#.\n.#.\n']

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

Note:
The figure above shows the first sample test. In the first sample we should make both columns magic. The dragon figure represents the basilisk and the binoculars represent the person who will enter the Chamber of secrets. The black star shows the place where the person will be petrified. Yellow lines represent basilisk gaze moving through columns.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a polynom in form p(x) = (x + a1)·(x + a2)·... (x + an). Write Pike program to print it in a standard form p(x) = xn + b1xn - 1 + ... + bn - 1x + bn. You should write each addend in form «C*X^K» (for example, 5*X^8).

Please, write the polynom in the shortest way, so you should skip unnecessary terms: some terms «C*X^K» should be reduced or even omitted. Look for the samples for clarification.

Input

The first line of the input contains n (1 ≤ n ≤ 9). The following n lines contain integer ai ( - 10 ≤ ai ≤ 10).

Output

Print the given polynom in a standard way. Note, that the answer in this problem response uniquely determined.

Examples

Input

2
-1
1


Output

X^2-1


Input

2
1
1


Output

X^2+2*X+1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis.
Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i.
Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.
For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.
That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.

-----Constraints-----
 - 2 \leq n,m \leq 10^5
 - -10^9 \leq x_1 < ... < x_n \leq 10^9
 - -10^9 \leq y_1 < ... < y_m \leq 10^9
 - x_i and y_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

-----Output-----
Print the total area of the rectangles, modulo 10^9+7.

-----Sample Input-----
3 3
1 3 4
1 3 6

-----Sample Output-----
60

The following figure illustrates this input:

The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rotation is one of several popular pocket billiards games. It uses 15 balls numbered from 1 to 15, and set them up as illustrated in the following figure at the beginning of a game. (Note: the ball order is modified from real-world Rotation rules for simplicity of the problem.)


[ 1]
[ 2][ 3]
[ 4][ 5][ 6]
[ 7][ 8][ 9][10]
[11][12][13][14][15]


You are an engineer developing an automatic billiards machine. For the first step you had to build a machine that sets up the initial condition. This project went well, and finally made up a machine that could arrange the balls in the triangular shape. However, unfortunately, it could not place the balls in the correct order.

So now you are trying to build another machine that fixes the order of balls by swapping them. To cut off the cost, it is only allowed to swap the ball #1 with its neighboring balls that are not in the same row. For example, in the case below, only the following pairs can be swapped: (1,2), (1,3), (1,8), and (1,9).


[ 5]
[ 2][ 3]
[ 4][ 1][ 6]
[ 7][ 8][ 9][10]
[11][12][13][14][15]


Write a program that calculates the minimum number of swaps required.



Input

The first line of each test case has an integer N (1 \leq N \leq 5), which is the number of the rows.

The following N lines describe how the balls are arranged by the first machine; the i-th of them consists of exactly i integers, which are the ball numbers.

The input terminates when N = 0. Your program must not output for this case.

Output

For each test case, print its case number and the minimum number of swaps.

You can assume that any arrangement can be fixed by not more than 45 swaps.

Example

Input

2
3
2 1
4
9
2 4
8 5 3
7 1 6 10
0


Output

Case 1: 1
Case 2: 13

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

The input consists of a single string of uppercase letters A-Z. The length of the string is between 1 and 10 characters, inclusive.

Output

Output "YES" or "NO".

Examples

Input


GENIUS


Output


YES


Input


DOCTOR


Output


NO


Input


IRENE


Output


YES


Input


MARY


Output


NO


Input


SMARTPHONE


Output


NO


Input


REVOLVER


Output


YES


Input


HOLMES


Output


NO


Input


WATSON


Output


YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This (unpronounceable) word means simply fear of number 666. 

You are given a string of digits. Check whether it is scary for a person suffering from this phobia, i.e., whether it contains number 666 as a substring.

Input

The input will consist of a single string p. The string contains between 1 and 100 digits ('0'-'9'), inclusive. The string doesn't contain any other characters except digits.

Output

Output "YES" if given string contains number 666, and "NO" otherwise (quotes for clarity only).

Examples

Input

123098


Output

NO


Input

16660


Output

YES


Input

1606061


Output

NO

Note

Note that 666 must be a contiguous substring of p, not a subsequence (see sample 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.

At some points on the road there are n friends, and i-th of them is standing at the point x_{i} meters and can move with any speed no greater than v_{i} meters per second in any of the two directions along the road: south or north.

You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate. 


-----Input-----

The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.

The second line contains n integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9) — the current coordinates of the friends, in meters.

The third line contains n integers v_1, v_2, ..., v_{n} (1 ≤ v_{i} ≤ 10^9) — the maximum speeds of the friends, in meters per second.


-----Output-----

Print the minimum time (in seconds) needed for all the n friends to meet at some point on the road. 

Your answer will be considered correct, if its absolute or relative error isn't greater than 10^{ - 6}. Formally, let your answer be a, while jury's answer be b. Your answer will be considered correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$ holds.


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

Output
2.000000000000

Input
4
5 10 3 2
2 3 2 4

Output
1.400000000000



-----Note-----

In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a singly linked list of size N of integers. The task is to check if the given linked list is palindrome or not.
Example 1:
Input:
N = 3
value[] = {1,2,1}
Output: 1
Explanation: The given linked list is
1 2 1 , which is a palindrome and
Hence, the output is 1.
Example 2:
Input:
N = 4
value[] = {1,2,3,4}
Output: 0
Explanation: The given linked list
is 1 2 3 4 , which is not a palindrome
and Hence, the output is 0.
Your Task:
The task is to complete the function isPalindrome() which takes head as reference as the only parameter and returns true or false if linked list is palindrome or not respectively.
Expected Time Complexity: O(N)
Expected Auxialliary Space Usage: O(1)  (ie, you should not use the recursive stack space as well)
Constraints:
1 <= N <= 10^{5}

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