vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The hero is addicted to glory, and is fighting against a monster.

The hero has $n$ skills. The $i$-th skill is of type $a_i$ (either fire or frost) and has initial damage $b_i$.

The hero can perform all of the $n$ skills in any order (with each skill performed exactly once). When performing each skill, the hero can play a magic as follows:

If the current skill immediately follows another skill of a different type, then its damage is doubled.

In other words,

If a skill of type fire and with initial damage $c$ is performed immediately after a skill of type fire, then it will deal $c$ damage;

If a skill of type fire and with initial damage $c$ is performed immediately after a skill of type frost, then it will deal $2c$ damage;

If a skill of type frost and with initial damage $c$ is performed immediately after a skill of type fire, then it will deal $2c$ damage;

If a skill of type frost and with initial damage $c$ is performed immediately after a skill of type frost , then it will deal $c$ damage.

Your task is to find the maximum damage the hero can deal.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$), indicating the number of skills.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 1$), where $a_i$ indicates the type of the $i$-th skill. Specifically, the $i$-th skill is of type fire if $a_i = 0$, and of type frost if $a_i = 1$.

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \leq b_i \leq 10^9$), where $b_i$ indicates the initial damage of the $i$-th skill.

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


-----Output-----

For each test case, output the maximum damage the hero can deal.


-----Examples-----

Input
4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1
Output
2112
63
3000000000
1


-----Note-----

In the first test case, we can order the skills by $[3, 1, 4, 2]$, and the total damage is $100 + 2 \times 1 + 2 \times 1000 + 10 = 2112$.

In the second test case, we can order the skills by $[1, 4, 2, 5, 3, 6]$, and the total damage is $3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63$.

In the third test case, we can order the skills by $[1, 2, 3]$, and the total damage is $1000000000 + 1000000000 + 1000000000 = 3000000000$.

In the fourth test case, there is only one skill with initial damage $1$, so the total damage is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $n$ be a fixed integer. 

A permutation is a bijection from the set $\{1,2,\ldots,n\}$ to itself. 

A cycle of length ${k}$ ($k\geq2$) is a permutation $\mbox{f}$ where different integers exist $i_1,\ldots,i_k$ such that $f(i_1)=i_2,f(i_2)=i_3,...,f(i_k)=i_1$ and, for all $\boldsymbol{x}$ not in $\{i_1,\ldots,i_k\}$, $f(x)=x$.

The composition of $m$ permutations $f_1,\ldots,f_m$, written $f_1\circ f_2\circ\ldots\circ f_m$, is their composition as functions.

Steve has some cycles $f_1,f_2,\ldots,f_m$. He knows the length of cycle $f_i$ is $\mathbf{l}_i$, but he does not know exactly what the cycles are.
He finds that the composition $f_1\circ f_2\circ\ldots\circ f_m$ of the cycles is a cycle of length $n$. 

He wants to know how many possibilities of $f_1,\ldots,f_m$ exist.

Input Format

The first line contains ${T}$, the number of test cases. 

Each test case contains the following information:

The first line of each test case contains two space separated integers, $n$ and $m$.

The second line of each test case contains $m$ integers, $l_1,\ldots,l_m$.

Constraints 

$n\geq2$ 

Sum of $n\leqslant1000$ 

$2\leq l_i\leq n$ 

Sum of $m\leq10^{6}$  

Output Format

Output ${T}$ lines. Each line contains a single integer, the answer to the corresponding test case.

Since the answers may be very large, output them modulo $(10^9+7)$.

Sample Input
1
3 2
2 2

Sample Output
6

Explanation

There are three cycles of length $2$. The composition of two cycles of length $2$ is a cycle of length $3$ if, and only if, the two cycles are different. So, there are $3\cdot2=6$ possibilities.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes a positive integer and returns the next smaller positive integer containing the same digits.

For example:

```python
next_smaller(21) == 12
next_smaller(531) == 513
next_smaller(2071) == 2017
```

