vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
While reviewing code recently being checked into the repository, Jim discovered that some employees now and then seemed to copy code right from the Internet into the company code base. This would be a potential disaster as the company then risks getting sued by copyright holders of the original code. The obvious solution, talking to the employees and kindly ask them not to submit any stolen code, seemed to solve the problem. Still, it was decided that a screening process should be introduced to detect newly stolen code. 

The screening would work as follows: Every time new code was checked in, the full contents of the changed files where matched against a repository of known open source code. For each file the longest match, in number of consecutive lines, should be reported.

Comparison is done line by line. Empty lines, and lines only containing space, are ignored during comparison and not counted. Leading and trailing spaces should be ignored completely and consecutive space characters inside the lines are treated as one single space. The comparison is case-sensitive.

-----Input-----
Test data starts with the number $0 \le N \le 100$ of code fragments in the repository. Then follows, for each code fragment, one line containing the file name that the fragment was fetched from and the contents of the fragment on subsequent lines. File names will neither contain whitespace nor be guaranteed to be unique. The name is at most 254 characters long. Each fragment is terminated by ***END*** on a line by its own. This line is not considered being part of the fragment.

After the fragments in the repository have all been listed, comes the actual code snippet to find matches for. This snippet is also terminated by ***END*** on a line by its own.

Lines are guaranteed to be no longer than $254$ characters. No code fragment will be longer than $10000$ lines. Any code and file name lines will only contain the ASCII characters 32-126. The total size of the input file will not exceed $10^6$ characters.

-----Output-----
Output the number of matching consecutive lines (empty lines not counted) in a longest match from the repository, followed by a space-separated list of the file names of each fragments containing a match of this length, given in the order that the matching fragments were presented in the repository description. If no fragments match, write the number 0 on a line of its own.

-----Examples-----
Sample Input:
2
HelloWorld.c
int Main() {
    printf("Hello %d\n",i);
}
***END***
Add.c
int Main() {
  for (int i=0; i<10; i++)
    sum += i;
  printf("SUM %d", sum);
}
***END***
int Main() {
  printf("Hello %d\n",i);
  printf("THE END\n");
}
***END***
Sample Output:
2 HelloWorld.c

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You were strolling outside the restaurant at the end of the universe. On a metaspiral path you stumble upon a weird device which takes a three-digit number as input and processes it. The Hitchhiker's guide to the galaxy explains that it processes the input in the following manner: 
- Multiplies it with 13, followed by 11 and then 7          
- Outputs all the distinct three-digit numbers possible from the digits of the new number (each digit can only be used once)          
Your friend Zaphod is in a playful mood, and does the following with the device-           
- Given a three-digit positive number $K$, he feeds it to the device for processing.          
- He then takes the numbers it gives as output, and send each of them through the device and again collect all the numbers sent out.          
- Repeats the above step $N$ times.          
To test your wit, he challenges you to find the number of distinct 3-digit numbers which the device outputs over the $N$ steps. Can you?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, two integers $K, N$.

-----Output:-----
For each testcase, output a single integer denoting the number of distinct 3-digit numbers which the device outputs over the $N$ steps.

-----Constraints-----
- $1 \leq T \leq 1000$ 
- $5 \leq N \leq 10^9$ 
- Each digit of $K$ is non-zero           

-----Sample Input:-----
1

123 5         

-----Sample Output:-----
27

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The hero of this story is a toddler named BooBoo. Inspired by the legendary competitive coder Gena, BooBoo has also started preparing to race to the top of the ranks.

BooBoo is going to practice N different problems in the exact given order over the next M days. For each problem, he writes down the amount of time q_i he will take to think and code the i^{th} problem (He is quite good at estimating!). Before starting on the problems, he took advice from experienced competitive programmers on his practice routine and almost all of them advised him to keep his daily load at the minimum possible and avoid over training.

Since BooBoo already has N problems to solve, he asks you to find the minimum time T such that training everyday for a time t_i ≤ T is sufficient to solve all the N problems in M days.

