vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a set S. Generate T, a set that contains all subsets of S minus the null set  and calculate A, XOR sum of the set T.  
S={1,2,3}
T={{1},{2},{3},{1,2},{1,3},{2,3} ,{1,2,3}}
A=XORiana of T .
XORiana of a set is defined as XOR of all the elements it contains.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
0 ≤ Array[i] ≤ 200

SAMPLE INPUT
2
2 
3 3
3 
1 2 3

SAMPLE OUTPUT
0
0

Explanation

*Test Case 1: *
All subsets will be {3},{3},{3,3}
XOR of of all elements : {3} XOR{3} XOR {3 XOR 3} is zero .

*Test Case 2: * 
All subsets will be   {1} ,{2} ,{3} ,{1,2} ,{1,3} ,{2,3} ,{1,2,3} 
XOR of all elements :  {1}  XOR {2} XOR {3} XOR {1 XOR 2} XOR {1 XOR 3}  XOR {2 XOR 3}  XOR {1 XOR 2 XOR 3}  is zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length k is a sequence of k integers from 1 to k containing each integer exactly once. For example, the sequence [3, 1, 2] is a permutation of length 3.

When Neko was five, he thought of an array a of n positive integers and a permutation p of length n - 1. Then, he performed the following:

  * Constructed an array b of length n-1, where b_i = min(a_i, a_{i+1}). 
  * Constructed an array c of length n-1, where c_i = max(a_i, a_{i+1}). 
  * Constructed an array b' of length n-1, where b'_i = b_{p_i}. 
  * Constructed an array c' of length n-1, where c'_i = c_{p_i}. 



For example, if the array a was [3, 4, 6, 5, 7] and permutation p was [2, 4, 1, 3], then Neko would have constructed the following arrays:

  * b = [3, 4, 5, 5] 
  * c = [4, 6, 6, 7] 
  * b' = [4, 5, 3, 5] 
  * c' = [6, 7, 4, 6] 



Then, he wrote two arrays b' and c' on a piece of paper and forgot about it. 14 years later, when he was cleaning up his room, he discovered this old piece of paper with two arrays b' and c' written on it. However he can't remember the array a and permutation p he used.

In case Neko made a mistake and there is no array a and permutation p resulting in such b' and c', print -1. Otherwise, help him recover any possible array a. 

Input

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

The second line contains n-1 integers b'_1, b'_2, …, b'_{n-1} (1 ≤ b'_i ≤ 10^9).

The third line contains n-1 integers c'_1, c'_2, …, c'_{n-1} (1 ≤ c'_i ≤ 10^9).

Output

If Neko made a mistake and there is no array a and a permutation p leading to the b' and c', print -1. Otherwise, print n positive integers a_i (1 ≤ a_i ≤ 10^9), denoting the elements of the array a.

If there are multiple possible solutions, print any of them. 

Examples

Input


5
4 5 3 5
6 7 4 6


Output


3 4 6 5 7 


Input


3
2 4
3 2


Output


-1


Input


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


Output


3 4 5 2 1 4 3 2 

Note

The first example is explained is the problem statement.

In the third example, for a = [3, 4, 5, 2, 1, 4, 3, 2], a possible permutation p is [7, 1, 5, 4, 3, 2, 6]. In that case, Neko would have constructed the following arrays:

  * b = [3, 4, 2, 1, 1, 3, 2] 
  * c = [4, 5, 5, 2, 4, 4, 3] 
  * b' = [2, 3, 1, 1, 2, 4, 3] 
  * c' = [3, 4, 4, 2, 5, 5, 4] 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After learning basics of arrays and strings, Dark started wondering that if we can sort the numbers then why not STRINGS?

Deeply thinking and looking the various strings lying in the string pool, he decided to ascend or descend the string according to his wish.

Ascending means strings having all the characters in a string in a order like A,B,C,D,...,Z  while descending means string having all characters in a reverse order that is first all Z,Y,X,...,A and so on....

Note: String may contain all the characters available on the normal keyboard.
Thus Dark want you to help him design a code to sort the strings according to his wish the code has to sort either ascending or descending...

To make it easy, Dark wants to print only the characters which are Upper Case Alphabets present in the string in sorted form and don't display the other characters of the string.

Note: String will be only one word with mixture of any key present in the normal keyboard.

Input:

The first line contains T, the number of test cases.
Followed by T lines each contains space separated  a single string 'S' and a number 'N'.

N is even--> Ascending 

N is odd--> Descending

Output:

For every test case print the sorted form of the string.
Print "NULL" if their is no UPPER CASE ALPHABETS present in the string.

Constraints:

