vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Running with Obstacles

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A sportsman starts from point *x**start*<==<=0 and runs to point with coordinate *x**finish*<==<=*m* (on a straight line). Also, the sportsman can jump — to jump, he should first take a run of length of not less than *s* meters (in this case for these *s* meters his path should have no obstacles), and after that he can jump over a length of not more than *d* meters. Running and jumping is permitted only in the direction from left to right. He can start andfinish a jump only at the points with integer coordinates in which there are no obstacles. To overcome some obstacle, it is necessary to land at a point which is strictly to the right of this obstacle.

On the way of an athlete are *n* obstacles at coordinates *x*1,<=*x*2,<=...,<=*x**n*. He cannot go over the obstacles, he can only jump over them. Your task is to determine whether the athlete will be able to get to the finish point.

Input Specification:
The first line of the input containsd four integers *n*, *m*, *s* and *d* (1<=≤<=*n*<=≤<=200<=000, 2<=≤<=*m*<=≤<=109, 1<=≤<=*s*,<=*d*<=≤<=109) — the number of obstacles on the runner's way, the coordinate of the finishing point, the length of running before the jump and the maximum length of the jump, correspondingly.

The second line contains a sequence of *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*m*<=-<=1) — the coordinates of the obstacles. It is guaranteed that the starting and finishing point have no obstacles, also no point can have more than one obstacle, The coordinates of the obstacles are given in an arbitrary order.

Output Specification:
If the runner cannot reach the finishing point, print in the first line of the output "IMPOSSIBLE" (without the quotes).

If the athlete can get from start to finish, print any way to do this in the following format:
 -  print a line of form "RUN X&gt;" (where "X" should be a positive integer), if the athlete should run for "X" more meters; -  print a line of form "JUMP Y" (where "Y" should be a positive integer), if the sportsman starts a jump and should remain in air for "Y" more meters. 
All commands "RUN" and "JUMP" should strictly alternate, starting with "RUN", besides, they should be printed chronologically. It is not allowed to jump over the finishing point but it is allowed to land there after a jump. The athlete should stop as soon as he reaches finish.

Demo Input:
['3 10 1 3\n3 4 7\n', '2 9 2 3\n6 4\n']

Demo Output:
['RUN 2\nJUMP 3\nRUN 1\nJUMP 2\nRUN 2\n', 'IMPOSSIBLE\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array.

More formally, given a suffix array of length $n$ and having an alphabet size $k$, count the number of strings that produce such a suffix array.

Let $s$ be a string of length $n$. Then the $i$-th suffix of $s$ is the substring $s[i \ldots n-1]$. A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $[3,2,4,1,0,5,6]$ as the array of sorted suffixes is $[{imry},{limry},{mry},{olimry},{oolimry},{ry},{y}]$.

A string $x$ is lexicographically smaller than string $y$, if either $x$ is a prefix of $y$ (and $x\neq y$), or there exists such $i$ that $x_i < y_i$, and for any $1\leq j < i$ , $x_j = y_j$.


-----Input-----

The first line contain 2 integers $n$ and $k$ ($1 \leq n \leq 200000,1 \leq k \leq 200000$) — the length of the suffix array and the alphabet size respectively.

The second line contains $n$ integers $s_0, s_1, s_2, \ldots, s_{n-1}$ ($0 \leq s_i \leq n-1$) where $s_i$ is the $i$-th element of the suffix array i.e. the starting position of the $i$-th lexicographically smallest suffix. It is guaranteed that for all $0 \leq i< j \leq n-1$, $s_i \neq s_j$.


-----Output-----

Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $998244353$.


-----Examples-----

Input
3 2
0 2 1
Output
1
Input
5 1
0 1 2 3 4
Output
0
Input
6 200000
0 1 2 3 4 5
Output
822243495
Input
7 6
3 2 4 1 0 5 6
Output
36


-----Note-----

In the first test case, "abb" is the only possible solution.

In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal.

In the fourth test case, one possible string is "ddbacef".

Please remember to print your answers modulo $998244353$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations.

Initially, there are $n$ superheroes in avengers team having powers $a_1, a_2, \ldots, a_n$, respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by $1$. They can do at most $m$ operations. Also, on a particular superhero at most $k$ operations can be done.

Can you help the avengers team to maximize the average power of their crew?


-----Input-----

The first line contains three integers $n$, $k$ and $m$ ($1 \le n \le 10^{5}$, $1 \le k \le 10^{5}$, $1 \le m \le 10^{7}$) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{6}$) — the initial powers of the superheroes in the cast of avengers.


-----Output-----

Output a single number — the maximum final average power.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.