Note : Unlike in real world, you cannot think on a problem on one day and solve it on the other day. You need to do it on the very same day!

Input Format:

The first line contains two space separated integers N and M. The next line contains N space  separated integers denoting the time q_i required to solve the i^{th} problem.

Output Format:

The output consists of one integer, the minimum time T as described in the problem statement.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ M ≤ N
1 ≤ q_i ≤ 10^{12}

SAMPLE INPUT
5 3
1 2 2 1 3

SAMPLE OUTPUT
3

Explanation

By setting T = 3, we can solve 1st two questions on day 1, next two on day 2 and 5th one on day 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an array of non-negative integers $a_1, a_2, \ldots, a_n$ a $k$-extension for some non-negative integer $k$ if for all possible pairs of indices $1 \leq i, j \leq n$ the inequality $k \cdot |i - j| \leq min(a_i, a_j)$ is satisfied. The expansion coefficient of the array $a$ is the maximal integer $k$ such that the array $a$ is a $k$-extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$. Find its expansion coefficient.


-----Input-----

The first line contains one positive integer $n$ — the number of elements in the array $a$ ($2 \leq n \leq 300\,000$). The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, separated by spaces ($0 \leq a_i \leq 10^9$).


-----Output-----

Print one non-negative integer — expansion coefficient of the array $a_1, a_2, \ldots, a_n$.


-----Examples-----
Input
4
6 4 5 5

Output
1
Input
3
0 1 2

Output
0
Input
4
821 500 479 717

Output
239


-----Note-----

In the first test, the expansion coefficient of the array $[6, 4, 5, 5]$ is equal to $1$ because $|i-j| \leq min(a_i, a_j)$, because all elements of the array satisfy $a_i \geq 3$. On the other hand, this array isn't a $2$-extension, because $6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$ is false.

In the second test, the expansion coefficient of the array $[0, 1, 2]$ is equal to $0$ because this array is not a $1$-extension, but it is $0$-extension.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Base64 Numeric Translator

Our standard numbering system is (Base 10). That includes 0 through 9. Binary is (Base 2), only 1’s and 0’s.  And Hexadecimal is (Base 16) (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). A hexadecimal “F” has a (Base 10) value of 15. (Base 64) has 64 individual characters which translate in value in (Base 10) from between 0 to 63.

####Write a method that will convert a string from (Base 64) to it's (Base 10) integer value.

The (Base 64) characters from least to greatest will be
```
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
```
Where 'A' is equal to 0 and '/' is equal to 63.

Just as in standard (Base 10) when you get to the highest individual integer 9 the next number adds an additional place and starts at the beginning 10; so also (Base 64) when you get to the 63rd digit '/' and the next number adds an additional place and starts at the beginning "BA".

Example:
```
base64_to_base10("/") # => 63
base64_to_base10("BA") # => 64
base64_to_base10("BB") # => 65
base64_to_base10("BC") # => 66
```

Write a method `base64_to_base10` that will take a string (Base 64) number and output it's (Base 10) value as an integer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you may know, MemSQL has American offices in both San Francisco and Seattle. Being a manager in the company, you travel a lot between the two cities, always by plane.

You prefer flying from Seattle to San Francisco than in the other direction, because it's warmer in San Francisco. You are so busy that you don't remember the number of flights you have made in either direction. However, for each of the last n days you know whether you were in San Francisco office or in Seattle office. You always fly at nights, so you never were at both offices on the same day. Given this information, determine if you flew more times from Seattle to San Francisco during the last n days, or not.


-----Input-----

The first line of input contains single integer n (2 ≤ n ≤ 100) — the number of days.

The second line contains a string of length n consisting of only capital 'S' and 'F' letters. If the i-th letter is 'S', then you were in Seattle office on that day. Otherwise you were in San Francisco. The days are given in chronological order, i.e. today is the last day in this sequence.


-----Output-----