Return -1 (for `Haskell`: return `Nothing`, for `Rust`: return `None`), when there is no smaller number that contains the same digits. Also return -1 when the next smaller number with the same digits would require the leading digit to be zero.

```python 
next_smaller(9) == -1
next_smaller(135) == -1
next_smaller(1027) == -1  # 0721 is out since we don't write numbers with leading zeros
```
```ruby 
next_smaller(9) == -1
next_smaller(135) == -1
next_smaller(1027) == -1  # 0721 is out since we don't write numbers with leading zeros
```

 * some tests will include very large numbers.
 * test data only employs positive integers.

*The function you write for this challenge is the inverse of this kata: "[Next bigger number with the same digits](http://www.codewars.com/kata/next-bigger-number-with-the-same-digits)."*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N points on the road ,you can step ahead by 1 or 2 . Find the number of ways you can reach at point N. 
Example 1:
Input: N = 4
Output: 5
Explanation: Three ways to reach at 4th
point. They are {1, 1, 1, 1}, {1, 1, 2},
{1, 2, 1} {2, 1, 1}, {2, 2}.
Example 2:
Input: N = 5
Output: 8
Explanation: Three ways to reach at 5th
point. They are {1, 1, 1, 1, 1},
{1, 1, 1, 2}, {1, 1, 2, 1}, {1, 2, 1, 1},
{2, 1, 1, 1}{1, 2, 2}, {2, 1, 2}, {2, 2, 1}
Your Task:
You don't need to read or print anyhting. Your task is to complete the function nthPoint() which takes N as input parameter and returns the total number of ways modulo 10^{9} + 7 to reach at Nth point.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 ≤ N ≤ 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers `a` and `b` (`a < b <= 20000`). Complete the function which returns a list of all those numbers in the interval `[a, b)` whose digits are made up of prime numbers (`2, 3, 5, 7`) but which are not primes themselves.


Be careful about your timing!


Good luck :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given set of two-dimensional points S, let's denote its extension E(S) as the result of the following algorithm:

Create another set of two-dimensional points R, which is initially equal to S. Then, while there exist four numbers x_1, y_1, x_2 and y_2 such that (x_1, y_1) ∈ R, (x_1, y_2) ∈ R, (x_2, y_1) ∈ R and (x_2, y_2) ∉ R, add (x_2, y_2) to R. When it is impossible to find such four integers, let R be the result of the algorithm.

Now for the problem itself. You are given a set of two-dimensional points S, which is initially empty. You have to process two types of queries: add some point to S, or remove some point from it. After each query you have to compute the size of E(S).

Input

The first line contains one integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Then q lines follow, each containing two integers x_i, y_i (1 ≤ x_i, y_i ≤ 3 ⋅ 10^5), denoting i-th query as follows: if (x_i, y_i) ∈ S, erase it from S, otherwise insert (x_i, y_i) into S.

Output

Print q integers. i-th integer should be equal to the size of E(S) after processing first i queries.

Example

Input


7
1 1
1 2
2 1
2 2
1 2
1 3
2 1


Output


1 2 4 4 4 6 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Vasya had n boxes with balls in the room. The boxes stood in a row and were numbered with numbers from 1 to n from left to right.

Once Vasya chose one of the boxes, let's assume that its number is i, took all balls out from it (it is guaranteed that this box originally had at least one ball), and began putting balls (one at a time) to the boxes with numbers i + 1, i + 2, i + 3 and so on. If Vasya puts a ball into the box number n, then the next ball goes to box 1, the next one goes to box 2 and so on. He did it until he had no balls left in his hands. It is possible that Vasya puts multiple balls to the same box, and it is also possible that one or more balls will go to the box number i. If i = n, Vasya puts the first ball into the box number 1, then the next ball goes to box 2 and so on. 

For example, let's suppose that initially Vasya had four boxes, and the first box had 3 balls, the second one had 2, the third one had 5 and the fourth one had 4 balls. Then, if i = 3, then Vasya will take all five balls out of the third box and put them in the boxes with numbers: 4, 1, 2, 3, 4. After all Vasya's actions the balls will lie in the boxes as follows: in the first box there are 4 balls, 3 in the second one, 1 in the third one and 6 in the fourth one.