-----Examples-----
Input
2 4 6
4 7

Output
11.00000000000000000000

Input
4 2 6
1 3 2 3

Output
5.00000000000000000000



-----Note-----

In the first example, the maximum average is obtained by deleting the first element and increasing the second element four times.

In the second sample, one of the ways to achieve maximum average is to delete the first and the third element and increase the second and the fourth elements by $2$ each.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John was given N number of candy bars all of varied length. He puts all the candy bars side by side of each other in a random order and now he wants to arrange them in increasing order of their length, but doesn’t know how to do this in minimum number of attempts. Help him out in doing so.

Input

There will be 2 line of inputs. 1st line will contain number of candies (N) and 2nd line will contain N different heights (positive integer) separated by space.

Output

A single line containing the number of attempts required to arrange the given candies in increasing order of their lengths.

Note :- Shifting and swapping all included into one will be counted as 1 attempt.

Constraints

1 ≤ N ≤ 10000

1 ≤ h ≤ 10000

SAMPLE INPUT
9
9 5 4 3 1 7 6  8 10

SAMPLE OUTPUT
5

Explanation

In  9 5 4 3 1 7 6 8 10, shifting 10 towards right by one index and then inserting 9 at between 8 and 10 gives 5 4 3 1 7 6 8 9 10 -> 1st attempt
now shifting 8, 9 and 10 towards right by one index and then inserting 7 between 6 and 8 gives 5 4 3 1 6 7 8 9 10 -> 2nd attempt
doing same for 5 by shifting 6, 7, 8, 9 and 10 towards right and inserting 5 between 1 and 6 gives 4 3 1 5 6 7 8 9 10 ->3rd attempt
now shifting 5, 6, 7, 8, 9 and 10 towards right and inserting 4 between 1 and 5 gives 3 1 4 5 6 7 8 9 10 ->4th attempt
finally shifting 4, 5, 6, 7, 8, 9 and 10 towards right and inserting 3 between 1 and 4 gives 1 3 4 5 6 7 8 9 10 ->5th attempt

so a total of 5 attempts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rahul and Rashi are bored with playing the game of Nim, particularly after Rahul gained a thorough understanding of game theory, and would always win.

Now, they are going to play on a variation. 
There are only 2 piles of coins. Each player can make the following move:
Pick K ( ≥ 1) coins from pile 1.
Pick K ( ≥ 1) coins from pile 2.
Pick K ( ≥ 1) coins from pile 1 as well as pile 2.

As with the older version, the person unable to make a move shall lose. Can you help analyse this game for the novice, Rashi.

Input Format:

The first line contains an integer T, denoting the number of test cases to follow.
The next T lines each contain two integers N1 and N2, separated by a single space, denoting sizes of first pile and second pile respectively. 

Output Format:

The output file should contain exactly T lines.
Output Play, if Rashi would win as the first player and Don't Play, if she shall lose.

Constraints:

1 ≤ T ≤ 10^5
0 ≤ N1, N2 ≤ 10^6

SAMPLE INPUT
3
1 1
0 2
1 2

SAMPLE OUTPUT
Play
Play
Don't Play

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Smart Beaver from ABBYY loves puzzles. One of his favorite puzzles is the magic square. He has recently had an idea to automate the solution of this puzzle. The Beaver decided to offer this challenge to the ABBYY Cup contestants.

The magic square is a matrix of size n × n. The elements of this matrix are integers. The sum of numbers in each row of the matrix is equal to some number s. The sum of numbers in each column of the matrix is also equal to s. In addition, the sum of the elements on the main diagonal is equal to s and the sum of elements on the secondary diagonal is equal to s. Examples of magic squares are given in the following figure:

<image> Magic squares 

You are given a set of n2 integers ai. It is required to place these numbers into a square matrix of size n × n so that they form a magic square. Note that each number must occur in the matrix exactly the same number of times as it occurs in the original set.

It is guaranteed that a solution exists!

Input

The first input line contains a single integer n. The next line contains n2 integers ai ( - 108 ≤ ai ≤ 108), separated by single spaces.

The input limitations for getting 20 points are: 

  * 1 ≤ n ≤ 3



The input limitations for getting 50 points are: 

  * 1 ≤ n ≤ 4
  * It is guaranteed that there are no more than 9 distinct numbers among ai. 



The input limitations for getting 100 points are: 

  * 1 ≤ n ≤ 4

Output

The first line of the output should contain a single integer s. In each of the following n lines print n integers, separated by spaces and describing the resulting magic square. In the resulting magic square the sums in the rows, columns and diagonals must be equal to s. If there are multiple solutions, you are allowed to print any of them.

Examples

