vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
One fall day Joe got bored because he couldn't find himself something interesting to do. Marty suggested Joe to generate a string of length n to entertain him somehow. It didn't seem particularly difficult, but Joe's generated string had to follow these rules:

  * the string may only contain characters 'a', 'b', or 'c'; 
  * the maximum length of a substring of this string that is a palindrome does not exceed k. 

<image>

A string a is a substring of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. For example, strings "a", "bc", "abc" are substrings of a string "abc", while strings "ac", "ba", "cba" are not.

A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, strings "abccba", "abbba", "aba", "abacaba", "a", and "bacab" are palindromes, while strings "abcbba", "abb", and "ab" are not.

Now Joe wants to find any correct string. Help him! It can be proven that the answer always exists under the given constraints.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10).

The only line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 1 000) — the required string length and the maximum length of a palindrome substring, respectively.

Output

For each test case, print any string that satisfies the conditions from the problem statement. If there are multiple correct answers, you can print any one of them. It can be proven that the answer always exists under the given constraints.

Example

Input


2
3 2
4 1


Output


aab
acba

Note

In the first test case of the example, the palindrome substring with the maximum length is "aa". Its length does not exceed 2, so it fits.

In the second test case all palindrome substrings have the length one.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike has *n* strings *s*1,<=*s*2,<=...,<=*s**n* each consisting of lowercase English letters. In one move he can choose a string *s**i*, erase the first character and append it to the end of the string. For example, if he has the string "coolmike", in one move he can transform it into the string "oolmikec".

Now Mike asks himself: what is minimal number of moves that he needs to do in order to make all the strings equal?

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=50) — the number of strings.

This is followed by *n* lines which contain a string each. The *i*-th line corresponding to string *s**i*. Lengths of strings are equal. Lengths of each string is positive and don't exceed 50.

Output Specification:
Print the minimal number of moves Mike needs in order to make all the strings equal or print <=-<=1 if there is no solution.

Demo Input:
['4\nxzzwo\nzwoxz\nzzwox\nxzzwo\n', '2\nmolzv\nlzvmo\n', '3\nkc\nkc\nkc\n', '3\naa\naa\nab\n']

Demo Output:
['5\n', '2\n', '0\n', '-1\n']

Note:
In the first sample testcase the optimal scenario is to perform operations in such a way as to transform all strings into "zwoxz".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya and his friend Vasya play an interesting game. Petya randomly chooses an integer p from the interval [pl, pr] and Vasya chooses an integer v from the interval [vl, vr] (also randomly). Both players choose their integers equiprobably. Find the probability that the interval [min(v, p), max(v, p)] contains exactly k lucky numbers.

Input

The single line contains five integers pl, pr, vl, vr and k (1 ≤ pl ≤ pr ≤ 109, 1 ≤ vl ≤ vr ≤ 109, 1 ≤ k ≤ 1000).

Output

On the single line print the result with an absolute error of no more than 10 - 9.

Examples

Input

1 10 1 10 2


Output

0.320000000000


Input

5 6 8 10 1


Output

1.000000000000

Note

Consider that [a, b] denotes an interval of integers; this interval includes the boundaries. That is, <image>

In first case there are 32 suitable pairs: (1, 7), (1, 8), (1, 9), (1, 10), (2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10), (4, 7), (4, 8), (4, 9), (4, 10), (7, 1), (7, 2), (7, 3), (7, 4), (8, 1), (8, 2), (8, 3), (8, 4), (9, 1), (9, 2), (9, 3), (9, 4), (10, 1), (10, 2), (10, 3), (10, 4). Total number of possible pairs is 10·10 = 100, so answer is 32 / 100.