1 ≤ T ≤ 500
1 ≤ |S| ≤ 100000
0 ≤ N ≤ 100

Author : Darshak Mehta

SAMPLE INPUT
4
AABAHD 0
AABGHAD 1
AXBCD 0
AXBCD 1

SAMPLE OUTPUT
AAABDH
HGDBAAA
ABCDX
XDCBA

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zubin is the dark messiah. He roams the streets at night, helping the poor and the innocent from evil. He's Batman.
Ghosh is Zubin's nemesis. He's the Riddler to Zubin's Batman. He delights in torturing people with his puzzles.
Tonight, Ghosh has gotten hold of yet another innocent victim. When Zubin tries to save him, Ghosh sends him a message
Whom you seek is not here. Find him at GothamFuljhore 1st Street. The house number can be any of the length of the factorials of the numbers I'll send you next.
Now Zubin is a warrior, a hero. What he's not is too bright. Can you help him calculate the house number and help the poor victim?

EDIT

Maximum number of test cases - 500, 
Number of addresses < 5*10^9

SAMPLE INPUT
5

1
5
86
23
4

SAMPLE OUTPUT
1
3
131
23
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have array of n numbers a_{1}, a_{2}, …, a_{n}. 

Rearrange these numbers to satisfy |a_{1} - a_{2}| ≤ |a_{2} - a_{3}| ≤ … ≤ |a_{n-1} - a_{n}|, where |x| denotes absolute value of x. It's always possible to find such rearrangement.

Note that all numbers in a are not necessarily different. In other words, some numbers of a may be same.

You have to answer independent t test cases.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^{4}) — the number of test cases.

The first line of each test case contains single integer n (3 ≤ n ≤ 10^{5}) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed 10^{5}.

The second line of each test case contains n integers a_{1}, a_{2}, …, a_{n} (-10^{9} ≤ a_{i} ≤ 10^{9}).

Output

For each test case, print the rearranged version of array a which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Example

Input


2
6
5 -2 4 8 6 5
4
8 1 4 2


Output


5 5 4 6 8 -2
1 2 4 8

Note

In the first test case, after given rearrangement, |a_{1} - a_{2}| = 0 ≤ |a_{2} - a_{3}| = 1 ≤ |a_{3} - a_{4}| = 2 ≤ |a_{4} - a_{5}| = 2 ≤ |a_{5} - a_{6}| = 10. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, |a_{1} - a_{2}| = 1 ≤ |a_{2} - a_{3}| = 2 ≤ |a_{3} - a_{4}| = 4. There are other possible answers like "2 4 8 1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For this game of `BINGO`, you will receive a single array of 10 numbers from 1 to 26 as an input. Duplicate numbers within the array are possible.

Each number corresponds to their alphabetical order letter (e.g. 1 = A. 2 = B, etc). Write a function where you will win the game if your numbers can spell `"BINGO"`. They do not need to be in the right order in the input array). Otherwise you will lose. Your outputs should be `"WIN"` or `"LOSE"` respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's 3AM and you get the dreaded call from a customer: the program your company sold them is hanging. You eventually trace the problem down to a call to a function named `mystery`. Usually, `mystery` works fine and produces an integer result for an integer input. However, on certain inputs, the `mystery` function just locks up.

Unfortunately, the `mystery` function is part of a third-party library, and you don't have access to the source code. Uck. It may take a while to get support from the provider of the library, and in the meantime, your customer is getting frustrated.

Your mission, should you choose to accept it, is to create a new function called `wrap_mystery` that returns the same results as `mystery`, but does not hang. Since you're not sure exactly what values `mystery` should be returning for hangs, just have `wrap_mystery` return -1 for problematic input. Your customer is counting on you!

`wrap_mystery` will only be called with positive integers less than 1,000,000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oskar really loves onions. Unfortunately, the onions he loves belong to the local vegetable farmer, Lökas Tomatcek. Since Oskar is very cheap, he simply steals Lökas’ onions from the large, convex, onion field. For obvious reasons, Lökas does not approve of this. Rather than going to the police, however, Lökas wants to raise a high-energy laser fence around the onions to replace his wooden fence. 

As laser fences are rather expensive, Lökas can only afford to upgrade $K$ of the fence posts to laser fence posts. If a set of posts are upgraded, the lasers will protect all the onions lying strictly within the convex hull of the selected fence posts. This may not be all of the onions though. Lökas wonders which posts he should upgrade if he wants to protect as many of his $N$ onions as possible.

The original fence has the shape of a convex polygon with $M$ fence posts as vertices, and all the onions lie strictly within the fence.

