vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is an easy version of the problem. In this version, all numbers in the given array are distinct and the constraints on $n$ are less than in the hard version of the problem.

You are given an array $a$ of $n$ integers (there are no equals elements in the array). You can perform the following operations on array elements:  choose any index $i$ ($1 \le i \le n$) and move the element $a[i]$ to the begin of the array;  choose any index $i$ ($1 \le i \le n$) and move the element $a[i]$ to the end of the array. 

For example, if $n = 5$, $a = [4, 7, 2, 3, 9]$, then the following sequence of operations can be performed:   after performing the operation of the first type to the second element, the array $a$ will become $[7, 4, 2, 3, 9]$;  after performing the operation of the second type to the second element, the array $a$ will become $[7, 2, 3, 9, 4]$. 

You can perform operations of any type any number of times in any order.

Find the minimum total number of operations of the first and second type that will make the $a$ array sorted in non-decreasing order. In other words, what is the minimum number of operations that must be performed so the array satisfies the inequalities $a[1] \le a[2] \le \ldots \le a[n]$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 3000$) — length of the array $a$.

Then follow $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — an array that needs to be sorted by the given operations. All numbers in the given array are distinct.

The sum of $n$ for all test cases in one test does not exceed $3000$.


-----Output-----

For each test case output one integer — the minimum total number of operations of the first and second type, which will make the array sorted in non-decreasing order.


-----Example-----
Input
4
5
4 7 2 3 9
5
3 5 8 1 7
5
1 4 5 7 12
4
0 2 1 3

Output
2
2
0
2



-----Note-----

In the first test case, you first need to move 3, and then 2 to the beginning of the array. Therefore, the desired sequence of operations: $[4, 7, 2, 3, 9] \rightarrow [3, 4, 7, 2, 9] \rightarrow [2, 3, 4, 7, 9]$.

