vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.

You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:

  1. Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
  2. Count how many numbers equal to k are on the segment from l to r (both borders inclusive). 



Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.

As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.

To decode the queries from the data given in input, you need to perform the following transformations:

li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.

Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.

Output

For each query of the 2-nd type print the answer on a single line.

Examples

Input

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


Output

2
1
0
0


Input

8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5


Output

2
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.

To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi's sequence has been broken for a long time, but now Kaiki provides an opportunity.

Hitagi's sequence a has a length of n. Lost elements in it are denoted by zeros. Kaiki provides another sequence b, whose length k equals the number of lost elements in a (i.e. the number of zeros). Hitagi is to replace each zero in a with an element from b so that each element in b should be used exactly once. Hitagi knows, however, that, apart from 0, no integer occurs in a and b more than once in total.

If the resulting sequence is not an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki's sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in a with an integer from b so that each integer from b is used exactly once, and the resulting sequence is not increasing.


-----Input-----

The first line of input contains two space-separated positive integers n (2 ≤ n ≤ 100) and k (1 ≤ k ≤ n) — the lengths of sequence a and b respectively.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 200) — Hitagi's broken sequence with exactly k zero elements.

The third line contains k space-separated integers b_1, b_2, ..., b_{k} (1 ≤ b_{i} ≤ 200) — the elements to fill into Hitagi's sequence.

Input guarantees that apart from 0, no integer occurs in a and b more than once in total.


-----Output-----

Output "Yes" if it's possible to replace zeros in a with elements in b and make the resulting sequence not increasing, and "No" otherwise.


-----Examples-----
Input
4 2
11 0 0 14
5 4

Output
Yes

Input
6 1
2 3 0 8 9 10
5

Output
No

Input
4 1
8 94 0 4
89

Output
Yes

Input
7 7
0 0 0 0 0 0 0
1 2 3 4 5 6 7

Output
Yes



-----Note-----

In the first sample:   Sequence a is 11, 0, 0, 14.  Two of the elements are lost, and the candidates in b are 5 and 4.  There are two possible resulting sequences: 11, 5, 4, 14 and 11, 4, 5, 14, both of which fulfill the requirements. Thus the answer is "Yes". 

In the second sample, the only possible resulting sequence is 2, 3, 5, 8, 9, 10, which is an increasing sequence and therefore invalid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a fraction $\frac{a}{b}$. You need to find the first occurrence of digit c into decimal notation of the fraction after decimal point.


-----Input-----

The first contains three single positive integers a, b, c (1 ≤ a < b ≤ 10^5, 0 ≤ c ≤ 9).


-----Output-----

Print position of the first occurrence of digit c into the fraction. Positions are numbered from 1 after decimal point. It there is no such position, print -1.


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

Output
2
Input
2 3 7

Output
-1


-----Note-----

The fraction in the first example has the following decimal notation: $\frac{1}{2} = 0.500(0)$. The first zero stands on second position.

The fraction in the second example has the following decimal notation: $\frac{2}{3} = 0.666(6)$. There is no digit 7 in decimal notation of the fraction.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20&gt;10$, $40&gt;20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input Specification:
The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.

Output Specification:
Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.

Demo Input:
['7\n10 1 1 1 5 5 3\n', '5\n1 1 1 1 1\n']

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

Note:
In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string, consisting of lowercase Latin letters.

A pair of neighbouring letters in a string is considered ugly if these letters are also neighbouring in a alphabet. For example, string "abaca" contains ugly pairs at positions (1, 2) — "ab" and (2, 3) — "ba". Letters 'a' and 'z' aren't considered neighbouring in a alphabet.

Can you rearrange the letters of a given string so that there are no ugly pairs? You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

You also have to answer T separate queries.

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of queries.

Each of the next T lines contains string s (1 ≤ |s| ≤ 100) — the string for the next query. It is guaranteed that it contains only lowercase Latin letters.

Note that in hacks you have to set T = 1.

Output

Print T lines. The i-th line should contain the answer to the i-th query.

If the answer for the i-th query exists, then print such a rearrangment of letters of the given string that it contains no ugly pairs. You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

Otherwise print "No answer" for that query.

Example

Input


4
abcd
gg
codeforces
abaca


Output


cadb
gg
codfoerces
No answer

Note

In the first example answer "bdac" is also correct.

The second example showcases the fact that only neighbouring in alphabet letters are not allowed. The same letter is ok.

There are lots of valid answers for the third example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# How many ways can you make the sum of a number?

From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)#

>In number theory and combinatorics, a partition of a positive integer *n*, also called an *integer partition*, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:
```
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
```

## Examples

### Basic

```python
exp_sum(1) # 1
exp_sum(2) # 2  -> 1+1 , 2
exp_sum(3) # 3 -> 1+1+1, 1+2, 3
exp_sum(4) # 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
exp_sum(5) # 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3

exp_sum(10) # 42
```

### Explosive

```python
exp_sum(50) # 204226
exp_sum(80) # 15796476
exp_sum(100) # 190569292
```

