vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Sunita has lots of tasks pending and she has no time to complete.  She needs your help and wants you complete the task.
You are given a list of integers and two values $N$ and $K$ $-$ the size of array of integers and the numbers of partitions to be made respectively.
You have to partition the list of integers without changing the order of elements ,into exactly $K$ parts. 
Calculate Greatest Common Divisor of all $K$ partition and sum up the gcd values for each partition.
Maximize the sum obtained. 
Can you help Sunita ? 

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input, two integers $N, K$. 
- Next line contains $N$ integers $-$ the list of integers.

-----Output:-----
For each test case, output in a single line integer $-$ the maximal result.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N, K \leq 250$
- $1 \leq K \leq N$
- $1 \leq A[i] \leq 1e5$

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

-----Sample Output:-----
6

-----EXPLANATION:-----
[5] [6 3 2] is the best partition [5 + GCD(6,3,2)] = 6

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There is a very secret base in Potatoland where potato mash is made according to a special recipe. The neighbours from Porridgia decided to seize this recipe and to sell it to Pilauland. For this mission they have been preparing special agent Pearlo for many years. When, finally, Pearlo learned all secrets of espionage, he penetrated into the Potatoland territory and reached the secret base.

Now he is standing at the entrance, but to get inside he need to pass combination lock. Minute ago one of the workers entered the password on the terminal and opened the door. The terminal is a square digital keyboard 3<=×<=3 with digits from 1 to 9.

Pearlo knows that the password consists from distinct digits and is probably symmetric with respect to the central button of the terminal. He has heat sensor which allowed him to detect the digits which the worker pressed. Now he wants to check whether the password entered by the worker is symmetric with respect to the central button of the terminal. This fact can Help Pearlo to reduce the number of different possible password combinations.

Input Specification:
Input contains the matrix of three rows of three symbols each. Symbol «X» means that the corresponding button was pressed, and «.» means that is was not pressed. The matrix may contain no «X», also it may contain no «.».

Output Specification:
Print YES if the password is symmetric with respect to the central button of the terminal and NO otherwise.

Demo Input:
['XX.\n...\n.XX\n', 'X.X\nX..\n...\n']

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

Note:
If you are not familiar with the term «central symmetry», you may look into http://en.wikipedia.org/wiki/Central_symmetry

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tara has an array, $\mbox{A}$, consisting of $n$ integers where each integer occurs at most $2$ times in the array. 

Let's define $\mbox{P}$ to be a permutation of $\mbox{A}$ where $p_i$ is the $i^{\mbox{th}}$ element of permutation $\mbox{P}$. Tara thinks a permutation is beautiful if there is no index $\boldsymbol{i}$ such that $p_{i}-p_{i+1}=0$ where $i\in[0,n-1)$.

You are given $\textit{q}$ queries where each query consists of some array $\mbox{A}$. For each $\mbox{A}$, help Tara count the number of possible beautiful permutations of the $n$ integers in $\mbox{A}$ and print the count, modulo $10^9+7$, on a new line.

Note: Two permutations, $\mbox{P}$ and $\mbox{Q}$, are considered to be different if and only if there exists an index $\boldsymbol{i}$ such that $p_i\neq q_i$ and $i\in[0,n)$.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The $2\cdot q$ subsequent lines describe each query in the following form:

The first line contains an integer, $n$, denoting the number of elements in array $\mbox{A}$. 
The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$ in array $\mbox{A}$.

Constraints

$1\leq a_i\leq10^9$
Each integer in $\mbox{A}$ can occur at most $2$ times.

For $\textbf{40\%}$ of the maximum score:

$1\leq q\leq100$    
$1\leq n\leq1000$  
The sum of $n$ over all queries does not exceed $\mathbf{10}^4$.  

For $\textbf{100\%}$ of the maximum score:  

$1\leq q\leq100$    
$1\leq n\leq2000$

Output Format

For each query, print the the number of possible beautiful permutations, modulo $10^9+7$, on a new line.

Sample Input 0
3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0
1
2
2

Explanation 0

We perform the following $q=3$ queries:

Array $A=[1,2,1]$ and there is only one good permutation: 

Thus, we print the result of $1\:\text{mod}\:(10^9+7)=1$ on a new line.

Array $A=[1,2]$ and there are two good permutations: 

Thus, we print the result of $2\ \text{mod}\ (10^9+7)=2$ on a new line.

