vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A permutation is a sequence of n integers from 1 to n, in which all numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was presented with a permutation p of numbers from 1 to n. However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule: 

  * q_i = max(p_1, p_2, …, p_i). 



Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array a of length n is lexicographically smaller than an array b of length n if there is an index i (1 ≤ i ≤ n) such that the first i-1 elements of arrays a and b are the same, and the i-th element of the array a is less than the i-th element of the array b. For example, the array a=[1, 3, 2, 3] is lexicographically smaller than the array b=[1, 3, 4, 2].

For example, if n=7 and p=[3, 2, 4, 1, 7, 5, 6], then q=[3, 3, 4, 4, 7, 7, 7] and the following permutations could have been as p initially: 

  * [3, 1, 4, 2, 7, 5, 6] (lexicographically minimal permutation); 
  * [3, 1, 4, 2, 7, 6, 5]; 
  * [3, 2, 4, 1, 7, 5, 6]; 
  * [3, 2, 4, 1, 7, 6, 5] (lexicographically maximum permutation). 



For a given array q, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers q_1, q_2, …, q_n (1 ≤ q_i ≤ n).

It is guaranteed that the array q was obtained by applying the rule from the statement to some permutation p.

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

Output

For each test case, output two lines: 

  * on the first line output n integers — lexicographically minimal permutation that could have been originally presented to Polycarp; 
  * on the second line print n integers — lexicographically maximal permutation that could have been originally presented to Polycarp; 

Example

Input


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


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The local zoo has acquired a large open garden in which animals may freely move as in their natural habitats and entertain visitors with their usual shenanigans.

The most popular animals are monkeys. With their climbing and jumping and other skills, they delight old and young visitors alike.

One species of monkey has specialized in climbing tall trees and picking off coconuts. Another species has specialized in breaking them open.

There are $N$ monkeys of the first type (numbered 1 through $N$) and $M$ monkeys of the second type (numbered 1 through $M$).

Monkey $k$ of the first type takes $A_ k$ seconds to find a good spot on the tree, after which it picks off its first coconut. After that the monkey produces a new coconut every $B_ k$ seconds.

Monkey $k$ of the second type takes $C_ k$ seconds to find a good tool for opening the coconuts, after which it opens its first coconut. After that the monkey opens another coconut every $D_ k$ seconds.

Unfortunately, the second type of monkey is extremely aggressive so the two types may not be in the garden at the same time. Therefore, zoo keepers will chase away the first type of monkeys as soon as they have picked off all the coconuts. Similarly, if monkeys of the same type stay too long after opening all the coconuts, fights will ensue. Because of that, zoo keepers will send them away as soon as they have opened all the coconuts.

The zoo keepers first arrive immediately after all coconuts have been picked, and again immediately after the monkeys open them all. The time needed for monkeys to enter or leave the garden is also negligibly small.

Tomislav especially likes the second type of monkey, but can never guess when to arrive in order to see them. Help him calculate the time when the second type arrives if he knows the total time that monkeys spent in the garden, but does not know the number of coconuts in the garden.

-----Input-----
The first line contains the integer $T$ $(1 \leq T \leq 1000000000)$, the total time that monkeys spent in the garden, in seconds.

The next line contains the integer $N$ $(1 \leq N \leq 100)$, the number of monkeys of the first type. Each of the following $N$ lines contains two integers $A_ k$ and $B_ k$ $(1 \leq A_ k, B_ k \leq 1000000000)$, how fast monkey $k$ of the first type is.

The next line contains the integer $M$ $(1 \leq M \leq 100)$, the number of monkeys of the second type. Each of the following $M$ lines contains two integers $C_ k$ and $D_ k$ $(1 \leq C_ k, D_ k \leq 1000000000)$, how fast monkey $k$ of the second type is.

-----Output-----
Output the number of seconds between the arrival of the first type of monkeys and the arrival of the second type.

-----Examples-----
Sample Input:
12
1
3 1
1
5 1
Sample Output:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).
Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.
Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq H, W \leq 3 \times 10^5
 - 1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)
 - 1 \leq h_i \leq H
 - 1 \leq w_i \leq W
 - \left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

