vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Your friend Salem is Warawreh's brother and only loves math and geometry problems. He has solved plenty of such problems, but according to Warawreh, in order to graduate from university he has to solve more graph problems. Since Salem is not good with graphs he asked your help with the following problem.

<image>

You are given a complete directed graph with n vertices without self-loops. In other words, you have n vertices and each pair of vertices u and v (u ≠ v) has both directed edges (u, v) and (v, u).

Every directed edge of the graph is labeled with a single character: either 'a' or 'b' (edges (u, v) and (v, u) may have different labels).

You are also given an integer m > 0. You should find a path of length m such that the string obtained by writing out edges' labels when going along the path is a palindrome. The length of the path is the number of edges in it.

You can visit the same vertex and the same directed edge any number of times.

Input

The first line contains a single integer t (1 ≤ t ≤ 500) — the number of test cases.

The first line of each test case contains two integers n and m (2 ≤ n ≤ 1000; 1 ≤ m ≤ 10^{5}) — the number of vertices in the graph and desirable length of the palindrome.

Each of the next n lines contains n characters. The j-th character of the i-th line describes the character on the edge that is going from node i to node j.

Every character is either 'a' or 'b' if i ≠ j, or '*' if i = j, since the graph doesn't contain self-loops.

It's guaranteed that the sum of n over test cases doesn't exceed 1000 and the sum of m doesn't exceed 10^5.

Output

For each test case, if it is possible to find such path, print "YES" and the path itself as a sequence of m + 1 integers: indices of vertices in the path in the appropriate order. If there are several valid paths, print any of them.

Otherwise, (if there is no answer) print "NO".

Example

Input


5
3 1
*ba
b*b
ab*
3 3
*ba
b*b
ab*
3 4
*ba
b*b
ab*
4 6
*aaa
b*ba
ab*a
bba*
2 6
*a
b*


Output


YES
1 2
YES
2 1 3 2
YES
1 3 1 3 1
YES
1 2 1 3 4 1 4
NO

Note

The graph from the first three test cases is shown below:

<image>

In the first test case, the answer sequence is [1,2] which means that the path is:

$$$1 \xrightarrow{b} 2$$$

So the string that is obtained by the given path is b.

In the second test case, the answer sequence is [2,1,3,2] which means that the path is:

$$$2 \xrightarrow{b} 1 \xrightarrow{a} 3 \xrightarrow{b} 2$$$

So the string that is obtained by the given path is bab.

In the third test case, the answer sequence is [1,3,1,3,1] which means that the path is:

$$$1 \xrightarrow{a} 3 \xrightarrow{a} 1 \xrightarrow{a} 3 \xrightarrow{a} 1$$$

So the string that is obtained by the given path is aaaa.

The string obtained in the fourth test case is abaaba.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the n numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

Input

The first line contains n (1 ≤ n ≤ 4⋅10^5). The second line contains n integers (1 ≤ a_i ≤ 10^9).

Output

In the first line print x (1 ≤ x ≤ n) — the total number of cells of the required maximum beautiful rectangle. In the second line print p and q (p ⋅ q=x): its sizes. In the next p lines print the required rectangle itself. If there are several answers, print any.

Examples

Input


12
3 1 4 1 5 9 2 6 5 3 5 8


Output


12
3 4
1 2 3 5
3 1 5 4
5 6 8 9


Input


5
1 1 1 1 1


Output


1
1 1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rob needs to give a string to each of his students. There is huge string S that is known to all.
He doesn't want to work much, hence decides to give each of them, some prefix of S.

Now, the students consider their strings holy, if their string is very similar to this known string S.
Now, this similarity comparison is done from suffix matching.

So, now you are to help in this computation. So, given an integer i, find the longest matching suffix
in between S[1...i] and S.

Input:
The first line contains string S.
The next line contains q, the number of queries.
Each of the following q lines contain a number i, denoting the query.

Output:
Output q lines each containing the answer as explained above.

Constraints:
1 ≤ |S| ≤ 200000
1 ≤ q ≤ |S|
1 ≤ i ≤ |S|

SAMPLE INPUT
ababa
5
1
2
3
4
5

SAMPLE OUTPUT
1
0
3
0
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef was busy in solving algebra, he found some interesting results, that there are many numbers which can be formed by sum of some numbers which are prime. Chef wrote those numbers in dairy. Cheffina came and saw what the chef was doing. Cheffina immediately closed chef's dairy and for testing chef's memory, she starts asking numbers and chef needs to answer wheater given number N can be formed by the sum of K prime numbers if it yes then print 1 else print 0. 

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $N, K$.

-----Output:-----
For each test case, output in a single line answer as 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $2 \leq N \leq 10^5$
- $1 \leq K \leq 10^5$

-----Sample Input:-----
2
12 2
11 2

