vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
K-th String

Problem Statement

The suffix array SA for the character string S of length N is defined as a permutation of positive integers of N or less obtained by the following procedure.
The substring from the i-th character to the j-th character of S is expressed as S [i..j]. However, the subscript is 1-indexed.

1. Arrange each suffix S [i..N] (i = 1,2, ..., N) in lexicographic order (ascending order).
2. Arrange the start position i of each of the aligned suffixes in order.



For example, the suffix array SA for S = "mississippi" is as follows.

<image>



As input, the suffix array SA for a string of length N is given.
Find the K-th (1-indexed) string in lexicographic order from which SA can be obtained.
However, the original character string consists of at most A characters counting from'a'in alphabetical order.

Constraints

* 1 ≤ N ≤ 10 ^ 5
* 1 ≤ A ≤ 26
* 1 ≤ K ≤ 10 ^ {18}
* 1 ≤ SA_i ≤ N
* If i \ neq j, then SA_i \ neq SA_j

Input

Input follows the following format. All given numbers are integers.


N A K
SA_1_1
SA_2
...
SA_N

Output

Output the K-th character string on one line in a lexicographic order that gives SA.
If the Kth character string does not exist, output "Impossible".

Examples

Input

3 4 2
2
1
3


Output

bad


Input

18 26 10275802967
10
14
9
13
7
8
2
6
11
18
12
1
4
3
16
5
17
15


Output

ritsumeicampdaytwo

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will consider the numbers a and b as adjacent if they differ by exactly one, that is, |a-b|=1.

We will consider cells of a square matrix n × n as adjacent if they have a common side, that is, for cell (r, c) cells (r, c-1), (r, c+1), (r-1, c) and (r+1, c) are adjacent to it.

For a given number n, construct a square matrix n × n such that: 

  * Each integer from 1 to n^2 occurs in this matrix exactly once; 
  * If (r_1, c_1) and (r_2, c_2) are adjacent cells, then the numbers written in them must not be adjacent. 

Input

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

Each test case is characterized by one integer n (1 ≤ n ≤ 100).

Output

For each test case, output: 

  * -1, if the required matrix does not exist; 
  * the required matrix, otherwise (any such matrix if many of them exist). 



The matrix should be outputted as n lines, where each line contains n integers.

Example

Input


3
1
2
3


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function that calculates the derivative of a polynomial. A polynomial is an expression like: 3x^(4) - 2x^(2) + x - 10

### How to calculate the derivative:

* Take the exponent and multiply it with the coefficient
* Reduce the exponent by 1

For example: 3x^(4) --> (4*3)x^((4-1)) = 12x^(3)

### Good to know:

* The derivative of a constant is 0 (e.g. 100 --> 0)
* Anything to the 0th exponent equals 1 (e.g. x^(0) = 1)
* The derivative of the sum of two function is the sum of the derivatives

Notes:
* The exponentiation is marked with "^"
* Exponents are always integers and >= 0
* Exponents are written only if > 1
* There are no spaces around the operators
* Leading "+" signs are omitted

See the examples below.

## Examples
```python
derivative("-100")      = "0"
derivative("4x+1")      = "4"      # = 4x^0 + 0
derivative("-x^2+3x+4") = "-2x+3"  # = -2x^1 + 3x^0 + 0
```

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
And again a misfortune fell on Poor Student. He is being late for an exam.

Having rushed to a bus stop that is in point (0,<=0), he got on a minibus and they drove along a straight line, parallel to axis *OX*, in the direction of increasing *x*.

Poor Student knows the following: 
 -  during one run the minibus makes *n* stops, the *i*-th stop is in point (*x**i*,<=0) -  coordinates of all the stops are different -  the minibus drives at a constant speed, equal to *v**b* -  it can be assumed the passengers get on and off the minibus at a bus stop momentarily -  Student can get off the minibus only at a bus stop -  Student will have to get off the minibus at a terminal stop, if he does not get off earlier -  the University, where the exam will be held, is in point (*x**u*,<=*y**u*) -  Student can run from a bus stop to the University at a constant speed *v**s* as long as needed -  a distance between two points can be calculated according to the following formula:  -  Student is already on the minibus, so, he cannot get off at the first bus stop 