Array $A=[1,2,2,1]$ and there are two good permutations: 

For demonstration purposes, the following two permutations are invalid (i.e., not good): 

Because we only want the number of good permutations, we print the result of $2\ \text{mod}\ (10^9+7)=2$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).
 
Example 1:
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].
Example 2:
Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].
 
Constraints:

0 <= low <= high <= 10^9

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

Fred is the captain of a spaceship crew. He wishes to build a some spaceships. Each spaceship requires n parts labeled from 1 to n.

Fred can buy parts from various vendors. More specifically, there are n vendors, labeled from 1 to n. Each vendor will sell some subset of the parts at various prices. Additionally, each of the vendors will sell the parts for some integer amount between 0 and 10 dollars, inclusive. It is also possible for a vendor to sell the same part for different prices. Each vendor has an unlimited supply of the part/cost that they are selling.

Each spaceship that Fred builds requires exactly one copy of each part. In addition, in the interest of fairness, the spaceship must have exactly one part from every vendor. The total cost of a spaceship is the sum of the cost of the parts.

Now, Fred wants to build spaceships of all kinds (i.e. luxury spaceships, cheap spaceships, and everything in between). Thus, he wants to know, what are all the possible costs a spaceship can take on. More specifically, he is interested in the (10n+1) bit string, where the i-th bit (0-based) is '1' if there is a spaceship that costs exactly i, and '0' otherwise. Help Fred compute this string.

Input Format:
The first line of input will contain two integers n,m.
The next m lines of input will contain three integers ai, bi, ci, which is a description of the i-th product. This means that the ai-th vendor is selling the bi-th part for ci dollars. 

Output Format:
A (10n+1) bit string, as described in the statement. 

Constraints

For all subtasks: 
1 ≤ m ≤ 11 × n^2
0 ≤ ci ≤ 10
1 ≤ ai,bi ≤ n

10 pts:
1 ≤ n ≤ 5

20 pts:
1 ≤ n ≤ 12

25 pts:
1 ≤ n ≤ 20

25 pts:
1 ≤ n ≤ 50
There are at most 10 products with nonzero cost.

20 pts:
1 ≤ n ≤ 50

SAMPLE INPUT
3 9
1 1 1
1 2 3
1 3 9
2 1 2
2 2 5
2 2 6
3 1 4
3 2 10
3 3 0

SAMPLE OUTPUT
0000011100000000001101000000000

Explanation

Fred can make a spaceship of cost 5 by taking part 1 from vendor 2, part 2 from vendor 1, and part 3 from vendor 3. The spaceship of cost 6 can be made from taking part 1 from vendor 1, part 2 from vendor 2, and part 3 from vendor 3.

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


NEAT


Output


YES


Input


WORD


Output


NO


Input


CODER


Output


NO


Input


APRILFOOL


Output


NO


Input


AI


Output


YES


Input


JUROR


Output


YES


Input


YES


Output


NO

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
You are given a rectangular board of *M*<=×<=*N* squares. Also you are given an unlimited number of standard domino pieces of 2<=×<=1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

1. Each domino completely covers two squares.

2. No two dominoes overlap.

3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

Input Specification:
In a single line you are given two integers *M* and *N* — board sizes in squares (1<=≤<=*M*<=≤<=*N*<=≤<=16).

Output Specification:
Output one number — the maximal number of dominoes, which can be placed.

Demo Input:
['2 4\n', '3 3\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads.
The following are known about the road network:
 - People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
 - Different roads may have had different lengths, but all the lengths were positive integers.
Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom.
He thought that it represented the shortest distances between the cities along the roads in the kingdom.
Determine whether there exists a road network such that for each u and v, the integer A_{u, v} at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v.
If such a network exist, find the shortest possible total length of the roads.

-----Constraints-----
 - 1 \leq N \leq 300
 - If i ≠ j, 1 \leq A_{i, j} = A_{j, i} \leq 10^9.
 - A_{i, i} = 0

-----Inputs-----
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}

-----Outputs-----
If there exists no network that satisfies the condition, print -1.
If it exists, print the shortest possible total length of the roads.

-----Sample Input-----
3
0 1 3
1 0 2
3 2 0

-----Sample Output-----
3

The network below satisfies the condition:
 - City 1 and City 2 is connected by a road of length 1.
 - City 2 and City 3 is connected by a road of length 2.
 - City 3 and City 1 is not connected by a road.

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