-----Sample Output:-----
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lets wish Horsbug98 on his birthday and jump right into the question.
In Chefland, $6$ new mobile brands have appeared each providing a range of smartphones. For simplicity let the brands be represented by numbers $1$ to $6$. All phones are sold at the superstore. 
There are total $N$ smartphones. Let $P_i$ & $B_i$ be the price and the brand of the $i^{th}$ smartphone. The superstore knows all the price and brand details beforehand. 
Each customer has a preference for brands. The preference is a subset of the brands available (i.e $1$ to $6$). Also, the customer will buy the $K^{th}$ costliest phone among all the phones of his preference.
You will be asked $Q$ queries. Each query consists of the preference of the customer and $K$.
Find the price the customer has to pay for his preference. If no such phone is available, print $-1$
Note that for each query the total number of smartphones is always $N$ since, after each purchase, the phones are replaced instantly.

-----Input:-----
- First Line contains $N$ and $Q$
- Second-line contains $N$ integers $P_1,P_2,...,P_N$ (Price)
- Third line contains $N$ integers $B_1,B_2,...,B_N$ (Brand)
- Each of the next Q lines contains a query, the query is describes below
- First line of each quey contains $b$ and $K$ where $b$ is the size of the preference subset.
- Second line of each query contains $b$ integers, describing the preference subset.

-----Output:-----
For each query, print the price to be paid.

-----Constraints-----
- $1 \leq N, Q, P_i \leq 10^5$
- $1 \leq B_i, b \leq 6$
- $1 \leq K \leq N$

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

-----Sample Output:-----
4

-1

-----Explaination-----
Query 1: The preference subset is {1, 2, 3}, The prices of phones available of these brands are {4, 5, 6}. The third costliest phone is 4.
Query 2: The preference subset is {4, 5, 6}, The prices of phones available of these brands are {7}.
Fouth costliest phone is required, which is not available. Hence, answer is $-1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mathison recently inherited an ancient papyrus that contained some text. Unfortunately, the text was not a
pangram. Now, Mathison has a particular liking for holoalphabetic strings and the text bothers him. The good news is that Mathison can buy letters from the local store in order to turn his text into a pangram.

However, each letter has a price and Mathison is not very rich. Can you help Mathison find the cheapest way to obtain a pangram?

-----Input-----
The first line of the input file will contain one integer, T, representing the number of tests.
Each test will be formed from two lines. The first one contains 26 space-separated integers, representing the prices of all letters.
The second will contain Mathison's initial text (a string of N lowercase letters).

-----Output-----
The output file will contain T lines, one for each test. Each line will contain the answer for the corresponding test.

-----Constraints and notes-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 50,000
- All prices are natural numbers between 1 and 1,000,000 (i.e. 106).
- A pangram is a string that contains every letter of the Latin alphabet at least once.
- All purchased letters are added to the end of the string.

-----Subtaks-----
Subtask #1 (30 points):

- N = 1

Subtask #2 (70 points):

- Original constraints

-----Example-----
Input:
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abcdefghijklmopqrstuvwz
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
thequickbrownfoxjumpsoverthelazydog

Output:
63
0

-----Explanation-----
First test
There are three letters missing from the original string: n (price 14), x (price 24), and y (price 25).
Therefore the answer is 14 + 24 + 25 = 63.

Second test
No letter is missing so there is no point in buying something. The answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string A. Find a string B, where B is a palindrome and A is a subsequence of B.

A subsequence of a string is a string that can be derived from it by deleting some (not necessarily consecutive) characters without changing the order of the remaining characters. For example, "cotst" is a subsequence of "contest".

A palindrome is a string that reads the same forward or backward.

The length of string B should be at most 104. It is guaranteed that there always exists such string.

You do not need to find the shortest answer, the only restriction is that the length of string B should not exceed 104.

Input

First line contains a string A (1 ≤ |A| ≤ 103) consisting of lowercase Latin letters, where |A| is a length of A.

Output

Output single line containing B consisting of only lowercase Latin letters. You do not need to find the shortest answer, the only restriction is that the length of string B should not exceed 104. If there are many possible B, print any of them.

Examples

Input

aba


Output

aba

Input

ab


Output

aabaa

Note

In the first example, "aba" is a subsequence of "aba" which is a palindrome.

In the second example, "ab" is a subsequence of "aabaa" which is a palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers a and b. You also have a number x, which is initially set to 0. At first, you can add a to x any number of times. After that, you can divide x by b any number of times as long as x is divisible by b.

Print YES if you can make x equal to 1, otherwise print NO.

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

- First line of input will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line, two positive integers a, b.

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

For each test case, output on one line YES if it is possible to make x , or NO if it is not possible to do so. 

Output is case insensitive, which means that "yes", "Yes", "YEs", "no", "nO" - all such strings will be acceptable.

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