-----Input-----
The first line of input consists of three space-separated integers $3 \le N \le 10000$, $3 \le M \le 400$ and $3 \le K \le 400$. These are the number of onions, the number of old fence posts, and the number of fence posts Lökas can upgrade.

Then follow $N$ lines with two space-separated integers $0 \le X_ i, Y_ i \le 10^9$ each. $(X_ i, Y_ i)$ gives the coordinate of the $i$-th onion.

Then follow $M$ lines with two space-separated integers $0 \le A_ i, B_ i \le 10^9$ each. $(A_ i, B_ i)$ gives the coordinate of the $i$-th fence post.

The fence posts will be given in clockwise order of the old fence. No three fence posts will lie on a line.

-----Output-----
Output should be a single integer; the maximum number of onions Lökas can protect.

-----Examples-----
Sample Input:
3 5 3
1 1
2 2
1 3
0 0
0 3
1 4
3 3
3 0
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define the transformation P of a sequence of integers a1, a2, ..., an as b1, b2, ..., bn, where bi = a1 | a2 | ... | ai for all i = 1, 2, ..., n, where | is the bitwise OR operation.

Vasya consequently applies the transformation P to all sequences of length n consisting of integers from 1 to 2k - 1 inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo 109 + 7.

Input

The only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30 000).

Output

Print a single integer — the answer to the problem modulo 109 + 7.

Examples

Input

1 2


Output

3


Input

2 3


Output

30


Input

3 3


Output

48

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lira is now very keen on compiler development. :) 
She knows that one of the most important components of a compiler, is its parser.
A parser is, in simple terms, a software component that processes text, and checks it's semantic correctness, or, if you prefer, if the text is properly built.
As an example, in declaring and initializing an integer, in C/C++, you can't do something like:
int = x ;4
as the semantics of such statement is incorrect, as we all know that the datatype must precede an identifier and only afterwards should come the equal sign and the initialization value, so, the corrected statement should be:
int x = 4;
Today, Lira is concerned with an abstract instruction which is composed of the characters "<" and ">" , which she will use on the design of her language, L++ :D.
She is using it as an abstraction for generating XML code Tags in an easier fashion and she understood that, for an expression to be valid, a "<" symbol must always have a corresponding ">" character somewhere (not necessary immediately) after it. Moreover, each ">" symbol should correspond to exactly one "<" symbol.
So, for instance, the instructions:
<<>> 
<> 
<><> 
are all valid. While:
>> 
><>< 
are not.
Given some expressions which represent some instructions to be analyzed by Lira's compiler, you should tell the length of the longest prefix of each of these expressions that is valid, or 0 if there's no such a prefix.

-----Input-----
Input will consist of an integer T denoting the number of test cases to follow.
Then, T strings follow, each on a single line, representing a possible expression in L++.

-----Output-----
For each expression you should output the length of the longest prefix that is valid or 0 if there's no such a prefix. 


-----Constraints-----
- 1 ≤ T ≤ 500
- 1 ≤ The length of a single expression ≤ 106
- The total size all the input expressions is no more than 5*106

-----Example-----
Input:
3
<<>>
><
<>>>
Output:
4
0
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all know Gru loves Agnes very much. One day Agnes asked Gru to answer some of her queries. She lined up $N$ minions in a straight line from $1$ to $N$. 
You are given an array $A$ which contains the height of minions. Agnes will ask him several queries. In each query, Gru has to tell whether the bitwise AND of  $A[L \ldots R]$ is EVEN or ODD. Since Gru is busy planning the biggest heist on Earth, he asks for your help.

-----Input:-----
- First line of the input contains an integer $T$ denoting the number of test cases.
For each test case:-
- First line contains an integer $N$ denoting the number of elements.
- Second line contains $N$ spaced integer representing array elements.
- Third line contains $Q$ representing number of query.
- Next $Q$ lines contains two integer $L$ and $R$ as defined above.

-----Output:-----
For each query, output "EVEN" or "ODD" without quotes.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^5$
- $1 \leq Q \leq 10^5$

-----Sample Input:-----
1
5
1 3 2 4 5
3
1 2 
1 5
3 4

-----Sample Output:-----
ODD
EVEN
EVEN

-----Explanation-----
- For the first query, the bitwise AND of 1 and 3 is 1, which is Odd. Hence the first output is ODD.
- For the third query, the bitwise AND of 2 and 4 is 0, which is Even. Hence the third output is EVEN.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As a token of his gratitude, Takahashi has decided to give his mother an integer sequence.
The sequence A needs to satisfy the conditions below:
 - A consists of integers between X and Y (inclusive).
 - For each 1\leq i \leq |A|-1, A_{i+1} is a multiple of A_i and strictly greater than A_i.