Poor Student wants to get to the University as soon as possible. Help him to choose the bus stop, where he should get off. If such bus stops are multiple, choose the bus stop closest to the University.

Input Specification:
The first line contains three integer numbers: 2<=≤<=*n*<=≤<=100, 1<=≤<=*v**b*,<=*v**s*<=≤<=1000. The second line contains *n* non-negative integers in ascending order: coordinates *x**i* of the bus stop with index *i*. It is guaranteed that *x*1 equals to zero, and *x**n*<=≤<=105. The third line contains the coordinates of the University, integers *x**u* and *y**u*, not exceeding 105 in absolute value.

Output Specification:
In the only line output the answer to the problem — index of the optimum bus stop.

Demo Input:
['4 5 2\n0 2 4 6\n4 1\n', '2 1 1\n0 100000\n100000 100000\n']

Demo Output:
['3', '2']

Note:
As you know, students are a special sort of people, and minibuses usually do not hurry. That's why you should not be surprised, if Student's speed is higher than the speed of the minibus.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrzej was given a task:
There are n jars with pills. In every jar there is a different type of pill and the amount of pills in each jar is infinite. One type of pill makes a person glow about 30 minutes after taking and none of the other types has any effect.
His job is to determine, in which jar are the pills that make a person glow.
But there is one catch, he only has 35 minutes to do so.(so he can't take a pill, wait for the results and then take another one, because he wouldn't be able to see the results)
Fortunetely, he can take any number of friends he needs with him.
On completing the task Andrzej receives one million dollars. You know that Andrzej is very honest, so he will split the money equally with his friends.
Your job is to determine how many friends does Andrzej need to complete the task.(He also wants to make the highest amount of money.)
For example for n = 2
The answer is 0 because he doesn't need any friends, he just needs to take a pill from the first jar and wait for the effects.
For another example for n = 4
The answer is 1 because having pills A B C D Andrzej can take pills A B and the friend can take pills B C

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is a version of problem D from the same contest with some additional constraints and tasks.

There are $n$ candies in a candy box. The type of the $i$-th candy is $a_i$ ($1 \le a_i \le n$). 

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $1$ and two candies of type $2$ is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

You really like some of the candies and don't want to include them into the gift, but you want to eat them yourself instead. For each candy, a number $f_i$ is given, which is equal to $0$ if you really want to keep $i$-th candy for yourself, or $1$ if you don't mind including it into your gift. It is possible that two candies of the same type have different values of $f_i$.

You want your gift to be as large as possible, but you don't want to include too many of the candies you want to eat into the gift. So, you want to calculate the maximum possible number of candies that can be included into a gift, and among all ways to choose maximum number of candies, you want to maximize the number of candies having $f_i = 1$ in your gift.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of candies.

Then $n$ lines follow, each containing two integers $a_i$ and $f_i$ ($1 \le a_i \le n$, $0 \le f_i \le 1$), where $a_i$ is the type of the $i$-th candy, and $f_i$ denotes whether you want to keep the $i$-th candy for yourself ($0$ if you want to keep it, $1$ if you don't mind giving it away).

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print two integers:

  the maximum number of candies in a gift you can compose, according to the constraints in the statement;  the maximum number of candies having $f_i = 1$ in a gift you can compose that contains the maximum possible number of candies.  


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

Output
3 3
3 3
9 5



-----Note-----

In the first query, you can include two candies of type $4$ and one candy of type $5$. All of them have $f_i = 1$ and you don't mind giving them away as part of the gift.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and Prime Numbers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers *x*1,<=*x*2,<=...,<=*x**n* of length *n* and *m* queries, each of them is characterized by two integers *l**i*,<=*r**i*. Let's introduce *f*(*p*) to represent the number of such indexes *k*, that *x**k* is divisible by *p*. The answer to the query *l**i*,<=*r**i* is the sum: , where *S*(*l**i*,<=*r**i*) is a set of prime numbers from segment [*l**i*,<=*r**i*] (both borders are included in the segment).

Help the bear cope with the problem.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=106). The second line contains *n* integers *x*1,<=*x*2,<=...,<=*x**n* (2<=≤<=*x**i*<=≤<=107). The numbers are not necessarily distinct.