Print "YES" if you flew more times from Seattle to San Francisco, and "NO" otherwise.

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


-----Examples-----
Input
4
FSSF

Output
NO

Input
2
SF

Output
YES

Input
10
FFFFFFFFFF

Output
NO

Input
10
SSFFSFFSFF

Output
YES



-----Note-----

In the first example you were initially at San Francisco, then flew to Seattle, were there for two days and returned to San Francisco. You made one flight in each direction, so the answer is "NO".

In the second example you just flew from Seattle to San Francisco, so the answer is "YES".

In the third example you stayed the whole period in San Francisco, so the answer is "NO".

In the fourth example if you replace 'S' with ones, and 'F' with zeros, you'll get the first few digits of π in binary representation. Not very useful information though.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a road with length $l$ meters. The start of the road has coordinate $0$, the end of the road has coordinate $l$.

There are two cars, the first standing at the start of the road and the second standing at the end of the road. They will start driving simultaneously. The first car will drive from the start to the end and the second car will drive from the end to the start.

Initially, they will drive with a speed of $1$ meter per second. There are $n$ flags at different coordinates $a_1, a_2, \ldots, a_n$. Each time when any of two cars drives through a flag, the speed of that car increases by $1$ meter per second.

Find how long will it take for cars to meet (to reach the same coordinate). 


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$): the number of test cases.

The first line of each test case contains two integers $n$, $l$ ($1 \leq n \leq 10^5$, $1 \leq l \leq 10^9$): the number of flags and the length of the road.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ in the increasing order ($1 \leq a_1 < a_2 < \ldots < a_n < l$).

It is guaranteed that the sum of $n$ among all test cases does not exceed $10^5$.


-----Output-----

For each test case print a single real number: the time required for cars to meet.

Your answer will be considered correct, if its absolute or relative error does not exceed $10^{-6}$. More formally, if your answer is $a$ and jury's answer is $b$, your answer will be considered correct if $\frac{|a-b|}{\max{(1, b)}} \leq 10^{-6}$.


-----Example-----
Input
5
2 10
1 9
1 10
1
5 7
1 2 3 4 6
2 1000000000
413470354 982876160
9 478
1 10 25 33 239 445 453 468 477

Output
3.000000000000000
3.666666666666667
2.047619047619048
329737645.750000000000000
53.700000000000000



-----Note-----

In the first test case cars will meet in the coordinate $5$.

The first car will be in the coordinate $1$ in $1$ second and after that its speed will increase by $1$ and will be equal to $2$ meters per second. After $2$ more seconds it will be in the coordinate $5$. So, it will be in the coordinate $5$ in $3$ seconds.

The second car will be in the coordinate $9$ in $1$ second and after that its speed will increase by $1$ and will be equal to $2$ meters per second. After $2$ more seconds it will be in the coordinate $5$. So, it will be in the coordinate $5$ in $3$ seconds.

In the second test case after $1$ second the first car will be in the coordinate $1$ and will have the speed equal to $2$ meters per second, the second car will be in the coordinate $9$ and will have the speed equal to $1$ meter per second. So, they will meet after $\frac{9-1}{2+1} = \frac{8}{3}$ seconds. So, the answer is equal to $1 + \frac{8}{3} = \frac{11}{3}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The sum of divisors of `6` is `12` and the sum of divisors of `28` is `56`. You will notice that `12/6 = 2` and `56/28 = 2`. We shall say that `(6,28)` is a pair with a ratio of `2`.  Similarly, `(30,140)` is also a pair but with a ratio of `2.4`. These ratios are simply decimal representations of fractions.

`(6,28)` and `(30,140)` are the only pairs in which `every member of a pair is 0 <= n < 200`. The sum of the lowest members of each pair is `6 + 30 = 36`. 

You will be given a `range(a,b)`, and your task is to group the numbers into pairs with the same ratios. You will return the sum of the lowest member of each pair in the range. If there are no pairs. return `nil` in Ruby, `0` in python. Upper limit is `2000`.