-----Input-----
Input is given from Standard Input in the following format:
H W M
h_1 w_1
\vdots
h_M w_M

-----Output-----
Print the answer.

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

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

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to increase creativity by drawing pictures. Let's draw a pattern well using a square stamp.

I want to use stamps of various sizes to complete the picture of the red, green, and blue streets specified on the 4 x 4 squared paper. The stamp is rectangular and is used to fit the squares. The height and width of the stamp cannot be swapped.

The paper is initially uncolored. When you stamp on paper, the stamped part changes to the color of the stamp, and the color hidden underneath becomes completely invisible. Since the color of the stamp is determined by the ink to be applied, it is possible to choose the color of any stamp. The stamp can be stamped with a part protruding from the paper, and the protruding part is ignored.

It is possible to use one stamp multiple times. You may use the same stamp for different colors. Stamping is a rather nerve-wracking task, so I want to reduce the number of stamps as much as possible.



Input


N
H1 W1
...
HN WN
C1,1C1,2C1,3C1,4
C2,1C2,2C2,3C2,4
C3,1C3,2C3,3C3,4
C4,1C4,2C4,3C4,4


N is the number of stamps, and Hi and Wi (1 ≤ i ≤ N) are integers representing the vertical and horizontal lengths of the i-th stamp, respectively. Ci, j (1 ≤ i ≤ 4, 1 ≤ j ≤ 4) is a character that represents the color of the picture specified for the cells in the i-th row from the top and the j-th column from the left. Red is represented by `R`, green is represented by` G`, and blue is represented by `B`.

Satisfy 1 ≤ N ≤ 16, 1 ≤ Hi ≤ 4, 1 ≤ Wi ≤ 4. The same set as (Hi, Wi) does not appear multiple times.

Output

Print the minimum number of stamps that must be stamped to complete the picture on a single line.

Examples

Input

2
4 4
1 1
RRRR
RRGR
RBRR
RRRR


Output

3


Input

1
2 3
RRGG
BRGG
BRRR
BRRR


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After acquiring a new integer and showing it off to other couples at a cocktail party, Alice and Bob headed home for a good night of sleep. As their integer was quite large, they were forced to carry it together. Then, on the Boole Boulevard, right by the Bayes Bay, disaster struck. History does not tell us which of our two protagonists stumbled first, but stumble they did, and their integer shattered into $n$ positive integral pieces on the pavement in front of them.

The couple’s marriage, already under financial stress due to the expensive integer acquisition, did not survive this event, and Bob and Alice resolved to separate. Thus the question was raised on how to split the remnants of their integer. Bob and Alice decided to play a game with the remaining $n$ pieces: the two would repeatedly choose pieces in alternating turns until none were left.

Bob and Alice, both very materialistic, seek to acquire the largest possible sum of integers possible. Compute the value of the integers each of them ends up with. Assume both players play optimally. Since A comes before B in the alphabet, Alice moves first.

-----Input-----
The input consists of two lines.
 - A single integer $1 \leq n \leq 15$, the number of pieces.
 - The values of the pieces $a_0, a_1, \dots , a_{n-1}$, space-separated. It is given that $1 \leq a_ i \leq 100$.

-----Output-----
Output a single line containing two integers, the combined value of Alice’s pieces, and the combined value of Bob’s pieces.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ricky gives a number 'n' to John. Now Ricky wants John to generate Z with symbol "*" such that it spans n rows.

Example:

Input : n=3

Output :

***
  *
***

Input : n=4

Output :

****
   *
  *
****

Constraint :

3 ≤ n ≤20

SAMPLE INPUT
5

SAMPLE OUTPUT
*****
   *
  *
 *
*****

Explanation

The 'Z' is printed across 5 lines as shown above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp invited all his friends to the tea party to celebrate the holiday. He has n cups, one for each of his n friends, with volumes a_1, a_2, ..., a_{n}. His teapot stores w milliliters of tea (w ≤ a_1 + a_2 + ... + a_{n}). Polycarp wants to pour tea in cups in such a way that:  Every cup will contain tea for at least half of its volume  Every cup will contain integer number of milliliters of tea  All the tea from the teapot will be poured into cups  All friends will be satisfied. 