The third line contains integer *m* (1<=≤<=*m*<=≤<=50000). Each of the following *m* lines contains a pair of space-separated integers, *l**i* and *r**i* (2<=≤<=*l**i*<=≤<=*r**i*<=≤<=2·109) — the numbers that characterize the current query.

Output Specification:
Print *m* integers — the answers to the queries on the order the queries appear in the input.

Demo Input:
['6\n5 5 7 10 14 15\n3\n2 11\n3 12\n4 4\n', '7\n2 3 5 7 11 4 8\n2\n8 10\n2 123\n']

Demo Output:
['9\n7\n0\n', '0\n7\n']

Note:
Consider the first sample. Overall, the first sample has 3 queries.
 1.  The first query *l* = 2, *r* = 11 comes. You need to count *f*(2) + *f*(3) + *f*(5) + *f*(7) + *f*(11) = 2 + 1 + 4 + 2 + 0 = 9. 1.  The second query comes *l* = 3, *r* = 12. You need to count *f*(3) + *f*(5) + *f*(7) + *f*(11) = 1 + 4 + 2 + 0 = 7. 1.  The third query comes *l* = 4, *r* = 4. As this interval has no prime numbers, then the sum equals 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N people numbered from 1 to N such that:
Exactly one of these people is a thief and always lies;
All the others are honest and always tell the truth. 

If the i^{th} person claims that the thief is one person out of L_{i}, L_{i}+1, L_{i}+2, \cdots, R_{i}, determine how many people could be the thief.

It is guaranteed that at least one person can be the thief.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- First line of each test case will contain N, the number of people. N lines follow. 
- The i^{th} line contains two space-separated integers - L_{i} and R_{i}, the range of people amongst which the i^{th} person claims the thief is.

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

- For each test case, in the first line, output K, the number of possible thieves. 
- In the next K lines, output the list of people that could be the thieves, in ascending order. 

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

$1 ≤ T ≤ 10^{5}$
$3 ≤ N ≤ 10^{5}$
$1 ≤ L_{i} ≤ R_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{5}$.
- It is guaranteed that at least one person can be the thief.

----- Sample Input 1 ------ 
1
4
2 2
1 1
1 3
1 3
----- Sample Output 1 ------ 
2
1
2
----- explanation 1 ------ 
Test case $1$: Two people (numbered $1$ and $2$) can be thief:
- Person $1$ may be the thief because, the other $3$ people claim that he may be the thief, whereas, he lies and claims that person $2$ is the thief. 
- Person $2$ may be the thief because, the other $3$ people claim that he may be the thief, whereas, he lies and claims that person $1$ is the thief. 
- Person $3$ cannot be the thief because, he claims that the thief lies in the range $[1, 3]$. If he were the thief, then his statement should be false. However, since 3 lies in $[1, 3]$, his statement would be true, which results in a contradiction. Furthermore, the first $2$ people do not claim that he is the thief. Therefore, he cannot be the thief. 
- Person $4$ cannot be the thief because the first $3$ people do not claim that he is the thief.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem F: Magnum Tornado

We have a toy that consists of a small racing circuit and a tiny car. For simplicity you can regard the circuit as a 2-dimensional closed loop, made of line segments and circular arcs. The circuit has no branchings. All segments and arcs are connected smoothly, i.e. there are no sharp corners.