```Haskell
solve(0,200) = 36
```

Good luck!

if you like this Kata, please try:

[Simple division](https://www.codewars.com/kata/59ec2d112332430ce9000005)

[Sub-array division](https://www.codewars.com/kata/59eb64cba954273cd4000099)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string containing of 0, 1 and ? - a wildcard character, generate all distinct binary strings that can be formed by replacing each wildcard character by either 0 or 1.
Example 1:
Input: 1??0?101
Output: 10000101 10001101 10100101 10101101 
11000101 11001101 11100101 11101101
Explanation:
There will be 8 such possible strings that 
can be formed, they are 10000101, 10001101, 
10100101, 10101101, 11000101, 11001101, 
11100101 and 11101101.
Example 2:
Input: 10?
Output: 100 101
Explanation: There are 2 such possible strings
and they are 100 and 101.
Your Task:
You don't need to read or print anything. Your task is to complete the function generate_binary_string() which takes the given string as input parameter and returns a vector of strings containing all the possible strings that can be formed.
Note : Strings should be printed in lexicographically increasing order.
Expected Time complexity: O(2^{n})
Expected Space complexity: O(n*2^{n})
Constraints:
1 ≤ length of string ≤ 30
Note: Number of '?' in any string does not exceed 15.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Graph constructive problems are back! This time the graph you are asked to build should match the following properties.

The graph is connected if and only if there exists a path between every pair of vertices.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

The degree of a vertex is the number of edges incident to it.

Given a sequence of n integers a_1, a_2, ..., a_n construct a connected undirected graph of n vertices such that:

  * the graph contains no self-loops and no multiple edges; 
  * the degree d_i of the i-th vertex doesn't exceed a_i (i.e. d_i ≤ a_i); 
  * the diameter of the graph is maximum possible. 



Output the resulting graph or report that no solution exists.

Input

The first line contains a single integer n (3 ≤ n ≤ 500) — the number of vertices in the graph.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n - 1) — the upper limits to vertex degrees.

Output

Print "NO" if no graph can be constructed under the given conditions.

Otherwise print "YES" and the diameter of the resulting graph in the first line.

The second line should contain a single integer m — the number of edges in the resulting graph.

The i-th of the next m lines should contain two integers v_i, u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — the description of the i-th edge. The graph should contain no multiple edges — for each pair (x, y) you output, you should output no more pairs (x, y) or (y, x).

Examples

Input


3
2 2 2


Output


YES 2
2
1 2
2 3


Input


5
1 4 1 1 1


Output


YES 2
4
1 2
3 2
4 2
5 2


Input


3
1 1 1


Output


NO

Note

Here are the graphs for the first two example cases. Both have diameter of 2.

<image> d_1 = 1 ≤ a_1 = 2

d_2 = 2 ≤ a_2 = 2

d_3 = 1 ≤ a_3 = 2 

<image> d_1 = 1 ≤ a_1 = 1

d_2 = 4 ≤ a_2 = 4

d_3 = 1 ≤ a_3 = 1

d_4 = 1 ≤ a_4 = 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call some square matrix with integer values in its cells palindromic if it doesn't change after the order of rows is reversed and it doesn't change after the order of columns is reversed.

For example, the following matrices are palindromic:

<image>

The following matrices are not palindromic because they change after the order of rows is reversed:

<image>

The following matrices are not palindromic because they change after the order of columns is reversed:

<image>

You are given n^2 integers. Put them into a matrix of n rows and n columns so that each number is used exactly once, each cell contains exactly one number and the resulting matrix is palindromic. If there are multiple answers, print any. If there is no solution, print "NO".

Input

The first line contains one integer n (1 ≤ n ≤ 20).

The second line contains n^2 integers a_1, a_2, ..., a_{n^2} (1 ≤ a_i ≤ 1000) — the numbers to put into a matrix of n rows and n columns.

Output

If it is possible to put all of the n^2 numbers into a matrix of n rows and n columns so that each number is used exactly once, each cell contains exactly one number and the resulting matrix is palindromic, then print "YES". Then print n lines with n space-separated numbers — the resulting matrix.

If it's impossible to construct any matrix, then print "NO".

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

Examples

Input


4
1 8 8 1 2 2 2 2 2 2 2 2 1 8 8 1


Output


YES
1 2 2 1
8 2 2 8
8 2 2 8
1 2 2 1


Input


3
1 1 1 1 1 3 3 3 3


Output


YES
1 3 1
3 1 3
1 3 1


Input


4
1 2 1 9 8 4 3 8 8 3 4 8 9 2 1 1


Output


NO


Input


1
10


Output


YES
10 

Note

Note that there exist multiple answers for the first two examples.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary matrix $a$ of size $n \times m$. A binary matrix is a matrix where each element is either $0$ or $1$.

You may perform some (possibly zero) operations with this matrix. During each operation you can inverse the row of this matrix or a column of this matrix. Formally, inverting a row is changing all values in this row to the opposite ($0$ to $1$, $1$ to $0$). Inverting a column is changing all values in this column to the opposite.

Your task is to sort the initial matrix by some sequence of such operations. The matrix is considered sorted if the array $[a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, a_{n, m - 1}, a_{n, m}]$ is sorted in non-descending order.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 200$) — the number of rows and the number of columns in the matrix.