Friend with cup i won't be satisfied, if there exists such cup j that cup i contains less tea than cup j but a_{i} > a_{j}.

For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Input-----

The first line contains two integer numbers n and w (1 ≤ n ≤ 100, $1 \leq w \leq \sum_{i = 1}^{n} a_{i}$).

The second line contains n numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100).


-----Output-----

Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them.

If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Examples-----
Input
2 10
8 7

Output
6 4 

Input
4 4
1 1 1 1

Output
1 1 1 1 

Input
3 10
9 8 10

Output
-1



-----Note-----

In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko lives in a big enchanted forest where trees are very tall and grow really quickly. That forest can be represented as an $N\cdot N$ matrix where each field contains one tree.

Mirko is very fond of the trees in the enchanted forest. He spent years observing them and for each tree measured how many meters it grew in a year. The trees grow continuously. In other words, if the tree grows $5$ meters in a year, it will grow $2.5$ meters in half a year.

Apart from trees, Mirko likes mushrooms from the enchanted forest. Sometimes, he eats suspicious colorful mushrooms and starts thinking about peculiar questions. Yesterday, this unfortunate thing happened and he wondered what would be the size of the largest connected group of trees that are all of equal height if the trees continue to grow at the same speed they’re growing at that moment.

Mirko quickly measured the current height of all trees in the forest and asked you to answer his question.

Two trees are adjacent if their fields in the matrix share a common edge.

Two trees are connected if there is a sequence of adjacent trees that leads from the first to the second.

A group of trees is connected if every pair of trees in the group is connected.

-----Input-----
The first line of input contains the integer $N$ ($1 \leq N \leq 700$).

After the first line, $N$ lines follow, each of them containing $N$ integers.

The $i$-th line contains integers $h_{ij}$ ($1 \leq h_{ij} \leq 10^6$), the initial height of tree in the $i$-th row and $j$-th column, given in meters.

After that, $N$ more lines follow with $N$ integers each.

The $i$-th line contains integers $v_{ij}$ ($1 \leq v_{ij} \leq 10^6$), the growth speed of the tree in the $i$-th row and $j$-th column, given in meters.

Warning: Please use faster input methods beacuse the amount of input is very large. For example, either set ios::sync_with_stdio(false) or use scanf instead of cin in C++, and use BufferedReader instead of Scanner in Java.

-----Output-----
The first and only line of output must contain the required number from the task.

-----Examples-----
Sample Input:
3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3
Sample Output:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Volodya has recently visited a very odd town. There are N tourist attractions in the town and every two of them are connected by a bidirectional road. Each road has some travel price (natural number) assigned to it and all prices are distinct. But the most striking thing about this town is that each city sightseeing tour has the same total price! That is, if we choose any city sightseeing tour — a cycle which visits every attraction exactly once — the sum of the costs of the tour roads is independent of the tour. Volodya is curious if you can find such price system with all road prices not greater than 1000.

Input

Input contains just one natural number (3 ≤ N ≤ 20) — the number of town attractions.

Output

Output should contain N rows containing N positive integer numbers each — the adjacency matrix of the prices graph (thus, j-th number in i-th row should be equal to the price of the road between the j-th and the i-th attraction). Diagonal numbers should be equal to zero. All numbers should not be greater than 1000. All prices should be positive and pairwise distinct. If there are several solutions, output any of them.

Examples

Input

3


Output

0 3 4 
3 0 5 
4 5 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is going to buy N items one by one.
The price of the i-th item he buys is A_i yen (the currency of Japan).
He has M discount tickets, and he can use any number of them when buying an item.
If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.
What is the minimum amount of money required to buy all the items?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_N

-----Output-----
Print the minimum amount of money required to buy all the items.

-----Sample Input-----
3 3
2 13 8

-----Sample Output-----
9

We can buy all the items for 9 yen, as follows:
 - Buy the 1-st item for 2 yen without tickets.
 - Buy the 2-nd item for 3 yen with 2 tickets.
 - Buy the 3-rd item for 4 yen with 1 ticket.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to simply count total numbers in range L to R such that their sum of digits is K

Input
First line contains L,R and K as input. 