In the second test case, you need to move the 1 to the beginning of the array, and the 8 — to the end. Therefore, the desired sequence of operations: $[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$.

In the third test case, the array is already sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# # Task:
  * #### Complete the pattern, using the special character ```■   □```
  * #### In this kata, we draw some histogram of the sound performance of ups and downs.

# # Rules:
  -  parameter ```waves```  The value of sound waves, an array of number, all number in array >=0.
  -  return a string, ```■``` represents the sound waves, and ```□``` represents the blank part, draw the histogram from bottom to top.

# # Example:

```
draw([1,2,3,4])

□□□■
□□■■
□■■■
■■■■

draw([1,2,3,3,2,1])

□□■■□□
□■■■■□
■■■■■■

draw([1,2,3,3,2,1,1,2,3,4,5,6,7])

□□□□□□□□□□□□■
□□□□□□□□□□□■■
□□□□□□□□□□■■■
□□□□□□□□□■■■■
□□■■□□□□■■■■■
□■■■■□□■■■■■■
■■■■■■■■■■■■■


draw([5,3,1,2,4,6,5,4,2,3,5,2,1])

□□□□□■□□□□□□□
■□□□□■■□□□■□□
■□□□■■■■□□■□□
■■□□■■■■□■■□□
■■□■■■■■■■■■□
■■■■■■■■■■■■■

draw([1,0,1,0,1,0,1,0])

■□■□■□■□
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Rohu from Pluto is the best bomb defusor on the entire planet. She has saved the planet from getting destruced multiple times now. Of course, she's proud of her achievments. But, to prepare herself for more complicated situations, she keeps challenging herself to handle tricky tasks.
Her current challenge involves the following things:
- A square matrix of the form N*N.  
- B bombs planted at various cells of the square matrix.
- There can be multiple bombs at a given cell. 
- Only the four corners of the square matrix have a bomb defusor, so if a bomb is moved to any one of the four corners, it will be defused.

From a given cell, any bomb can be moved in all the four directions, North, South, East, West respectively.

Rohu is given the number of bombs and the dimensions of the square matrix she's going to be dealing with, you've to help her figure out the minimum number of moves required to defuse all the bombs.

Note-1: She's not going to enter the matrix, she's just going to move the bombs from outside. 
Note-2: The matrix is 1-indexed. 

-----Input-----
- The first line of each test case contains two integers N, denoting the dimension of the square matrix, and B denoting the number of bombs. This will be followed by two lines, where the first line will denote the x-coordinate of all the bombs, and the second line will denote the y-coordinate of all the bombs. x[0], y[0] will be the position of the first bomb, ... , x[B-1], y[B-1] will be the position of the Bth bomb.

-----Output-----
- Output a single line containing the minimum number of moves required.

-----Subtasks-----
- 1 ≤ N, B ≤ 100000: 50 points

- 1 ≤ N, B ≤ 1000: 30 points

- 1 ≤ N, B ≤ 10: 20 points

-----Constraints-----
- 1 ≤ N, B ≤ 100000

-----Example 1-----
Input:
3 3
1 2 3
3 2 1

Output:
2

-----Example 2-----
Input:
2 1
1
1

Output:
0

-----Explanation-----
Example case 1:Only the bomb at {2,2} needs to be moved in two steps.
Example case 2:No bomb needs to be moved anywhere.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is war and ashu needs hog riders for the fight. The area on which hog riders live is a N X N square matrix. If A[i][j] = 1 it means a hog rider is standing at that place and if it is 0 then the place is empty. To call them ashu stands on any tile on which a hog is present  and makes that particular hog shout loud. All the hog riders standing adjacent to the tile where one shouts listen and they also start shouting so again those hogs which are connected to them also starts shouting and calling others for war. So you have to output the best position where ashu should go so that maximum hog riders will attend the war. 
Adjacent to a tile means tiles which lie on above,below,left and right of that tile. Ashu can't stand on a tile which is empty or else he has to make the noise which is not  possible 
Input
First line contains N as input which is size of matrix. Next N lines contain N integers as 0 or 1 indicating gaps and hogs
Output
You have to output the maximum number of hogs that can be called
Scoring
1≤ N ≤ 10      20pts
1≤ N ≤ 100    40pts
1≤ N ≤ 1000  40pts

SAMPLE INPUT
3
1 1 1
1 0 0
0 1 1

SAMPLE OUTPUT
4

Explanation

If ashu stands at any of the first four cells then 4 hogs will come for war

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dasha logged into the system and began to solve problems. One of them is as follows:

Given two sequences a and b of length n each you need to write a sequence c of length n, the i-th element of which is calculated as follows: ci = bi - ai.

About sequences a and b we know that their elements are in the range from l to r. More formally, elements satisfy the following conditions: l ≤ ai ≤ r and l ≤ bi ≤ r. About sequence c we know that all its elements are distinct.

<image>

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy. Due to an error in the test system only the sequence a and the compressed sequence of the sequence c were known from that test.

Let's give the definition to a compressed sequence. A compressed sequence of sequence c of length n is a sequence p of length n, so that pi equals to the number of integers which are less than or equal to ci in the sequence c. For example, for the sequence c = [250, 200, 300, 100, 50] the compressed sequence will be p = [4, 3, 5, 2, 1]. Pay attention that in c all integers are distinct. Consequently, the compressed sequence contains all integers from 1 to n inclusively.

Help Dasha to find any sequence b for which the calculated compressed sequence of sequence c is correct.

Input

The first line contains three integers n, l, r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109) — the length of the sequence and boundaries of the segment where the elements of sequences a and b are.

The next line contains n integers a1, a2, ..., an (l ≤ ai ≤ r) — the elements of the sequence a.

The next line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the compressed sequence of the sequence c.

Output

If there is no the suitable sequence b, then in the only line print "-1".

Otherwise, in the only line print n integers — the elements of any suitable sequence b.

Examples

Input

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


Output

3 1 5 4 2 

Input

4 2 9
3 4 8 9
3 2 1 4


Output

2 2 2 9 

Input

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


Output

-1

Note

Sequence b which was found in the second sample is suitable, because calculated sequence c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1, - 2, - 6, 0] (note that ci = bi - ai) has compressed sequence equals to p = [3, 2, 1, 4].

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input consists of four lines, each line containing a single digit 0 or 1.

Output Specification:
Output a single digit, 0 or 1.

Demo Input:
['0\n1\n1\n0\n']

Demo Output:
['0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is setting up a perfect bath for himself. He has X litres of hot water and Y litres of cold water.  
The initial temperature of water in his bathtub is A degrees. On mixing water, the temperature of the bathtub changes as following:

The temperature rises by 1 degree on mixing 1 litre of hot water.
The temperature drops by 1 degree on mixing 1 litre of cold water.

Determine whether he can set the temperature to B degrees for a perfect bath.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of four space-separated integers A, B, X, and Y — the initial temperature of bathtub, the desired temperature of bathtub, the amount of hot water in litres, and the amount of cold water in litres respectively.

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

For each test case, output on a new line, YES if Chef can get the desired temperature for his bath, and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

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

$1 ≤ T ≤ 2000$
$20 ≤ A, B ≤ 40$
$0 ≤ X, Y ≤ 20$

----- Sample Input 1 ------ 
4
24 25 2 0
37 37 2 9
30 20 10 9
30 31 0 20

----- Sample Output 1 ------ 
YES
YES
NO
NO

----- explanation 1 ------ 
Test case $1$: The initial temperature of water is $24$ and the desired temperature is $25$. Chef has $2$ litres of hot water. He can add $1$ litre hot water in the tub and change the temperature to $24+1=25$ degrees.

Test case $2$: The initial temperature of water is $37$ and the desired temperature is also $37$. Thus, Chef does not need to add any more water in the bathtub.

Test case $3$: The initial temperature of water is $30$ and the desired temperature is $20$. Chef needs to add $10$ litres of cold water to reach the desired temperature. Since he only has $9$ litres of cold water, he cannot reach the desired temperature.

Test case $4$: The initial temperature of water is $30$ and the desired temperature is $31$. Chef needs to add $1$ litre of hot water to reach the desired temperature. Since he has no hot water, he cannot reach the desired temperature.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two sorted arrays of distinct elements. There is only 1 difference between the arrays. First array has one element extra added in between. Find the index of the extra element.
Example 1:
Input:
N = 7
A[] = {2,4,6,8,9,10,12}
B[] = {2,4,6,8,10,12}
Output: 4
Explanation: In the second array, 9 is
missing and it's index in the first array
is 4.
Example 2:
Input:
N = 6
A[] = {3,5,7,9,11,13}
B[] = {3,5,7,11,13}
Output: 3
Your Task:
You don't have to take any input. Just complete the provided function findExtra() that takes array A[], B[] and size of A[] and return the valid index (0 based indexing).
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
2<=N<=10^{4}
1<=Ai<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$ consisting of lowercase Latin letters. Let the length of $s$ be $|s|$. You may perform several operations on this string.

In one operation, you can choose some index $i$ and remove the $i$-th character of $s$ ($s_i$) if at least one of its adjacent characters is the previous letter in the Latin alphabet for $s_i$. For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index $i$ should satisfy the condition $1 \le i \le |s|$ during each operation.

For the character $s_i$ adjacent characters are $s_{i-1}$ and $s_{i+1}$. The first and the last characters of $s$ both have only one adjacent character (unless $|s| = 1$).

Consider the following example. Let $s=$ bacabcab.  During the first move, you can remove the first character $s_1=$ b because $s_2=$ a. Then the string becomes $s=$ acabcab.  During the second move, you can remove the fifth character $s_5=$ c because $s_4=$ b. Then the string becomes $s=$ acabab.  During the third move, you can remove the sixth character $s_6=$'b' because $s_5=$ a. Then the string becomes $s=$ acaba.  During the fourth move, the only character you can remove is $s_4=$ b, because $s_3=$ a (or $s_5=$ a). The string becomes $s=$ acaa and you cannot do anything with it. 

Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.


-----Input-----

The first line of the input contains one integer $|s|$ ($1 \le |s| \le 100$) — the length of $s$.

The second line of the input contains one string $s$ consisting of $|s|$ lowercase Latin letters.


-----Output-----

Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.


-----Examples-----
Input
8
bacabcab

Output
4

Input
4
bcda

Output
3

Input
6
abbbbb

Output
5



-----Note-----

The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is $4$.

In the second example, you can remove all but one character of $s$. The only possible answer follows.  During the first move, remove the third character $s_3=$ d, $s$ becomes bca.  During the second move, remove the second character $s_2=$ c, $s$ becomes ba.  And during the third move, remove the first character $s_1=$ b, $s$ becomes a.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fidget spinners are so 2017; this year’s rage are fidget cubes. A fidget cube is a cube with unit side lengths, which you hold in your hand and fidget with. Kids these days, right? 

You work in the planning department for a company that creates and ships fidget cubes. Having done some market analysis, you found that your customers want to receive shipments of exactly $V$ fidget cubes.

This means you have to design a container that will hold exactly $V$ fidget cubes. Since fidget cubes are very fragile, you cannot have any empty space in your container. If there is empty space, they might move around, bump into each other and get damaged. Because of this, you decide to ship the fidget cubes in a rectangular cardboard box.

The cost of a cardboard box is proportional to its surface area, costing exactly one unit of money per square unit of surface area. Of course you want to spend as little money as possible. Subject to the above constraints, how much money do you have to spend on a box for $V$ fidget cubes?

-----Input-----
The input contains a single integer, $1 \leq V \leq 10^6$, the number of fidget cubes for which you need to build a box.

-----Output-----
Print the cost of the cheapest rectangular box as specified in the statement.

-----Examples-----
Sample Input 1:
1
Sample Output 1:
6

Sample Input 2:
4
Sample Output 2:
16

Sample Input 3:
3
Sample Output 3:
14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array consisting of $n$ integers $a_1, a_2, \dots , a_n$ and an integer $x$. It is guaranteed that for every $i$, $1 \le a_i \le x$.

Let's denote a function $f(l, r)$ which erases all values such that $l \le a_i \le r$ from the array $a$ and returns the resulting array. For example, if $a = [4, 1, 1, 4, 5, 2, 4, 3]$, then $f(2, 4) = [1, 1, 5]$.

Your task is to calculate the number of pairs $(l, r)$ such that $1 \le l \le r \le x$ and $f(l, r)$ is sorted in non-descending order. Note that the empty array is also considered sorted.


-----Input-----

The first line contains two integers $n$ and $x$ ($1 \le n, x \le 10^6$) — the length of array $a$ and the upper limit for its elements, respectively.

The second line contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \le a_i \le x$).


-----Output-----

Print the number of pairs $1 \le l \le r \le x$ such that $f(l, r)$ is sorted in non-descending order.


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

Output
4

Input
7 4
1 3 1 2 2 4 3

Output
6



-----Note-----

In the first test case correct pairs are $(1, 1)$, $(1, 2)$, $(1, 3)$ and $(2, 3)$.

In the second test case correct pairs are $(1, 3)$, $(1, 4)$, $(2, 3)$, $(2, 4)$, $(3, 3)$ and $(3, 4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s, consisting of small Latin letters. Let's denote the length of the string as |s|. The characters in the string are numbered starting from 1. 

Your task is to find out if it is possible to rearrange characters in string s so that for any prime number p ≤ |s| and for any integer i ranging from 1 to |s| / p (inclusive) the following condition was fulfilled sp = sp × i. If the answer is positive, find one way to rearrange the characters.

Input

The only line contains the initial string s, consisting of small Latin letters (1 ≤ |s| ≤ 1000).

Output

If it is possible to rearrange the characters in the string so that the above-mentioned conditions were fulfilled, then print in the first line "YES" (without the quotes) and print on the second line one of the possible resulting strings. If such permutation is impossible to perform, then print the single string "NO".

Examples

Input

abc


Output

YES
abc


Input

abcd


Output

NO


Input

xxxyxxx


Output

YES
xxxxxxy

Note

In the first sample any of the six possible strings will do: "abc", "acb", "bac", "bca", "cab" or "cba".

In the second sample no letter permutation will satisfy the condition at p = 2 (s2 = s4).

In the third test any string where character "y" doesn't occupy positions 2, 3, 4, 6 will be valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two exits in a bus with 100 seats:
First exit is located beside seat number 1.
Second exit is located beside seat number 100.

Seats are arranged in a straight line from 1 to 100 with equal spacing between any 2 adjacent seats.

A passenger prefers to choose the nearest exit while leaving the bus.

Determine the exit taken by passenger sitting on seat X.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists a single integer X, denoting the seat number.

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

For each test case, output LEFT if the passenger chooses the exit beside seat 1, RIGHT otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings LEFT, lEft, left, and lEFT will all be treated as identical).

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

$1 ≤ T ≤ 100$
$1 ≤ X ≤ 100$

----- Sample Input 1 ------ 
6
1
50
100
30
51
73

----- Sample Output 1 ------ 
LEFT
LEFT
RIGHT
LEFT
RIGHT
RIGHT

----- explanation 1 ------ 
Test case $1$: The exit is located beside seat $1$. Hence, the passenger can take this exit without moving to any other seat.

Test case $2$: To take exit at seat $1$, the passenger needs to move $49$ seats. However, to take the exit at seat $100$, the passenger needs to move $50$ seats. Thus, exit at seat $1$ is closer.

Test case $3$: The exit is located beside seat $100$. Hence, the passenger can take this exit without moving to any other seat.

Test case $4$: To take exit at seat $1$, the passenger needs to move $29$ seats. However, to take the exit at seat $100$, the passenger needs to move $70$ seats. Thus, exit at seat $1$ is closer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

* For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

* 1 \leq N \leq 3 × 10^5
* 1 \leq A_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1
:
A_N


Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Examples

Input

3
1
2
1


Output

2


Input

5
3
1
4
1
5


Output

0


Input

8
4
4
4
1
1
1
2
2


Output

24


Input

6
1
1
6
2
2
2


Output

0

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