Find the maximum possible length of the sequence.

-----Constraints-----
 - 1 \leq X \leq Y \leq 10^{18}
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y

-----Output-----
Print the maximum possible length of the sequence.

-----Sample Input-----
3 20

-----Sample Output-----
3

The sequence 3,6,18 satisfies the conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.  Current character pointer (CP);  Direction pointer (DP) which can point left or right; 

Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.  If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one.  If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence. 

If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s_1, s_2, ..., s_{n} of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence s_{l}, s_{l} + 1, ..., s_{r} as an independent program in this language.


-----Input-----

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100) — represents the length of the sequence s and the number of queries. 

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces. 

The next q lines each contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the i-th query.


-----Output-----

For each query print 10 space separated integers: x_0, x_1, ..., x_9 where x_{i} equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.


-----Examples-----
Input
7 4
1>3>22<
1 3
4 7
7 7
1 7

Output
0 1 0 1 0 0 0 0 0 0 
2 2 2 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
2 3 2 1 0 0 0 0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given two strings `a` and `b` and your task will be to return the characters that are not common in the two strings. 

For example:
```Haskell
solve("xyab","xzca") = "ybzc" 
--The first string has 'yb' which is not in the second string. 
--The second string has 'zc' which is not in the first string. 
```
Notice also that you return the characters from the first string concatenated with those from the second string.

More examples in the tests cases. 

Good luck!

Please also try [Simple remove duplicates](https://www.codewars.com/kata/5ba38ba180824a86850000f7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone knows that hobbits love to organize all sorts of parties and celebrations. There are n hobbits living in the Shire. They decided to organize the Greatest Party (GP) that would last for several days. Next day the hobbits wrote a guest list, some non-empty set containing all the inhabitants of the Shire. To ensure that everybody enjoy themselves and nobody gets bored, for any two days (say, days A and B) of the GP there existed at least one hobbit, invited to come on day A and on day B. However, to ensure that nobody has a row, for any three different days A, B, C there shouldn't be a hobbit invited on days A, B and C. The Shire inhabitants are keen on keeping the GP going for as long as possible. Your task is given number n, to indicate the GP's maximum duration and the guest lists for each day.

Input

The first line contains an integer n (3 ≤ n ≤ 10000), representing the number of hobbits.

Output

In the first output line print a number k — the maximum duration of GP in days. Then on k lines print the guest lists, (the guests should be separated by spaces). Print each guest list on the single line. Each list can contain an arbitrary positive number of hobbits. The hobbits are numbered with integers from 1 to n.

Examples

Input

4


Output

3
1 2 
1 3 
2 3 


Input

5


Output

3
1 2 
1 3 
2 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n left boots and n right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark ('?'). Thus, you are given two strings l and r, both of length n. The character l_i stands for the color of the i-th left boot and the character r_i stands for the color of the i-th right boot.

A lowercase Latin letter denotes a specific color, but the question mark ('?') denotes an indefinite color. Two specific colors are compatible if they are exactly the same. An indefinite color is compatible with any (specific or indefinite) color.

For example, the following pairs of colors are compatible: ('f', 'f'), ('?', 'z'), ('a', '?') and ('?', '?'). The following pairs of colors are not compatible: ('f', 'g') and ('a', 'z').

Compute the maximum number of pairs of boots such that there is one left and one right boot in a pair and their colors are compatible.

Print the maximum number of such pairs and the pairs themselves. A boot can be part of at most one pair.

Input

The first line contains n (1 ≤ n ≤ 150000), denoting the number of boots for each leg (i.e. the number of left boots and the number of right boots).

The second line contains the string l of length n. It contains only lowercase Latin letters or question marks. The i-th character stands for the color of the i-th left boot.

The third line contains the string r of length n. It contains only lowercase Latin letters or question marks. The i-th character stands for the color of the i-th right boot.

Output

Print k — the maximum number of compatible left-right pairs of boots, i.e. pairs consisting of one left and one right boot which have compatible colors.

The following k lines should contain pairs a_j, b_j (1 ≤ a_j, b_j ≤ n). The j-th of these lines should contain the index a_j of the left boot in the j-th pair and index b_j of the right boot in the j-th pair. All the numbers a_j should be distinct (unique), all the numbers b_j should be distinct (unique).

If there are many optimal answers, print any of them.

Examples

Input


10
codeforces
dodivthree


Output


5
7 8
4 9
2 2
9 10
3 1


Input


7
abaca?b
zabbbcc


Output


5
6 5
2 3
4 6
7 4
1 2


Input


9
bambarbia
hellocode


Output


0


Input


10
code??????
??????test


Output


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

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