In second case Petya always get number less than Vasya and the only lucky 7 is between this numbers, so there will be always 1 lucky number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A matrix B (consisting of integers) of dimension N × N is said to be good if there exists an array A (consisting of integers) such that B[i][j]  = |A[i] - A[j]|, where |x| denotes absolute value of integer x.
You are given a partially filled matrix B of dimension N × N. Q of the entries of this matrix are filled by either 0 or 1. You have to identify whether it is possible to fill the remaining entries of matrix B (the entries can be filled by any integer, not necessarily by 0 or 1) such that the resulting fully filled matrix B is good.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. 
The first line of each test case contains two space separated integers N, Q.
Each of the next Q lines contain three space separated integers i, j, val, which means that B[i][j] is filled with value val.

-----Output-----
For each test case, output "yes" or "no" (without quotes) in a single line corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ T ≤ 106
- 2 ≤ N ≤ 105
- 1 ≤ Q ≤ 106
- 1 ≤ i, j ≤ N
- 0 ≤ val ≤ 1
- Sum of each of N, Q over all test cases doesn't exceed 106

-----Subtasks-----
- Subtask #1 (40 points) 2 ≤ N ≤ 103, 1 ≤ Q ≤ 103, Sum of each of N, Q over all test cases doesn't exceed 104
- Subtask #2 (60 points) Original Constraints

-----Example-----
Input
4
2 2
1 1 0
1 2 1
2 3
1 1 0
1 2 1
2 1 0
3 2
2 2 0
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Output
yes
no
yes
no

-----Explanation-----
Example 1. You can fill the entries of matrix B as follows. 

0 1
1 0
This matrix corresponds to the array A = [1, 2].

Example 2. It is impossible to fill the remaining entries of matrix B such that the resulting matrix is good, as B[1][2] = 1 and B[2][1] = 0, which is impossible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ikta, who was in trouble because he couldn't come up with an idea for the problem to be presented at the training camp of the programming contest, consulted with a friend one day.

Mr. Ikta "I want to create a problem that cannot be solved without using such an algorithm. Is there anything?"

Friend "Then why not think about something like this?"

In this way, the friend came up with the idea that would be the basis for the following problems.

Given binary numbers A and B, process the following query.

* Output query: Outputs the number of 1s when max {x is expressed in binary | A ≤ x <A + B}
* A change query: Inverts the i-th bit (0-origin) from the least significant bit of A
* B change query: Inverts the i-th bit (0-origin) from the least significant bit of B



Note that the i-bit is represented by 0-origin. That is, the 0th bit from the least significant bit of A represents the least significant bit.



Input

The input is given in the following format.


N A B
Q1
...
QN

The number of queries N, binary numbers A and B are given in the first line.

The following query is given in the 2nd to N + 1 lines.

* Q
* A i
* B i



Q represents the output query, and A i and B i represent the change query that inverts the i-th bit from the least significant bit of A and the i-th bit from the least significant bit of B, respectively.

Constraints

Each variable being input satisfies the following constraints.

* 1 ≤ N <300,000
* 1 ≤ | A |, | B | ≤ 300,000 (| A | is the length of A)
* In the query A i, 0 ≤ i <| A |
* In the query B i 0 ≤ i <| B |
* B can never be 0

Output

Print the answer on one line for each output query.

Examples

Input

4 10000 00101
Q
A 0
B 1
Q


Output

3
4


Input

9 0110111101 0010100111
Q
B 4
Q
A 4
Q
B 9
Q
A 8
Q


Output

9
9
9
10
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an undirected graph G with n vertices. There is a value a_i in each vertex.

Two vertices i and j are connected with an edge if and only if gcd(a_i, a_j) > 1, where gcd(x, y) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers x and y.

Consider a set of vertices. Let's call a vertex in this set fair if it is connected with an edge with all other vertices in this set.

You need to find a set of k vertices (where k is a given integer, 2 ⋅ k ≤ n) where all vertices are fair or all vertices are not fair. One can show that such a set always exists.

Input

The first line contains integers n and k (6 ≤ 2 ⋅ k ≤ n ≤ 10^5) — the number of vertices and parameter k.

The second line contains n integers a_1, a_2, …, a_n (2 ≤ a_i ≤ 10^7) — the values in the vertices.

Output

Print exactly k distinct integers — the indices of the vertices in the chosen set in any order.

Examples

Input