Input

3
1 2 3 4 5 6 7 8 9


Output

15
2 7 6
9 5 1
4 3 8


Input

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


Output

0
1 0 -1
-2 0 2
1 0 -1


Input

2
5 5 5 5


Output

10
5 5
5 5

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

Senor Vorpal Kickass'o invented an innovative method to encrypt integer sequences of length n. To encrypt a sequence, one has to choose a secret sequence <image>, that acts as a key.

Vorpal is very selective, so the key should be such a sequence bi, that its cyclic shifts are linearly independent, that is, there is no non-zero set of coefficients x0, x1, ..., xn - 1, such that <image> for all k at the same time.

After that for a sequence <image> you should build the following cipher:

<image>

In other words, you are to compute the quadratic deviation between each cyclic shift of bi and the sequence ai. The resulting sequence is the Kickass's cipher. The cipher is in development right now and Vorpal wants to decipher a sequence after it has been encrypted. You are to solve this problem for him. You are given sequences ci and bi. You are to find all suitable sequences ai.

Input

The first line contains a single integer n (<image>).

The second line contains n integers b0, b1, ..., bn - 1 (<image>).

The third line contains n integers c0, c1, ..., cn - 1 (<image>).

It is guaranteed that all cyclic shifts of sequence bi are linearly independent.

Output

In the first line print a single integer k — the number of sequences ai, such that after encrypting them with key bi you get the sequence ci.

After that in each of k next lines print n integers a0, a1, ..., an - 1. Print the sequences in lexicographical order.

Note that k could be equal to 0.

Examples

Input

1
1
0


Output

1
1


Input

1
100
81


Output

2
91
109


Input

3
1 1 3
165 185 197


Output

2
-6 -9 -1
8 5 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike has a string s consisting of only lowercase English letters. He wants to change exactly one character from the string so that the resulting one is a palindrome. 

A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

Input

The first and single line contains string s (1 ≤ |s| ≤ 15).

Output

Print "YES" (without quotes) if Mike can change exactly one character so that the resulting string is palindrome or "NO" (without quotes) otherwise. 

Examples

Input

abccaa


Output

YES


Input

abbcca


Output

NO


Input

abcda


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set Y of n distinct positive integers y_1, y_2, ..., y_{n}.

Set X of n distinct positive integers x_1, x_2, ..., x_{n} is said to generate set Y if one can transform X to Y by applying some number of the following two operation to integers in X:  Take any integer x_{i} and multiply it by two, i.e. replace x_{i} with 2·x_{i}.  Take any integer x_{i}, multiply it by two and add one, i.e. replace x_{i} with 2·x_{i} + 1. 

Note that integers in X are not required to be distinct after each operation.

Two sets of distinct integers X and Y are equal if they are equal as sets. In other words, if we write elements of the sets in the array in the increasing order, these arrays would be equal.

Note, that any set of integers (or its permutation) generates itself.

You are given a set Y and have to find a set X that generates Y and the maximum element of X is mininum possible.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 50 000) — the number of elements in Y.

The second line contains n integers y_1, ..., y_{n} (1 ≤ y_{i} ≤ 10^9), that are guaranteed to be distinct.


-----Output-----

Print n integers — set of distinct integers that generate Y and the maximum element of which is minimum possible. If there are several such sets, print any of them.


-----Examples-----
Input
5
1 2 3 4 5

Output
4 5 2 3 1 

Input
6
15 14 3 13 1 12

Output
12 13 14 7 3 1 

Input
6
9 7 13 17 5 11

Output
4 5 2 6 3 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ever since Kalevitch, a famous Berland abstractionist, heard of fractals, he made them the main topic of his canvases. Every morning the artist takes a piece of graph paper and starts with making a model of his future canvas. He takes a square as big as n × n squares and paints some of them black. Then he takes a clean square piece of paper and paints the fractal using the following algorithm: 

Step 1. The paper is divided into n2 identical squares and some of them are painted black according to the model.

Step 2. Every square that remains white is divided into n2 smaller squares and some of them are painted black according to the model.

Every following step repeats step 2.

<image>

Unfortunately, this tiresome work demands too much time from the painting genius. Kalevitch has been dreaming of making the process automatic to move to making 3D or even 4D fractals.

Input

The first line contains integers n and k (2 ≤ n ≤ 3, 1 ≤ k ≤ 5), where k is the amount of steps of the algorithm. Each of the following n lines contains n symbols that determine the model. Symbol «.» stands for a white square, whereas «*» stands for a black one. It is guaranteed that the model has at least one white square. 

Output

Output a matrix nk × nk which is what a picture should look like after k steps of the algorithm.