See [here](http://www.numericana.com/data/partition.htm) for more examples.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Eleven wants to choose a new name for herself. As a bunch of geeks, her friends suggested an algorithm to choose a name for her. Eleven wants her name to have exactly *n* characters. 

Her friend suggested that her name should only consist of uppercase and lowercase letters 'O'. More precisely, they suggested that the *i*-th letter of her name should be 'O' (uppercase) if *i* is a member of Fibonacci sequence, and 'o' (lowercase) otherwise. The letters in the name are numbered from 1 to *n*. Fibonacci sequence is the sequence *f* where
 -  *f*1<==<=1, -  *f*2<==<=1, -  *f**n*<==<=*f**n*<=-<=2<=+<=*f**n*<=-<=1 (*n*<=&gt;<=2). 
As her friends are too young to know what Fibonacci sequence is, they asked you to help Eleven determine her new name.

Input Specification:
The first and only line of input contains an integer *n* (1<=≤<=*n*<=≤<=1000).

Output Specification:
Print Eleven's new name on the first and only line of output.

Demo Input:
['8\n', '15\n']

Demo Output:
['OOOoOooO\n', 'OOOoOooOooooOoo\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dhoni wants to collect sticks for making them as stumps for the T20 cricket matches. Now he visits a shop to buy some. 
The shopkeeper gave him a data of the available sticks in the form of N equations of lines (A.x + B.y + C = 0) which are laid down in the 2D floor of the shop. As the sticks used for making stumps must all be parallel to each other, 
Dhoni wants to know the size of largest group of distinct (if two sticks coincide, then count them as one) sticks he can buy such that all the sticks in the group are parallel to one another.

INPUT 
The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N denoting number of stumps.
Next N lines contain 3 space-separated integers each denoting coefficients A, B and C respectively.

OUTPUT
For each test case output the size of largest group of parallel sticks in a single line.

CONSTRAINS 
Sum of N over all test case is less than 10^7.
|A|,|B|,|C| ≤ 10^18.
1 ≤ N ≤ 10^6.
A and B can't be zero at the same time.
-All selected sticks must be in parallel but they need not to have the same distance between them.

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

SAMPLE OUTPUT
2

Explanation

Sticks with eqn. 1.x+3.y+0=0 and 2.x+6.y+2=0 forms the largest group of parallel lines.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ of length $2n$. Consider a partition of array $a$ into two subsequences $p$ and $q$ of length $n$ each (each element of array $a$ should be in exactly one subsequence: either in $p$ or in $q$).

Let's sort $p$ in non-decreasing order, and $q$ in non-increasing order, we can denote the sorted versions by $x$ and $y$, respectively. Then the cost of a partition is defined as $f(p, q) = \sum_{i = 1}^n |x_i - y_i|$.

Find the sum of $f(p, q)$ over all correct partitions of array $a$. Since the answer might be too big, print its remainder modulo $998244353$.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 150\,000$).

The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \leq a_i \leq 10^9$) — elements of array $a$.


-----Output-----

Print one integer — the answer to the problem, modulo $998244353$.


-----Examples-----
Input
1
1 4

Output
6
Input
2
2 1 2 1

Output
12
Input
3
2 2 2 2 2 2

Output
0
Input
5
13 8 35 94 9284 34 54 69 123 846

Output
2588544


-----Note-----

Two partitions of an array are considered different if the sets of indices of elements included in the subsequence $p$ are different.

In the first example, there are two correct partitions of the array $a$:  $p = [1]$, $q = [4]$, then $x = [1]$, $y = [4]$, $f(p, q) = |1 - 4| = 3$;  $p = [4]$, $q = [1]$, then $x = [4]$, $y = [1]$, $f(p, q) = |4 - 1| = 3$. 