At this point Vasya has completely forgotten the original arrangement of the balls in the boxes, but he knows how they are arranged now, and the number x — the number of the box, where he put the last of the taken out balls.

He asks you to help to find the initial arrangement of the balls in the boxes.


-----Input-----

The first line of the input contains two integers n and x (2 ≤ n ≤ 10^5, 1 ≤ x ≤ n), that represent the number of the boxes and the index of the box that got the last ball from Vasya, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n}, where integer a_{i} (0 ≤ a_{i} ≤ 10^9, a_{x} ≠ 0) represents the number of balls in the box with index i after Vasya completes all the actions. 

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print n integers, where the i-th one represents the number of balls in the box number i before Vasya starts acting. Separate the numbers in the output by spaces. If there are multiple correct solutions, you are allowed to print any of them.


-----Examples-----
Input
4 4
4 3 1 6

Output
3 2 5 4 
Input
5 2
3 2 0 2 7

Output
2 1 4 1 6 
Input
3 3
2 3 1

Output
1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$-periodic and $k$ divides $n+1$. In other words, for each $k \leq i \leq n$ it's satisfied that $s_{i} = s_{i - k}$.

Find out the non-negative remainder of division of $\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ by $10^{9} + 9$.

Note that the modulo is unusual!


-----Input-----

The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$.

The second line contains a sequence of length $k$ consisting of characters '+' and '-'. 

If the $i$-th character (0-indexed) is '+', then $s_{i} = 1$, otherwise $s_{i} = -1$.

Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property.


-----Output-----

Output a single integer — value of given expression modulo $10^{9} + 9$.


-----Examples-----
Input
2 2 3 3
+-+

Output
7

Input
4 1 5 1
-

Output
999999228



-----Note-----

In the first example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

In the second example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $n$.

Let $S(x)$ be sum of digits in base 10 representation of $x$, for example, $S(123) = 1 + 2 + 3 = 6$, $S(0) = 0$.

Your task is to find two integers $a, b$, such that $0 \leq a, b \leq n$, $a + b = n$ and $S(a) + S(b)$ is the largest possible among all such pairs.


-----Input-----

The only line of input contains an integer $n$ $(1 \leq n \leq 10^{12})$.


-----Output-----

Print largest $S(a) + S(b)$ among all pairs of integers $a, b$, such that $0 \leq a, b \leq n$ and $a + b = n$.


-----Examples-----
Input
35

Output
17

Input
10000000000

Output
91



-----Note-----

In the first example, you can choose, for example, $a = 17$ and $b = 18$, so that $S(17) + S(18) = 1 + 7 + 1 + 8 = 17$. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, $a = 5000000001$ and $b = 4999999999$, with $S(5000000001) + S(4999999999) = 91$. It can be shown that it is impossible to get a larger answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, find two permutations:

  1. Permutation p of numbers from 1 to N such that pi ≠ i and pi & i = 0 for all i = 1, 2, ..., N. 
  2. Permutation q of numbers from 1 to N such that qi ≠ i and qi & i ≠ 0 for all i = 1, 2, ..., N. 



& is the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

Input

The input consists of one line containing a single integer N (1 ≤ N ≤ 105).

Output

For each subtask, if the required permutation doesn't exist, output a single line containing the word "NO"; otherwise output the word "YES" in the first line and N elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them.

Examples

Input

3


Output

NO
NO


Input

6


Output

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between the easy and the hard version is the limit to the number of queries.

This is an interactive problem.

There is an array a of n different numbers. In one query you can ask the position of the second maximum element in a subsegment a[l..r]. Find the position of the maximum element in the array in no more than 20 queries.

A subsegment a[l..r] is all the elements a_l, a_{l + 1}, ..., a_r. After asking this subsegment you will be given the position of the second maximum from this subsegment in the whole array.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of elements in the array.

Interaction