The next $n$ lines contain $m$ integers each. The $j$-th element in the $i$-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 1$) — the element of $a$ at position $(i, j)$.


-----Output-----

If it is impossible to obtain a sorted matrix, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print a string $r$ of length $n$. The $i$-th character $r_i$ of this string should be '1' if the $i$-th row of the matrix is inverted and '0' otherwise. In the third line print a string $c$ of length $m$. The $j$-th character $c_j$ of this string should be '1' if the $j$-th column of the matrix is inverted and '0' otherwise. If there are multiple answers, you can print any.


-----Examples-----
Input
2 2
1 1
0 1

Output
YES
00
10

Input
3 4
0 0 0 1
0 0 0 0
1 1 1 1

Output
YES
010
0000

Input
3 3
0 0 0
1 0 1
1 1 0

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will get an array of numbers. 

Every preceding number is smaller than the one following it.

Some numbers will be missing, for instance:
```
[-3,-2,1,5] //missing numbers are: -1,0,2,3,4
```
Your task is to return an array of those missing numbers:
```
[-1,0,2,3,4]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The string $t_1t_2 \dots t_k$ is good if each letter of this string belongs to at least one palindrome of length greater than 1.

A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.

Here are some examples of good strings:   $t$ = AABBB (letters $t_1$, $t_2$ belong to palindrome $t_1 \dots t_2$ and letters $t_3$, $t_4$, $t_5$ belong to palindrome $t_3 \dots t_5$);  $t$ = ABAA (letters $t_1$, $t_2$, $t_3$ belong to palindrome $t_1 \dots t_3$ and letter $t_4$ belongs to palindrome $t_3 \dots t_4$);  $t$ = AAAAA (all letters belong to palindrome $t_1 \dots t_5$); 

You are given a string $s$ of length $n$, consisting of only letters A and B.

You have to calculate the number of good substrings of string $s$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the string $s$.

The second line contains the string $s$, consisting of letters A and B.


-----Output-----

Print one integer — the number of good substrings of string $s$.


-----Examples-----
Input
5
AABBB

Output
6

Input
3
AAA

Output
3

Input
7
AAABABB

Output
15



-----Note-----

In the first test case there are six good substrings: $s_1 \dots s_2$, $s_1 \dots s_4$, $s_1 \dots s_5$, $s_3 \dots s_4$, $s_3 \dots s_5$ and $s_4 \dots s_5$.

In the second test case there are three good substrings: $s_1 \dots s_2$, $s_1 \dots s_3$ and $s_2 \dots s_3$.

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