In the second example, there are six valid partitions of the array $a$:   $p = [2, 1]$, $q = [2, 1]$ (elements with indices $1$ and $2$ in the original array are selected in the subsequence $p$);  $p = [2, 2]$, $q = [1, 1]$;  $p = [2, 1]$, $q = [1, 2]$ (elements with indices $1$ and $4$ are selected in the subsequence $p$);  $p = [1, 2]$, $q = [2, 1]$;  $p = [1, 1]$, $q = [2, 2]$;  $p = [2, 1]$, $q = [2, 1]$ (elements with indices $3$ and $4$ are selected in the subsequence $p$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
Consider a list (list = []). You can perform the following commands:
1. insert i e: Insert integer e at position i.
2. print: Print the list.
3. remove e: Delete the first occurrence of integer e.
4. append e: Insert integer e at the end of the list.
5. sort: Sort the list.
6. pop: Pop the last element from the list.
7. reverse: Reverse the list.
Initialize your list and read in the value of n followed by n lines of commands where each command will be 7 of the types listed above. Iterate through each command in order and perform the corresponding operation on your list.

=====Example=====
N = 4
append 1
append 2
insert 3 1
print
append 1: Append 1 to the list, arr = [1].
append 2: Append 2 to the list, arr = [1,2].
insert 3 1: Insert 3 at index 1, arr = [1,3,2].
print: Print the array
Output:
[1, 3, 2]

=====Input Format=====
The first line contains an integer, n, denoting the number of commands. Each line i of the subsequent n lines contains one of the commands described above.

=====Constraints=====
The elements added to the list must be integers

=====Output Format=====
For each command of type print, print the list on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
F - Point Distance

Problem Statement

You work for invention center as a part time programmer. This center researches movement of protein molecules. It needs how molecules make clusters, so it will calculate distance of all pair molecules and will make a histogram. Molecules’ positions are given by a N x N grid map. Value C_{xy} of cell (x, y) in a grid map means that C_{xy} molecules are in the position (x, y).

You are given a grid map, please calculate histogram of all pair molecules.

Input

Input is formatted as follows.


N
C_{11} C_{12} ... C_{1N}
C_{21} C_{22} ... C_{2N}
...
C_{N1} C_{N2} ... C_{NN}


First line contains the grid map size N (1 \leq N \leq 1024). Each next N line contains N numbers. Each numbers C_{xy} (0 \leq C_{xy} \leq 9) means the number of molecule in position (x,y). There are at least 2 molecules.

Output

Output is formatted as follows.


D_{ave}
d_{1} c_{1}
d_{2} c_{2}
...
d_{m} c_{m}


Print D_{ave} which an average distance of all pair molecules on first line. Next, print histogram of all pair distance. Each line contains a distance d_i and the number of pair molecules c_i(0 \lt c_i). The distance d_i should be calculated by squared Euclidean distance and sorted as increasing order. If the number of different distance is more than 10,000, please show the first 10,000 lines. The answer may be printed with an arbitrary number of decimal digits, but may not contain an absolute or relative error greater than or equal to 10^{-8}.

Sample Input 1


2
1 0
0 1


Output for the Sample Input 1


1.4142135624
2 1


Sample Input 2


3
1 1 1
1 1 1
1 1 1


Output for the Sample Input 2


1.6349751825
1 12
2 8
4 6
5 8
8 2


Sample Input 3


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


Output for the Sample Input 3


1.8589994382
0 125
1 379
2 232
4 186
5 200
8 27
9 111
10 98
13 21
16 50
17 37
18 6
20 7
25 6






Example

Input

2
1 0
0 1


Output

1.4142135624
2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon saw a large integer x written on the ground and wants to print its binary form out. Dreamoon has accomplished the part of turning x into its binary format. Now he is going to print it in the following manner.

He has an integer n = 0 and can only perform the following two operations in any order for unlimited times each:

  1. Print n in binary form without leading zeros, each print will append to the right of previous prints. 
  2. Increase n by 1. 



Let's define an ideal sequence as a sequence of operations that can successfully print binary representation of x without leading zeros and ends with a print operation (i.e. operation 1). Dreamoon wants to know how many different ideal sequences are there and the length (in operations) of the shortest ideal sequence.

The answers might be large so please print them modulo 1000000007 (109 + 7).

Let's define the string representation of an ideal sequence as a string of '1' and '2' where the i-th character in the string matches the i-th operation performed. Two ideal sequences are called different if their string representations are different.

Input

The single line of the input contains a binary integer representing x (1 ≤ x < 25000) without leading zeros.

Output

The first line of the output should contain an integer representing the number of different ideal sequences modulo 1000000007 (109 + 7).

The second line of the output contains an integer representing the minimal length of an ideal sequence modulo 1000000007 (109 + 7).

Examples

Input

101


Output

1
6


Input

11010


Output

3
5

Note

For the first sample, the shortest and the only ideal sequence is «222221» of length 6.

For the second sample, there are three ideal sequences «21211», «212222222221», «222222222222222222222222221». Among them the shortest one has length 5.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Several ages ago Berland was a kingdom. The King of Berland adored math. That's why, when he first visited one of his many palaces, he first of all paid attention to the floor in one hall. The floor was tiled with hexagonal tiles.

The hall also turned out hexagonal in its shape. The King walked along the perimeter of the hall and concluded that each of the six sides has *a*, *b*, *c*, *a*, *b* and *c* adjacent tiles, correspondingly.

To better visualize the situation, look at the picture showing a similar hexagon for *a*<==<=2, *b*<==<=3 and *c*<==<=4.

According to the legend, as the King of Berland obtained the values *a*, *b* and *c*, he almost immediately calculated the total number of tiles on the hall floor. Can you do the same?

Input Specification:
The first line contains three integers: *a*, *b* and *c* (2<=≤<=*a*,<=*b*,<=*c*<=≤<=1000).

Output Specification:
Print a single number — the total number of tiles on the hall floor.

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

Demo Output:
['18']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

The GCD of a group of integers is the largest non-negative integer that divides all the integers in the group.

Both groups have to be non-empty.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the elements of the array.

Output

In the first line print "YES" (without quotes), if it is possible to split the integers into two groups as required, and "NO" (without quotes) otherwise.

If it is possible to split the integers, in the second line print n integers, where the i-th integer is equal to 1 if the integer a_i should be in the first group, and 2 otherwise.

If there are multiple solutions, print any.

Examples

Input


4
2 3 6 7


Output


YES
2 2 1 1 


Input


5
6 15 35 77 22


Output


YES
2 1 2 1 1 


Input


5
6 10 15 1000 75


Output


NO

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