6 3
6 15 10 8 14 12


Output


2 4 5

Input


8 4
11 15 10 6 21 15 10 6


Output


5 7 1 2

Input


10 5
3003 17017 3230 49742 546 41990 17765 570 21945 36465


Output


1 2 4 5 6

Note

In the first test case, set \{2, 4, 5\} is an example of set where no vertices are fair. The vertex 2 does not share an edge with vertex 4 since gcd(15, 8) = 1. The vertex 4 does not share an edge with vertex 2. The vertex 5 does not share an edge with vertex 2.

In the second test case, set \{8, 5, 6, 4\} is an example of a set where all vertices are fair.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of *n*<=×<=*m* cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

Input Specification:
First line of the input contains three integers *n*, *m* and *k* (3<=≤<=*n*,<=*m*<=≤<=1000,<=1<=≤<=*k*<=≤<=*min*(*n*·*m*,<=100<=000)) — the museum dimensions and the number of starting positions to process.

Each of the next *n* lines contains *m* symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last *k* lines contains two integers *x* and *y* (1<=≤<=*x*<=≤<=*n*,<=1<=≤<=*y*<=≤<=*m*) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

Output Specification:
Print *k* integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

Demo Input:
['5 6 3\n******\n*..*.*\n******\n*....*\n******\n2 2\n2 5\n4 3\n', '4 4 1\n****\n*..*\n*.**\n****\n3 2\n']

Demo Output:
['6\n4\n10\n', '8\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For NWERC 2018, the organisers have done something rather special with the balloons. Instead of buying balloons of equal size, they bought one balloon of every integer size from $1$ up to $n$. A balloon of size $s$ has a capacity of $s$ decilitres. 

To avoid inflating the balloons by hand, the organisers also bought $n$ helium gas canisters. Each canister can only be used to inflate one balloon, and must be emptied completely into that balloon (it is not possible to disconnect a canister from a balloon before the canister has been fully used).

Unfortunately the gas canisters were bought at a garage sale, and may contain differing amounts of helium. Some may even be empty! To make the best of this challenging situation, the canisters will have to be paired with the balloons smartly.

The organisers want to assign all of the gas canisters to separate balloons, such that the balloon that is inflated the least (relative to its capacity) still contains the maximum possible fraction of helium inside. What is the maximum such (minimum) fraction that is possible?

Balloons filled beyond their capacity will explode. Explosions are upsetting and must be avoided.

-----Input-----
The input consists of:
 - One line with the integer $n$ ($1 \le n \le 2\cdot 10^5$), the number of balloons and gas canisters.
 - One line with $n$ integers $c_1, \ldots , c_ n$ ($0 \le c_ i \le n$ for each $i$), the amounts of helium in the gas canisters, in decilitres.

-----Output-----
If it is possible to fill all the balloons without any exploding, output the maximum fraction $f$ such that every balloon can be filled to at least $f$ of its capacity. Otherwise, output “impossible”.

Your answer should have an absolute or relative error of at most $10^{-6}$.

-----Examples-----
Sample Input 1:
6
6 1 3 2 2 3
Sample Output 1:
0.6

Sample Input 2:
2
2 2
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Chris is very keen on his toy blocks. His teacher, however, wants Chris to solve more problems, so he decided to play a trick on Chris.

There are exactly s blocks in Chris's set, each block has a unique number from 1 to s. Chris's teacher picks a subset of blocks X and keeps it to himself. He will give them back only if Chris can pick such a non-empty subset Y from the remaining blocks, that the equality holds: $\sum_{x \in X}(x - 1) = \sum_{y \in Y}(s - y)$ "Are you kidding me?", asks Chris.

For example, consider a case where s = 8 and Chris's teacher took the blocks with numbers 1, 4 and 5. One way for Chris to choose a set is to pick the blocks with numbers 3 and 6, see figure. Then the required sums would be equal: (1 - 1) + (4 - 1) + (5 - 1) = (8 - 3) + (8 - 6) = 7.

 $\left. \begin{array}{l l l l l l}{1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} \end{array} \right.$ 

However, now Chris has exactly s = 10^6 blocks. Given the set X of blocks his teacher chooses, help Chris to find the required set Y!


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 5·10^5), the number of blocks in the set X. The next line contains n distinct space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^6), the numbers of the blocks in X.

Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.