Examples

Input

2 3
.*
..


Output

.*******
..******
.*.*****
....****
.***.***
..**..**
.*.*.*.*
........


Input

3 2
.*.
***
.*.


Output

.*.***.*.
*********
.*.***.*.
*********
*********
*********
.*.***.*.
*********
.*.***.*.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a following process. 

There is a platform with $n$ columns. $1 \times 1$ squares are appearing one after another in some columns on this platform. If there are no squares in the column, a square will occupy the bottom row. Otherwise a square will appear at the top of the highest square of this column. 

When all of the $n$ columns have at least one square in them, the bottom row is being removed. You will receive $1$ point for this, and all the squares left will fall down one row. 

You task is to calculate the amount of points you will receive.

Input Specification:
The first line of input contain 2 integer numbers $n$ and $m$ ($1 \le n, m \le 1000$) — the length of the platform and the number of the squares.

The next line contain $m$ integer numbers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n$) — column in which $i$-th square will appear.

Output Specification:
Print one integer — the amount of points you will receive.

Demo Input:
['3 9\n1 1 2 2 2 3 1 2 3\n']

Demo Output:
['2\n']

Note:
In the sample case the answer will be equal to $2$ because after the appearing of $6$-th square will be removed one row (counts of the squares on the platform will look like $[2~ 3~ 1]$, and after removing one row will be $[1~ 2~ 0]$).

After the appearing of $9$-th square counts will be $[2~ 3~ 1]$, and after removing one row it will look like $[1~ 2~ 0]$.

So the answer will be equal to $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a nearby village, the postman, milkman and garbage man face the same problem morning after morning: house 18. House 18 is guarded by two dogs that often cause problems. What they don’t know is that the dogs’ behaviour is completely predictable.

When the day starts, one dog is aggressive for $A$ minutes and is then calm for $B$ minutes. Similarly, the other dog is aggressive for $C$ minutes, then calm for $D$ minutes. Both dogs repeat their behaviours indefinitely, starting a new aggressive period after the calm period, then another calm period etc.

Given the arrival times of the postman, milkman and garbage man, determine how many dogs (none, one or both) attack each of them.

-----Input-----
The first line of input contains the integers $A$, $B$, $C$ and $D$.

The second line contains the integer $P$, $M$ and $G$, the minute in the day during which the postman, milkman and garbage man arrive at house 18. For example, if $P$ is 3, it should be interpreted as "the postman arrived sometime during the third minute in the day".

All numbers in the input will be between 1 and 999.

-----Output-----
Output should consist of three lines; each containing ’both’, ’one’ or ’none’, depending on how many dogs attack each of our heroes.

-----Examples-----
Sample Input:
2 2 3 3
1 3 4
Sample Output:
both
one
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given Q queries of the form (L, R). 

For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = a^{p}.


-----Input-----

The first line contains the number of queries Q (1 ≤ Q ≤ 10^5).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 10^18).


-----Output-----

Output Q lines — the answers to the queries.


-----Example-----
Input
6
1 4
9 9
5 7
12 29
137 591
1 1000000

Output
2
1
0
3
17
1111



-----Note-----

In query one the suitable numbers are 1 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two positive integers N and M, let S denote the set of all the arrays of size N such that each element of the array lies in the range [1, M]. Since there are M^{N} such arrays, the size of S is M^{N}.

Let X_{i} denote the [bitwise AND] of all elements of the i^{th} array in the set, where 1 ≤ i ≤ M^{N}.  
Find the value \sum_{i = 1}^{M^{N}} X_{i}. Since the answer can be huge, output the answer modulo 998244353.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two integers N and M, the size of the array, and the maximum limit of elements.

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

For each test case, print the value \sum_{i = 1}^{M^{N}} X_{i}. Since the answer can be huge, output the answer modulo 998244353.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2\cdot10^{5}$
$1 ≤ M ≤ 10^{9}$

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

----- Sample Output 1 ------ 
3
12
----- explanation 1 ------ 
Test case $1$: The set $S$ contains $\{[1,1], [1,2], [2,1], [2,2]\}$. The array $X = [1\& 1, 1\& 2, 2\& 1, 2\& 2] = [1, 0, 0, 2]$. Thus, sum of all elements of $X$ is $1+0+0+2 = 3$.

Test case $2$: The set $S$ contains $\{[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]\}$. The array $X = [1\& 1, 1\& 2, 1\& 3, 2\& 1, 2\& 2, 2\& 3, 3\& 1, 3\& 2, 3\& 3] = [1, 0, 1, 0, 2, 2, 1, 2, 3]$. Thus, sum of all elements of $X$ is $12$.

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