The car travels on this circuit with one distinct feature: it is capable of jumping, which enables short cuts. It can jump at any time for any distance. The constraints are that 1) the traveling direction will never change during each jump, 2) the jumping direction needs to match the traveling direction at the time of take-off, and 3) the car must land on the circuit in parallel to the tangent at the landing point. Note that, however, the traveling direction at the landing point may be the opposite of the forward direction (we define forward direction as the direction from the starting point to the ending point of each line segment in the circuit.) That is, the car can traverse part of the circuit in the reverse direction.

Your job is to write a program which, given the shape of the circuit, calculates the per-lap length of the shortest route. You can ignore the height of the jump, i.e. just project the route onto the plane on which the circuit resides. The car must start from the starting point of the first line segment, heading towards the ending point of that segment, and must come back to the same starting point heading in the same direction.

Figure 1 shows the solution for the first sample input.

<image>
Figure 1: The solution for the first sample input



Input

The input begins with a line that solely consists of an integer N (2 <= N <= 100), the number of line segments in the circuit. This is followed by N lines, where the i-th line corresponds to the i-th line segment (1 <= i <= N). Each of these N lines contains 4 integers x0, y0, x1 and y1 (-100 <= x0, y0, x1, y1 <= 100) in this order, separated by a space. Here (x0, y0) is the starting point and (x1, y1) is the ending point of the i-th line segment. For each i, the i-th and (i+1)-th line segments are connected smoothly by a circular arc, which you may assume exists uniquely (for simplicity, we consider the (N+1)-th line as the 1st line). You may also assume that, while two line segments or circular arcs may cross each other, they will never overlap nor be tangent to each other.

Output

For each test case, output one line that solely consists of a decimal value, representing the per-lap length. The output value should be in a decimal fraction and should not contain an error greater than 0.001.

Examples

Input

5
0 1 0 2
1 3 2 3
2 2 1 2
1 1 2 1
2 0 1 0


Output

9.712


Input

12
4 5 4 6
3 7 1 7
0 8 0 10
1 11 3 11
4 10 4 9
5 8 99 8
100 7 100 4
99 3 4 3
3 2 3 1
2 0 1 0
0 1 0 3
1 4 3 4


Output

27.406

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all know how to alphabetize a list of distinct words when you know the alphabet: One word may be a prefix of another longer word, in which case the shorter word always comes before the longer word. With any other two words there must be a first place in the words where their letters differ. Then the order of the words is determined by the lexicographical order of these first differing letters.

How about the reverse problem: Can you find the lexicographic order of the alphabet from an ordered list of words? Suppose an alphabet exists where the following list of word strings is given in lexicographical order:

cab
cda
ccc
badca

It is clear that c comes before b in the underlying alphabet because cab comes before badca. Similarly, we know a comes before d, because cab < cda, a comes before c because cab < ccc, and d comes before c because cda < ccc. The only ordering of the 4 alphabet characters that is possible is adcb.

However, it may be that a list contains inconsistencies that make it impossible to be ordered under any proposed alphabet. For example, in the following list it must be that a comes before b in the alphabet since abc < bca, yet it also must be that b comes before a in the alphabet since bca < aca.

abc
bca
cab
aca

Finally, some lists may not provide enough clues to derive a unique alphabet order, such as the following:

dea
cfb

In this list, d comes before c but we don’t know about the relative positions of any of the other letters, so we are unable to uniquely discern the order of the alphabet characters.

-----Input-----
The first line of input will contain $L$ and $N$, separated by a space, where $L$ is a lowercase character $\texttt{b} \le L \le \texttt{z}$ representing the highest character in the English alphabet that appears in the derived alphabet, and $N$ is an integer $1 \leq N \leq 1000$ that is equal to the number of strings in the list. Each of the next $N$ lines will contain a single nonempty string of length at most $1000$, consisting only of characters in the derived alphabet. No two strings will be the same.

-----Output-----
If the input is consistent with a unique ordering of the alphabet, output a string that designates that ordered alphabet. If the data is inconsistent with any ordering, output IMPOSSIBLE. If the data is consistent with multiple orderings, output AMBIGUOUS.