$1 ≤ T ≤ 100000$
$1 ≤ a, b ≤ 10^{9}$

----- Sample Input 1 ------ 
4
3 10
9 6
7 30
8 12
----- Sample Output 1 ------ 
NO
YES
NO
YES
----- explanation 1 ------ 
Test case $2$: We initially have $x$ set to $0$. Add $a = 9$ to $x$ for $4$ times to make $x$ equal to $36$. And then divide $x$ by $b = 6$ for $2$ times to make $x$ equal to $1$.

Test case $4$: We initially have $x$ set to $0$. Add $a = 8$ to $x$ for $18$ times to make $x$ equal to $144$. And then divide $x$ by $b = 12$ for $2$ times to make $x$ equal to $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke is having a barbeque party.
At the party, he will make N servings of Skewer Meal.
Example of a serving of Skewer Meal
He has a stock of 2N skewers, all of which will be used in Skewer Meal. The length of the i-th skewer is L_i.
Also, he has an infinite supply of ingredients.
To make a serving of Skewer Meal, he picks 2 skewers and threads ingredients onto those skewers.
Let the length of the shorter skewer be x, then the serving can hold the maximum of x ingredients.
What is the maximum total number of ingredients that his N servings of Skewer Meal can hold, if he uses the skewers optimally?

-----Constraints-----
 - 1≦N≦100
 - 1≦L_i≦100
 - For each i, L_i is an integer.

-----Input-----
The input is given from Standard Input in the following format:
N
L_1 L_2 ... L_{2N}

-----Output-----
Print the maximum total number of ingredients that Snuke's N servings of Skewer Meal can hold.

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

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

If he makes a serving using the first and third skewers, and another using the second and fourth skewers, each serving will hold 1 and 2 ingredients, for the total of 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
2048 is a single-player puzzle game created by Gabriele Cirulli1. It is played on a $4 \times 4$ grid that contains integers $\geq 2$ that are powers of 2. The player can use a keyboard arrow key (left/up/right/down) to move all the tiles simultaneously. Tiles slide as far as possible in the chosen direction until they are stopped by either another tile or the edge of the grid. If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. The resulting tile cannot merge with another tile again in the same move. Please observe this merging behavior carefully in all Sample Inputs and Outputs.

-----Input-----
The input is always a valid game state of a 2048 puzzle. The first four lines of input, that each contains four integers, describe the 16 integers in the $4 \times 4$ grid of 2048 puzzle. The $j$-th integer in the $i$-th line denotes the content of the cell located at the $i$-th row and the $j$-th cell. For this problem, all integers in the input will be either {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}. Integer 0 means an empty cell.

The fifth line of input contains an integer 0, 1, 2, or 3 that denotes a left, up, right, or down move executed by the player, respectively.

-----Output-----
Output four lines with four integers each. Two integers in a line must be separated by a single space. This describes the new state of the $4 \times 4$ grid of 2048 puzzle. Again, integer 0 means an empty cell. Note that in this problem, you can ignore the part from the 2048 puzzle where it introduces a new random tile with a value of either 2 or 4 in an empty spot of the board at the start of a new turn.

-----Examples-----
Sample Input 1:
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
0
Sample Output 1:
4 0 0 0
4 16 8 2
2 64 32 4
2048 64 0 0

Sample Input 2:
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
1
Sample Output 2:
2 16 8 4
4 64 32 4
2 1024 64 0
1024 0 0 0

Sample Input 3:
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
2
Sample Output 3:
0 0 0 4
4 16 8 2
2 64 32 4
0 0 2048 64

Sample Input 4:
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
3
Sample Output 4:
2 0 0 0
4 16 8 0
2 64 32 4
1024 1024 64 4

Sample Input 5:
2 2 4 8
4 0 4 4
16 16 16 16
32 16 16 32
0
Sample Output 5:
4 4 8 0
8 4 0 0
32 32 0 0
32 32 32 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I have a sequence defined as follows:

* All even-numbered terms are equal to the previous term multiplied by 2.
* All odd-numbered terms are equal to the previous term divided by 3.



Create a program that reads the first term a of this sequence and outputs the sum s (10) from the first term to the tenth term.



Input

The input consists of multiple test cases. For each test case, a real number a (1.0 ≤ a ≤ 10.0) representing the first term of the sequence is given in one row.

The number of test cases does not exceed 50.

Output

Print s (10) on one line for each test case.

The output may contain an error of 0.000001 or less.

Example

Input

1.0
2.0
3.0


Output

7.81481481
15.62962963
23.44444444

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jim likes to play with laser beams. 

Jim stays at point $(0,0)$. 

There is a mirror at point $(X_m,Y_m)$ and a wall between points $(X_1,Y_1)$ and $(X_2,Y_2)$.