You can ask queries by printing "? l r" (1 ≤ l < r ≤ n). The answer is the index of the second maximum of all elements a_l, a_{l + 1}, ..., a_r. Array a is fixed beforehand and can't be changed in time of interaction.

You can output the answer by printing "! p", where p is the index of the maximum element in the array.

You can ask no more than 20 queries. Printing the answer doesn't count as a query.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * see documentation for other languages 



Hacks

To make a hack, use the following test format.

In the first line output a single integer n (2 ≤ n ≤ 10^5). In the second line output a permutation of n integers 1 to n. The position of n in the permutation is the position of the maximum

Example

Input


5

3

4



Output


? 1 5

? 4 5

! 1

Note

In the sample suppose a is [5, 1, 4, 2, 3]. So after asking the [1..5] subsegment 4 is second to max value, and it's position is 3. After asking the [4..5] subsegment 2 is second to max value and it's position in the whole array is 4.

Note that there are other arrays a that would produce the same interaction, and the answer for them might be different. Example output is given in purpose of understanding the interaction.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this simple assignment you are given a number and have to make it negative. But maybe the number is already negative?

**Example:**
``` c
makeNegative(1); // return -1
makeNegative(-5); // return -5
makeNegative(0); // return 0
```
``` cfml
makeNegative(1); // return -1
makeNegative(-5); // return -5
makeNegative(0); // return 0
```
``` csharp
Kata.MakeNegative(1); // return -1
Kata.MakeNegative(-5); // return -5
Kata.MakeNegative(0); // return 0
```
``` java
Kata.makeNegative(1); // return -1
Kata.makeNegative(-5); // return -5
Kata.makeNegative(0); // return 0
```
``` python
make_negative(1);  # return -1
make_negative(-5); # return -5
make_negative(0);  # return 0
```
``` javascript
makeNegative(1); // return -1
makeNegative(-5); // return -5
makeNegative(0); // return 0
makeNegative(0.12); // return -0.12
```
``` typescript
makeNegative(1); // return -1
makeNegative(-5); // return -5
makeNegative(0); // return 0
```
``` cpp
makeNegative(1); // return -1
makeNegative(-5); // return -5
makeNegative(0); // return 0
```
``` haskell
makeNegative    1 -- return -1
makeNegative (-5) -- return -5
makeNegative    0 -- return 0
makeNegative 0.12 -- return -0.12
```
``` ruby
makeNegative(1); # return -1
makeNegative(-5); # return -5
makeNegative(0); # return 0
```
``` coffeescript
makeNegative 1    # return -1
makeNegative -5   # return -5
makeNegative 0    # return 0
```
``` elixir
make_negative 1    # return -1
make_negative -5   # return -5
make_negative 0    # return 0
```
``` go
MakeNegative(1)    # return -1
MakeNegative(-5)   # return -5
MakeNegative(0)    # return 0
```
``` julia
Kata.makeNegative(1)  # return -1
Kata.makeNegative(-5) # return -5
Kata.makeNegative(0)  # return 0
```
``` kotlin
Kata().makeNegative(1)  // return -1
Kata().makeNegative(-5) // return -5
Kata().makeNegative(0)  // return 0
```
``` asm
make_negative(1);    // return -1
make_negative(-5);   // return -5
make_negative(0);    // return 0
```
``` groovy
Kata.makeNegative(1)    // return -1
Kata.makeNegative(-5)   // return -5
Kata.makeNegative(0)    // return 0
```
``` php
makeNegative(1)    // return -1
makeNegative(-5)   // return -5
makeNegative(0)    // return 0
makeNegative(0.12) // return -0.12
```
```racket
(make-negative 1)    ; -1
(make-negative -5)   ; -5
(make-negative 0)    ; 0
(make-negative 0.12) ; -0.12
```

**Notes:**

- The number can be negative already, in which case no change is required.
- Zero (0) is not checked for any specific sign. Negative zeros make no mathematical sense.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has spent the entire day preparing problems for you. Now he has to sleep for at least $a$ minutes to feel refreshed.