-----Output-----

In the first line of output print a single integer m (1 ≤ m ≤ 10^6 - n), the number of blocks in the set Y. In the next line output m distinct space-separated integers y_1, y_2, ..., y_{m} (1 ≤ y_{i} ≤ 10^6), such that the required equality holds. The sets X and Y should not intersect, i.e. x_{i} ≠ y_{j} for all i, j (1 ≤ i ≤ n; 1 ≤ j ≤ m). It is guaranteed that at least one solution always exists. If there are multiple solutions, output any of them.


-----Examples-----
Input
3
1 4 5

Output
2
999993 1000000
Input
1
1

Output
1
1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order. 

After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.

Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: s_{i} ≠ t_{i}. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters s_{i} and t_{i} according to their order in alphabet.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 100): number of names.

Each of the following n lines contain one string name_{i} (1 ≤ |name_{i}| ≤ 100), the i-th name. Each name contains only lowercase Latin letters. All names are different.


-----Output-----

If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).

Otherwise output a single word "Impossible" (without quotes).


-----Examples-----
Input
3
rivest
shamir
adleman

Output
bcdefghijklmnopqrsatuvwxyz

Input
10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer

Output
Impossible

Input
10
petr
egor
endagorion
feferivan
ilovetanyaromanova
kostka
dmitriyh
maratsnowbear
bredorjaguarturnik
cgyforever

Output
aghjlnopefikdmbcqrstuvwxyz

Input
7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck

Output
acbdefhijklmnogpqrstuvwxyz

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today DZY begins to play an old game. In this game, he is in a big maze with n rooms connected by m corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly.

DZY has got lost in the maze. Currently he is in the first room and has k lives. He will act like the follows:

  * Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked. 
  * Then he will go through the corridor and then the process repeats. 



There are some rooms which have traps in them. The first room definitely has no trap, the n-th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the n-th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

Input

The first line contains three integers n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap.

Then m lines follows. Each of them contains two integers ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), meaning that current corridor connects two rooms ui and vi. It is guaranteed that the corridor system is connected.

Output

Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Examples

Input

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


Output

0.25000000


Input

3 2 2
0 1 1
1 2
2 3


Output

-0.00000000


Input

2 1 3
0 1
1 2


Output

1.00000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As behooves any intelligent schoolboy, Kevin Sun is studying psycowlogy, cowculus, and cryptcowgraphy at the Bovinia State University (BGU) under Farmer Ivan. During his Mathematics of Olympiads (MoO) class, Kevin was confronted with a weird functional equation and needs your help. For two fixed integers k and p, where p is an odd prime number, the functional equation states that $f(k x \operatorname{mod} p) \equiv k \cdot f(x) \operatorname{mod} p$ 

for some function $f : \{0,1,2, \cdots, p - 1 \} \rightarrow \{0,1,2, \cdots, p - 1 \}$. (This equation should hold for any integer x in the range 0 to p - 1, inclusive.)

It turns out that f can actually be many different functions. Instead of finding a solution, Kevin wants you to count the number of distinct functions f that satisfy this equation. Since the answer may be very large, you should print your result modulo 10^9 + 7.


-----Input-----

The input consists of two space-separated integers p and k (3 ≤ p ≤ 1 000 000, 0 ≤ k ≤ p - 1) on a single line. It is guaranteed that p is an odd prime number.


-----Output-----

Print a single integer, the number of distinct functions f modulo 10^9 + 7.


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

Output
3

Input
5 4

Output
25



-----Note-----

In the first sample, p = 3 and k = 2. The following functions work:   f(0) = 0, f(1) = 1, f(2) = 2.  f(0) = 0, f(1) = 2, f(2) = 1.  f(0) = f(1) = f(2) = 0.

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