Jim wants to find out if he can point the laser beam on the mirror.

Input Format 

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

Each subsequent line contains one test case: space separated integers that denote endpoints of the wall $X_1,Y_1$, $X_2,Y_2$ and position of the mirror $X_m,Y_m$.  

Output Format 

The answer for each test case: Display YES if Jim can point the laser beam to the mirror, otherwise display NO .  

Constraints 

$1\leq T\leq100$ 

$0≤|X_1|,|Y_1|,|X_2|,|Y_2|,|X_m|,|Y_m|≤10^6$ 

Mirror doesn't have common points with wall. 

Wall doesn't pass through the point $(0,0)$.  

Sample Input

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

Sample Output

NO
YES
NO
YES
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers $x$ and $y$. You can perform the following operation with $x$: write it in its binary form without leading zeros, add $0$ or $1$ to the right of it, reverse the binary form and turn it into a decimal number which is assigned as the new value of $x$.

For example:

$34$ can be turned into $81$ via one operation: the binary form of $34$ is $100010$, if you add $1$, reverse it and remove leading zeros, you will get $1010001$, which is the binary form of $81$.

$34$ can be turned into $17$ via one operation: the binary form of $34$ is $100010$, if you add $0$, reverse it and remove leading zeros, you will get $10001$, which is the binary form of $17$.

$81$ can be turned into $69$ via one operation: the binary form of $81$ is $1010001$, if you add $0$, reverse it and remove leading zeros, you will get $1000101$, which is the binary form of $69$.

$34$ can be turned into $69$ via two operations: first you turn $34$ into $81$ and then $81$ into $69$.

Your task is to find out whether $x$ can be turned into $y$ after a certain number of operations (possibly zero).


-----Input-----

The only line of the input contains two integers $x$ and $y$ ($1 \le x, y \le 10^{18}$).


-----Output-----

Print YES if you can make $x$ equal to $y$ and NO if you can't.


-----Examples-----

Input
3 3
Output
YES
Input
7 4
Output
NO
Input
2 8
Output
NO
Input
34 69
Output
YES
Input
8935891487501725 71487131900013807
Output
YES


-----Note-----

In the first example, you don't even need to do anything.

The fourth example is described in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: An overnight dance in discotheque

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?

The discotheque can be seen as an infinite *xy*-plane, in which there are a total of *n* dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area *C**i* described by a center (*x**i*,<=*y**i*) and a radius *r**i*. No two ranges' borders have more than one common point, that is for every pair (*i*,<=*j*) (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*) either ranges *C**i* and *C**j* are disjoint, or one of them is a subset of the other. Note that it's possible that two ranges' borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.

But no one keeps moving for the whole night after all, so the whole night's time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.

Input Specification:
The first line of input contains a positive integer *n* (1<=≤<=*n*<=≤<=1<=000) — the number of dancers.

The following *n* lines each describes a dancer: the *i*-th line among them contains three space-separated integers *x**i*, *y**i* and *r**i* (<=-<=106<=≤<=*x**i*,<=*y**i*<=≤<=106, 1<=≤<=*r**i*<=≤<=106), describing a circular movement range centered at (*x**i*,<=*y**i*) with radius *r**i*.

Output Specification:
Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10<=-<=9. Formally, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct if .

Demo Input:
['5\n2 1 6\n0 4 1\n2 -1 3\n1 -2 1\n4 -1 1\n', '8\n0 0 1\n0 0 2\n0 0 3\n0 0 4\n0 0 5\n0 0 6\n0 0 7\n0 0 8\n']

Demo Output:
['138.23007676\n', '289.02652413\n']

Note:
The first sample corresponds to the illustrations in the legend.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrey needs one more problem to conduct a programming contest. He has *n* friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends — the probability that this friend will come up with a problem if Andrey asks him.

Help Andrey choose people to ask. As he needs only one problem, Andrey is going to be really upset if no one comes up with a problem or if he gets more than one problem from his friends. You need to choose such a set of people that maximizes the chances of Andrey not getting upset.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of Andrey's friends. The second line contains *n* real numbers *p**i* (0.0<=≤<=*p**i*<=≤<=1.0) — the probability that the *i*-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.

Output Specification:
Print a single real number — the probability that Andrey won't get upset at the optimal choice of friends. The answer will be considered valid if it differs from the correct one by at most 10<=-<=9.

Demo Input:
['4\n0.1 0.2 0.3 0.8\n', '2\n0.1 0.2\n']

Demo Output:
['0.800000000000\n', '0.260000000000\n']

Note:
In the first sample the best strategy for Andrey is to ask only one of his friends, the most reliable one.

In the second sample the best strategy for Andrey is to ask all of his friends to come up with a problem. Then the probability that he will get exactly one problem is 0.1·0.8 + 0.9·0.2 = 0.26.

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