Polycarp can only wake up by hearing the sound of his alarm. So he has just fallen asleep and his first alarm goes off in $b$ minutes.

Every time Polycarp wakes up, he decides if he wants to sleep for some more time or not. If he's slept for less than $a$ minutes in total, then he sets his alarm to go off in $c$ minutes after it is reset and spends $d$ minutes to fall asleep again. Otherwise, he gets out of his bed and proceeds with the day.

If the alarm goes off while Polycarp is falling asleep, then he resets his alarm to go off in another $c$ minutes and tries to fall asleep for $d$ minutes again.

You just want to find out when will Polycarp get out of his bed or report that it will never happen.

Please check out the notes for some explanations of the example.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The only line of each testcase contains four integers $a, b, c, d$ ($1 \le a, b, c, d \le 10^9$) — the time Polycarp has to sleep for to feel refreshed, the time before the first alarm goes off, the time before every succeeding alarm goes off and the time Polycarp spends to fall asleep.


-----Output-----

For each test case print one integer. If Polycarp never gets out of his bed then print -1. Otherwise, print the time it takes for Polycarp to get out of his bed.


-----Example-----
Input
7
10 3 6 4
11 3 6 4
5 9 4 10
6 5 2 3
1 1 1 1
3947465 47342 338129 123123
234123843 13 361451236 361451000

Output
27
27
9
-1
1
6471793
358578060125049



-----Note-----

In the first testcase Polycarp wakes up after $3$ minutes. He only rested for $3$ minutes out of $10$ minutes he needed. So after that he sets his alarm to go off in $6$ minutes and spends $4$ minutes falling asleep. Thus, he rests for $2$ more minutes, totaling in $3+2=5$ minutes of sleep. Then he repeats the procedure three more times and ends up with $11$ minutes of sleep. Finally, he gets out of his bed. He spent $3$ minutes before the first alarm and then reset his alarm four times. The answer is $3+4 \cdot 6 = 27$.

The second example is almost like the first one but Polycarp needs $11$ minutes of sleep instead of $10$. However, that changes nothing because he gets $11$ minutes with these alarm parameters anyway.

In the third testcase Polycarp wakes up rested enough after the first alarm. Thus, the answer is $b=9$.

In the fourth testcase Polycarp wakes up after $5$ minutes. Unfortunately, he keeps resetting his alarm infinitely being unable to rest for even a single minute :(

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
«Next please», — the princess called and cast an estimating glance at the next groom.

The princess intends to choose the most worthy groom, this is, the richest one. Whenever she sees a groom who is more rich than each of the previous ones, she says a measured «Oh...». Whenever the groom is richer than all previous ones added together, she exclaims «Wow!» (no «Oh...» in this case). At the sight of the first groom the princess stays calm and says nothing.

The fortune of each groom is described with an integer between 1 and 50000. You know that during the day the princess saw n grooms, said «Oh...» exactly a times and exclaimed «Wow!» exactly b times. Your task is to output a sequence of n integers t1, t2, ..., tn, where ti describes the fortune of i-th groom. If several sequences are possible, output any of them. If no sequence exists that would satisfy all the requirements, output a single number -1.

Input

The only line of input data contains three integer numbers n, a and b (1 ≤ n ≤ 100, 0 ≤ a, b ≤ 15, n > a + b), separated with single spaces.

Output

Output any sequence of integers t1, t2, ..., tn, where ti (1 ≤ ti ≤ 50000) is the fortune of i-th groom, that satisfies the given constraints. If no sequence exists that would satisfy all the requirements, output a single number -1.

Examples

Input

10 2 3


Output

5 1 3 6 16 35 46 4 200 99

Input

5 0 0


Output

10 10 6 6 5

Note

Let's have a closer look at the answer for the first sample test. 

  * The princess said «Oh...» (highlighted in bold): 5 1 3 6 16 35 46 4 200 99. 
  * The princess exclaimed «Wow!» (highlighted in bold): 5 1 3 6 16 35 46 4 200 99.

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