Taro has N character strings, each of which is L in length. Taro loves palindromes, so I want to make palindromes as long as possible by selecting some of the N character strings and arranging them in any order.

Find the longest palindrome that Taro can make. If there are more than one, output the smallest one in lexicographical order. If you can't make a palindrome no matter how you choose and arrange them, output a blank line.

Constraints

The input satisfies the following conditions.

* 1 ≤ N ≤ 1000
* 1 ≤ L ≤ 30
* s_i is a character string consisting of lowercase letters.

Input

The input is given in the following format.


N L
s1
s2
..
..
..
sN


The number N of strings and the length L of strings are given on the first line. From the second line that follows, N & plus; The character string s_i that Taro has is given to the first line.

Output

Output the longest palindrome with the smallest dictionary order. If you cannot make a palindrome, output a blank line.

Examples

Input

4 2
oi
io
rr
rr


Output

iorrrroi


Input

5 1
a
b
c
a
c


Output

acbca


Input

3 3
uki
uku
uke


Output

uku

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a text consisting of *n* lines. Each line contains some space-separated words, consisting of lowercase English letters.

We define a syllable as a string that contains exactly one vowel and any arbitrary number (possibly none) of consonants. In English alphabet following letters are considered to be vowels: 'a', 'e', 'i', 'o', 'u' and 'y'.

Each word of the text that contains at least one vowel can be divided into syllables. Each character should be a part of exactly one syllable. For example, the word "mamma" can be divided into syllables as "ma" and "mma", "mam" and "ma", and "mamm" and "a". Words that consist of only consonants should be ignored.

The verse patterns for the given text is a sequence of *n* integers *p*1,<=*p*2,<=...,<=*p**n*. Text matches the given verse pattern if for each *i* from 1 to *n* one can divide words of the *i*-th line in syllables in such a way that the total number of syllables is equal to *p**i*.

You are given the text and the verse pattern. Check, if the given text matches the given verse pattern.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of lines in the text.

The second line contains integers *p*1,<=...,<=*p**n* (0<=≤<=*p**i*<=≤<=100) — the verse pattern.

Next *n* lines contain the text itself. Text consists of lowercase English letters and spaces. It's guaranteed that all lines are non-empty, each line starts and ends with a letter and words are separated by exactly one space. The length of each line doesn't exceed 100 characters.

Output Specification:
If the given text matches the given verse pattern, then print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).

Demo Input:
['3\n2 2 3\nintel\ncode\nch allenge\n', '4\n1 2 3 1\na\nbcdefghi\njklmnopqrstu\nvwxyz\n', '4\n13 11 15 15\nto be or not to be that is the question\nwhether tis nobler in the mind to suffer\nthe slings and arrows of outrageous fortune\nor to take arms against a sea of troubles\n']

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

Note:
In the first sample, one can split words into syllables in the following way: 

Since the word "ch" in the third line doesn't contain vowels, we can ignore it. As the result we get 2 syllabels in first two lines and 3 syllables in the third one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A line on the plane is described by an equation Ax + By + C = 0. You are to find any point on this line, whose coordinates are integer numbers from  - 5·1018 to 5·1018 inclusive, or to find out that such points do not exist.

Input
The first line contains three integers A, B and C ( - 2·109 ≤ A, B, C ≤ 2·109) — corresponding coefficients of the line equation. It is guaranteed that A2 + B2 > 0.

Output
If the required point exists, output its coordinates, otherwise output -1.

SAMPLE INPUT
2 5 3

SAMPLE OUTPUT
6 -3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
KM country has N kinds of coins and each coin has its value a_i.

The king of the country, Kita_masa, thought that the current currency system is poor, and he decided to make it beautiful by changing the values of some (possibly no) coins.

A currency system is called beautiful if each coin has an integer value and the (i+1)-th smallest value is divisible by the i-th smallest value for all i (1 \leq i \leq N-1).

For example, the set {1, 5, 10, 50, 100, 500} is considered as a beautiful system, while the set {1, 5, 10, 25, 50, 100} is NOT, because 25 is not divisible by 10.

Since changing the currency system may confuse citizens, the king, Kita_masa, wants to minimize the maximum value of the confusion ratios. Here, the confusion ratio for the change in the i-th coin is defined as |a_i - b_i| / a_i, where a_i and b_i is the value of i-th coin before and after the structure changes, respectively.