Constraints
1 ≤ L ≤ 10^18
1 ≤ R ≤ 10^18
1 ≤ K ≤ 10^9
L is always lesser than or equal to R

SAMPLE INPUT
2 15 4

SAMPLE OUTPUT
2

Explanation

4 and 13 are the two numbers with digit sum as 4 for the given range

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains a_{i} liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.


-----Output-----

The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.


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

Output
12

Input
3
5 5 5

Output
15

Input
6
10 10 10 1 10 10

Output
11



-----Note-----

In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
User ainta has a stack of n red and blue balls. He can apply a certain operation which changes the colors of the balls inside the stack.

  While the top ball inside the stack is red, pop the ball from the top of the stack.  Then replace the blue ball on the top with a red ball.  And finally push some blue balls to the stack until the stack has total of n balls inside.   

If there are no blue balls inside the stack, ainta can't apply this operation. Given the initial state of the stack, ainta wants to know the maximum number of operations he can repeatedly apply.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 50) — the number of balls inside the stack.

The second line contains a string s (|s| = n) describing the initial state of the stack. The i-th character of the string s denotes the color of the i-th ball (we'll number the balls from top to bottom of the stack). If the character is "R", the color is red. If the character is "B", the color is blue.


-----Output-----

Print the maximum number of operations ainta can repeatedly apply.

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


-----Examples-----
Input
3
RBR

Output
2

Input
4
RBBR

Output
6

Input
5
RBBRR

Output
6



-----Note-----

The first example is depicted below.

The explanation how user ainta applies the first operation. He pops out one red ball, changes the color of the ball in the middle from blue to red, and pushes one blue ball.

 [Image] 

The explanation how user ainta applies the second operation. He will not pop out red balls, he simply changes the color of the ball on the top from blue to red.

 [Image] 

From now on, ainta can't apply any operation because there are no blue balls inside the stack. ainta applied two operations, so the answer is 2.

The second example is depicted below. The blue arrow denotes a single operation.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most of the events were over and the participants were roaming about in the Nirma Campus when they reached the Nirma Lake. It is a Large lake and to get to the other side of the lake, you have to go around it. So, participants decide to construct plans for bridges on the lake. They identify points on each side of the lake on which Bridge end points can be made. The students then decide that a bridge can only be built between corresponding end points, i.e. a bridge starting from the ith end point on one side can only end on the ith end point on the other side, where the position of end points is seen in the order in which the points were identified. They just wants to make as many non-cutting bridges as possible, with the constraint in mind. Bridges "cut" if and only if they have exactly one common point that is not an end point.

Input:

The first line of the input contains test cases t. It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n. The second line contains x-coordinates of end points identified on the first side and similarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are givenin the order in which they were identified.

Output:

You are required to output a single line for each test case. The line contains a single integer – the maximum number of bridges possible with the constraints explained above.

Constraints:

1 ≤ t ≤ 50

1 ≤ n ≤ 1000

-1000 ≤ x-coordinates ≤ 1000

SAMPLE INPUT
3
4
2 5 8 10
6 4 1 2
3
5 3 10
6 4 1
6
1 2 3 4 5 6
3 4 5 6 1 2

SAMPLE OUTPUT
2
2
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lea runs into a lot of words in her life. A lot of them she finds unpleasant. To compensate for that she started making up pleasant words. Lea makes up new words by writing a nice looking string of characters on a piece of paper. She than erases a few of the most nasty looking characters and replaces them with underscores ‘_’. After that she tries to replace the underscores with more acceptable characters trying to form a pleasant word.

Lea considers words pleasant if they do not contain $3$ sequential vowels, $3$ sequential consonants and contain at least one letter ‘L’.

In Croatian, the vowels are the letters A, E, I, O, and U only. All other lettters are consonants.

-----Input-----
The first and only line of input contains a string of characters, at most $100$. The string contains only of uppercase English letters and ‘_’ characters. There will be at most $10$ ‘_’ characters.

-----Output-----
The first and only line of output should cotain a single integer – the total number of pleasant words that can be formed by substituting underscores with uppercase letters of the English alphabet.

-----Examples-----
Sample Input 1:
L_V
Sample Output 1:
5

Sample Input 2:
V__K
Sample Output 2:
10

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