-----Examples-----
Sample Input 1:
d 4
cab
cda
ccc
badca
Sample Output 1:
adcb

Sample Input 2:
c 4
abc
bca
cab
aca
Sample Output 2:
IMPOSSIBLE

Sample Input 3:
f 2
dea
cfb
Sample Output 3:
AMBIGUOUS

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn't give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor's handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor's signature is impossible to forge. Or is it?

For simplicity, the signature is represented as an $n\times m$ grid, where every cell is either filled with ink or empty. Andrey's pen can fill a $3\times3$ square without its central cell if it is completely contained inside the grid, as shown below. 

xxx

x.x

xxx

 

Determine whether is it possible to forge the signature on an empty $n\times m$ grid.


-----Input-----

The first line of input contains two integers $n$ and $m$ ($3 \le n, m \le 1000$).

Then $n$ lines follow, each contains $m$ characters. Each of the characters is either '.', representing an empty cell, or '#', representing an ink filled cell.


-----Output-----

If Andrey can forge the signature, output "YES". Otherwise output "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
3 3
###
#.#
###

Output
YES
Input
3 3
###
###
###

Output
NO
Input
4 3
###
###
###
###

Output
YES
Input
5 7
.......
.#####.
.#.#.#.
.#####.
.......

Output
YES


-----Note-----

In the first sample Andrey can paint the border of the square with the center in $(2, 2)$.

In the second sample the signature is impossible to forge.

In the third sample Andrey can paint the borders of the squares with the centers in $(2, 2)$ and $(3, 2)$:   we have a clear paper: 

...

...

...

...

  use the pen with center at $(2, 2)$. 

###

#.#

###

...

  use the pen with center at $(3, 2)$. 

###

###

###

###

 

In the fourth sample Andrey can paint the borders of the squares with the centers in $(3, 3)$ and $(3, 5)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vlad has $n$ friends, for each of whom he wants to buy one gift for the New Year.

There are $m$ shops in the city, in each of which he can buy a gift for any of his friends. If the $j$-th friend ($1 \le j \le n$) receives a gift bought in the shop with the number $i$ ($1 \le i \le m$), then the friend receives $p_{ij}$ units of joy. The rectangular table $p_{ij}$ is given in the input.

Vlad has time to visit at most $n-1$ shops (where $n$ is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.

Let the $j$-th friend receive $a_j$ units of joy from Vlad's gift. Let's find the value $\alpha=\min\{a_1, a_2, \dots, a_n\}$. Vlad's goal is to buy gifts so that the value of $\alpha$ is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.

For example, let $m = 2$, $n = 2$. Let the joy from the gifts that we can buy in the first shop: $p_{11} = 1$, $p_{12}=2$, in the second shop: $p_{21} = 3$, $p_{22}=4$.

Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy $3$, and for the second — bringing joy $4$. In this case, the value $\alpha$ will be equal to $\min\{3, 4\} = 3$

Help Vlad choose gifts for his friends so that the value of $\alpha$ is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most $n-1$ shops (where $n$ is the number of friends). In the shop, he can buy any number of gifts.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input.

An empty line is written before each test case. Then there is a line containing integers $m$ and $n$ ($2 \le n$, $2 \le n \cdot m \le 10^5$) separated by a space — the number of shops and the number of friends, where $n \cdot m$ is the product of $n$ and $m$.

Then $m$ lines follow, each containing $n$ numbers. The number in the $i$-th row of the $j$-th column $p_{ij}$ ($1 \le p_{ij} \le 10^9$) is the joy of the product intended for friend number $j$ in shop number $i$.

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


-----Output-----

Print $t$ lines, each line must contain the answer to the corresponding test case — the maximum possible value of $\alpha$, where $\alpha$ is the minimum of the joys from a gift for all of Vlad's friends.


-----Examples-----

Input
5

2 2
1 2
3 4

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

2 3
5 3 4
2 5 1

4 2
7 9
8 1
9 6
10 8

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


-----Note-----

None

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