Note that Kita_masa can change the value of each existing coin, but he cannot introduce new coins nor eliminate existing coins. After the modification, the values of two or more coins may coincide.



Input

Each dataset contains two lines. The first line contains a single integer, N, and the second line contains N integers, {a_i}.

You may assume the following constraints:

1 \leq N \leq 20

1 \leq a_1 \lt a_2 \lt... \lt a_N \lt 10^5

Output

Output one number that represents the minimum of the maximum value of the confusion ratios. The value may be printed with an arbitrary number of decimal digits, but may not contain an absolute error greater than or equal to 10^{-8}.

Examples

Input

3
6 11 12


Output

0.090909090909


Input

3
6 11 24


Output

0.090909090909


Input

3
6 11 30


Output

0.166666666667

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have *a* nuts and lots of boxes. The boxes have a wonderful feature: if you put *x* (*x*<=≥<=0) divisors (the spacial bars that can divide a box) to it, you get a box, divided into *x*<=+<=1 sections.

You are minimalist. Therefore, on the one hand, you are against dividing some box into more than *k* sections. On the other hand, you are against putting more than *v* nuts into some section of the box. What is the minimum number of boxes you have to use if you want to put all the nuts in boxes, and you have *b* divisors?

Please note that you need to minimize the number of used boxes, not sections. You do not have to minimize the number of used divisors.

Input Specification:
The first line contains four space-separated integers *k*, *a*, *b*, *v* (2<=≤<=*k*<=≤<=1000; 1<=≤<=*a*,<=*b*,<=*v*<=≤<=1000) — the maximum number of sections in the box, the number of nuts, the number of divisors and the capacity of each section of the box.

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['3 10 3 3\n', '3 10 1 3\n', '100 100 1 1000\n']

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

Note:
In the first sample you can act like this: 
 -  Put two divisors to the first box. Now the first box has three sections and we can put three nuts into each section. Overall, the first box will have nine nuts. -  Do not put any divisors into the second box. Thus, the second box has one section for the last nut. 
In the end we've put all the ten nuts into boxes.

The second sample is different as we have exactly one divisor and we put it to the first box. The next two boxes will have one section each.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For an n \times n grid, let (r, c) denote the square at the (r+1)-th row from the top and the (c+1)-th column from the left. A good coloring of this grid using K colors is a coloring that satisfies the following:

* Each square is painted in one of the K colors.
* Each of the K colors is used for some squares.
* Let us number the K colors 1, 2, ..., K. For any colors i and j (1 \leq i \leq K, 1 \leq j \leq K), every square in Color i has the same number of adjacent squares in Color j. Here, the squares adjacent to square (r, c) are ((r-1)\; mod\; n, c), ((r+1)\; mod\; n, c), (r, (c-1)\; mod\; n) and (r, (c+1)\; mod\; n) (if the same square appears multiple times among these four, the square is counted that number of times).



Given K, choose n between 1 and 500 (inclusive) freely and construct a good coloring of an n \times n grid using K colors. It can be proved that this is always possible under the constraints of this problem,

Constraints

* 1 \leq K \leq 1000

Input

Input is given from Standard Input in the following format:


K


Output

Output should be in the following format:


n
c_{0,0} c_{0,1} ... c_{0,n-1}
c_{1,0} c_{1,1} ... c_{1,n-1}
:
c_{n-1,0} c_{n-1,1} ... c_{n-1,n-1}


n should represent the size of the grid, and 1 \leq n \leq 500 must hold. c_{r,c} should be an integer such that 1 \leq c_{r,c} \leq K and represent the color for the square (r, c).

Examples

Input

2


Output

3
1 1 1
1 1 1
2 2 2


Input

9


Output

3
1 2 3
4 5 6
7 8 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n. 

You are given n integers c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between  - 2·n2 and 2·n2 (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to cv, or determine that this is impossible.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output

If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge wi ( - 2·n2 ≤ wi ≤ 2·n2).

Examples

Input

3 3
2 2 2
1 2
2 3
1 3


Output

YES
1
1
1


Input

4 3
-1 0 2 1
1 2
2 3
3 4


Output

YES
-1
1
1


Input

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


Output

YES
3
5
3
-1
-3
5


Input

4 4
4 4 2 4
1 2
2 3
3 4
4 1


Output

NO

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