vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Karan has his B'day today so,he invites his friends,relatives for party.But now the  problem arises that number of people in the party has increased.So, now Karan want his B'day cake should be given to all people present in the party keeping in mind that each Special person in party should have 100gm, Best friends should have 50gm, friends should have 25gm amount from the original cake.
So now you have to help Karan and you are given X gm of cake which you have to divide in 3 group(Special person,Best Friends,Friends)
such that each member of the group get the share not less than as state above.If such division is possible than print total ratio of the cake taken by each group, if not print No.

INPUT
Fist line would be T testcase (T<100) followed by T lines which have Quantity of cake in grams(cake ≤ constraints are n ≤ 36000000) and number of people in three groups separated by space

OUTPUT
If the division is possible for all group than print amount of cake only not units taken by each group else print No.
If after giving each member  there respective amount of cake, than left over cake  is to be given to
Special person
Best Friends 
Friends
if and only if every person of group get it.If not Print No,order
of priority given above should be taken in mind.You can give cake to group as 
many time as you can,but keeping in mind the given condition.
Consider the test Case
25 1 1 1
so here only friends will have not other you have to print No.
175 1 1 1
here sf =100,bf=50 and f=25 and there sum(100+50+25=175) so you have to print 100 50 25

SAMPLE INPUT
2
1500 8 8 2
500 2 5 7

SAMPLE OUTPUT
800 400 300
No

Explanation

So in 1st case you are given 1500gm of cake and on dividing this in group

Special Person 100*8=800

Best Friends  50*8=400

Friends 25*2=50

and now left with 250 gm of cake so on dividing this Special and Best friends each member will not get the cake so friends get their share of 50 and now leftover is 200 than again check we will left with 150 and repeatedly doing this at last friends share is 300.
2nd Case

Special Person 100*2=200

Best Friends  50*5=250

Friends 25*7=175

which equals to 200+250+175=625
so answer is No

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

John runs a shop, bought some goods, and then sells them. He used a special accounting method, like this:
```
[[60,20],[60,-20]]
```
Each sub array records the commodity price and profit/loss to sell (percentage). Positive mean profit and negative means loss.

In the example above, John's first commodity sold at a price of $60, he made a profit of 20%; Second commodities are sold at a price of $60 too, but he lost 20%.

Please calculate, whether his account is profit or loss in the end?
    
## Rules

Write a function ```profitLoss```, argument ```records``` is the list of sales.

return a number(positive or negative), round to two decimal places.
    

## Examples

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera is a little boy. Yesterday he got a huge Math hometask at school, so Valera didn't have enough time to properly learn the English alphabet for his English lesson. Unfortunately, the English teacher decided to have a test on alphabet today. At the test Valera got a square piece of squared paper. The length of the side equals n squares (n is an odd number) and each unit square contains some small letter of the English alphabet.

Valera needs to know if the letters written on the square piece of paper form letter "X". Valera's teacher thinks that the letters on the piece of paper form an "X", if:  on both diagonals of the square paper all letters are the same;  all other squares of the paper (they are not on the diagonals) contain the same letter that is different from the letters on the diagonals. 

Help Valera, write the program that completes the described task for him.


-----Input-----

The first line contains integer n (3 ≤ n < 300; n is odd). Each of the next n lines contains n small English letters — the description of Valera's paper.


-----Output-----

Print string "YES", if the letters on the paper form letter "X". Otherwise, print string "NO". Print the strings without quotes.


-----Examples-----
Input
5
xooox
oxoxo
soxoo
oxoxo
xooox

Output
NO

Input
3
wsw
sws
wsw

Output
YES

Input
3
xpx
pxp
xpe

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the sequence a_1, a_2, ..., a_n. You can choose any subset of elements and then reorder them to create a "saw".

The sequence b_1, b_2, ..., b_m is called a "saw" if the elements satisfy one of the following series of inequalities: b_1>b_2<b_3>b_4<... or b_1<b_2>b_3<b_4>....

Find the longest saw which can be obtained from a given array.

Note that both the given sequence a and the required saw b can contain duplicated (non-unique) values.

Input

The first line contains an integer t (1 ≤ t ≤ 10^5) — the number of test cases in the input. Then the descriptions of the t test cases follow. Each test case begins with a line containing integer n (1 ≤ n ≤ 2⋅10^5). Then a line containing n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) follows.

It's guaranteed that ∑{n} doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print two lines: print the length of the longest saw in the first line, and the saw itself in the second line. If there are several solutions, print any of them.

Example

Input


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


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length n such that some cells of this line are empty and some contain obstacles. Then, he places his grasshopper to one of the empty cells and a small insect in another empty cell. The grasshopper wants to eat the insect.

Ostap knows that grasshopper is able to jump to any empty cell that is exactly k cells away from the current (to the left or to the right). Note that it doesn't matter whether intermediate cells are empty or not as the grasshopper makes a jump over them. For example, if k = 1 the grasshopper can jump to a neighboring cell only, and if k = 2 the grasshopper can jump over a single cell.

Your goal is to determine whether there is a sequence of jumps such that grasshopper will get from his initial position to the cell with an insect.


-----Input-----

The first line of the input contains two integers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1) — the number of cells in the line and the length of one grasshopper's jump.

The second line contains a string of length n consisting of characters '.', '#', 'G' and 'T'. Character '.' means that the corresponding cell is empty, character '#' means that the corresponding cell contains an obstacle and grasshopper can't jump there. Character 'G' means that the grasshopper starts at this position and, finally, 'T' means that the target insect is located at this cell. It's guaranteed that characters 'G' and 'T' appear in this line exactly once.


-----Output-----

If there exists a sequence of jumps (each jump of length k), such that the grasshopper can get from his initial position to the cell with the insect, print "YES" (without quotes) in the only line of the input. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
5 2
#G#T#

Output
YES

Input
6 1
T....G

Output
YES

Input
7 3
T..#..G

Output
NO

Input
6 2
..GT..

Output
NO



-----Note-----

In the first sample, the grasshopper can make one jump to the right in order to get from cell 2 to cell 4.

In the second sample, the grasshopper is only able to jump to neighboring cells but the way to the insect is free — he can get there by jumping left 5 times.

In the third sample, the grasshopper can't make a single jump.

In the fourth sample, the grasshopper can only jump to the cells with odd indices, thus he won't be able to reach the insect.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every natural number, ```n```, may have a prime factorization like:



We define the arithmetic derivative of ```n```, ```n'``` the value of the expression:



Let's do the calculation for ```n = 231525```.
```
231525 = 3³5²7³ 
n' = (3*3²)*5²7³ + 3³*(2*5)*7³ + 3³*5²*(3*7²) = 231525 + 92610 + 99225 = 423360
```
We may make a chain of arithmetic derivatives, starting from a number we apply to the result the transformation and so on until we get the result ```1```.
```
n ---> n'  ---> (n')' ---> ((n')')' ---> ..... ---> ((...(n')...)')'
```
Let's do it starting with our number, ```n = 231525``` and making a chain of 5 terms:
```
231525 ---> 423360 ---> 1899072 ---> 7879680 ---> 51895296
```
We need a function ```chain_arith_deriv()``` that receives two arguments: ```start``` and ```k```, amount of terms of the chain.

The function should output the chain in an array format:
```
chain_arith_deriv(start, k) ---> [start, term1, term2, .....term(k-1)] # a total of k-terms
```
For the case presented above:
```python
chain_arith_deriv(231525, 5) == [231525, 423360, 1899072, 7879680, 51895296]
```
The function has to reject prime numbers giving an alerting message
```python
chain_arith_deriv(997, 5) == "997 is a prime number"
```
Features of the tests:
```
Number of Random Tests: 50
1000 ≤ start ≤ 99000000
3 ≤ k ≤ 15
```
Enjoy it and do your best!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Chef studied the binary numeral system and noticed that it is extremely simple to perform bitwise operations like AND, XOR or bit shift on non-negative integers, while it is much more complicated to perform arithmetic operations (e.g. addition, multiplication or division).
After playing with binary operations for a while, Chef invented an interesting algorithm for addition of two non-negative integers $A$ and $B$:
function add(A, B):
while B is greater than 0:
U = A XOR B
V = A AND B
A = U
B = V * 2
return A

Now Chef is wondering how fast this algorithm is. Given the initial values of $A$ and $B$ (in binary representation), he needs you to help him compute the number of times the while-loop of the algorithm is repeated.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single string $A$.
- The second line contains a single string $B$.

-----Output-----
For each test case, print a single line containing one integer ― the number of iterations the algorithm will perform during addition of the given numbers $A$ and $B$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le |A|, |B| \le 10^5$
- $A$ and $B$ contain only characters '0' and '1'
- the sum of $|A| + |B|$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points): $|A|, |B| \le 30$
Subtask #2 (30 points):
- $|A|, |B| \le 500$
- the sum of $|A| + |B|$ over all test cases does not exceed $10^5$
Subtask #3 (50 points): original constraints

-----Example Input-----
3
100010
0
0
100010
11100
1010

-----Example Output-----
0
1
3

-----Explanation-----
Example case 1: The initial value of $B$ is $0$, so while-loop is not performed at all.
Example case 2: The initial values of $A$ and $B$ are $0_2 = 0$ and $100010_2 = 34$ respectively. When the while-loop is performed for the first time, we have:
- $U = 34$
- $V = 0$
- $A$ changes to $34$
- $B$ changes to $2 \cdot 0 = 0$
The while-loop terminates immediately afterwards, so it is executed only once.
Example case 3: The initial values of $A$ and $B$ are $11100_2 = 28$ and $1010_2 = 10$ respectively. After the first iteration, their values change to $22$ and $16$ respectively. After the second iteration, they change to $6$ and $32$, and finally, after the third iteration, to $38$ and $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There exist certain strings, known as $Unique$ $Strings$. They possess a unique property: 
- The character 'c' gets converted to "ff" and the character 'k' gets converted to "gg". Any letter besides 'c' and 'k' does not get converted to any other character.
Your job is to count the number of strings that could possibly be represented by a given unique string. Since the value could be very large, output the remainder when divided by $10^9+7$.
Note that if the given string is not a unique string, i.e. it contains either 'c' or 'k', output $0$.

-----Input:-----
- The first line of input contains a string, $s$.

-----Output:-----
- Output in a single line the possible number of strings modulo $10^9+7$.

-----Constraints-----
- $1 \leq |s| \leq 10^5$
where |s| denotes length of string.

-----Sample Input 1:-----
thing

-----Sample Input 2:-----
ggdffn

-----Sample Input 3:-----
fff

-----Sample Input 4:-----
cat

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

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

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

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

-----EXPLANATION:-----
The possible strings that can be represented by the given string in each of the examples are as follows:
$1)$ 'thing'
$2)$ 'ggdffn','kdffn','ggdcn','kdcn'
$3)$ 'fff','cf','fc'
$4)$ Since the string 'cat' contains 'c', it is certain that this string is not a unique string. Hence, the output is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lauren has a chart of distinct projected prices for a house over the next several years.  She must buy the house in one year and sell it in another, and she must do so at a loss.  She wants to minimize her financial loss.  

Example 

$price=[20,15,8,2,12]$   

Her minimum loss is incurred by purchasing in year $2$ at $price[1]=15$ and reselling in year $5$ at $price[4]=12$.  Return $15-12=3$.  

Function Description  

Complete the minimumLoss function in the editor below.   

minimumLoss has the following parameter(s):  

int price[n]: home prices at each year  

Returns   

int: the minimum loss possible  

Input Format

The first line contains an integer $n$, the number of years of house data. 

The second line contains $n$ space-separated long integers that describe each $\textit{price[i]}$.

Constraints

$2\leq n\leq2\times10^5$
$1\leq price[i]\leq10^{16}$
All the prices are distinct. 
A valid answer exists.

Subtasks

$2\leq n\leq1000$ for $50\%$ of the maximum score. 

Sample Input 0
3
5 10 3

Sample Output 0
2

Explanation 0

Lauren buys the house in year $1$ at $price[0]=5$ and sells it in year $3$ at $price[2]=3$ for a minimal loss of $5-3=2$.

Sample Input 1
5
20 7 8 2 5

Sample Output 1
2

Explanation 1

Lauren buys the house in year $2$ at $price[1]=7$ and sells it in year $5$ at $price[4]=5$ for a minimal loss of $7-5=2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ points on the plane. The polygon formed from all the $n$ points is strictly convex, that is, the polygon is convex, and there are no three collinear points (i.e. lying in the same straight line). The points are numbered from $1$ to $n$, in clockwise order.

We define the distance between two points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ as their Manhattan distance: $$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$

Furthermore, we define the perimeter of a polygon, as the sum of Manhattan distances between all adjacent pairs of points on it; if the points on the polygon are ordered as $p_1, p_2, \ldots, p_k$ $(k \geq 3)$, then the perimeter of the polygon is $d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)$.

For some parameter $k$, let's consider all the polygons that can be formed from the given set of points, having any $k$ vertices, such that the polygon is not self-intersecting. For each such polygon, let's consider its perimeter. Over all such perimeters, we define $f(k)$ to be the maximal perimeter.

Please note, when checking whether a polygon is self-intersecting, that the edges of a polygon are still drawn as straight lines. For instance, in the following pictures:

 [Image] 

In the middle polygon, the order of points ($p_1, p_3, p_2, p_4$) is not valid, since it is a self-intersecting polygon. The right polygon (whose edges resemble the Manhattan distance) has the same order and is not self-intersecting, but we consider edges as straight lines. The correct way to draw this polygon is ($p_1, p_2, p_3, p_4$), which is the left polygon.

Your task is to compute $f(3), f(4), \ldots, f(n)$. In other words, find the maximum possible perimeter for each possible number of points (i.e. $3$ to $n$).


-----Input-----

The first line contains a single integer $n$ ($3 \leq n \leq 3\cdot 10^5$) — the number of points. 

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^8 \leq x_i, y_i \leq 10^8$) — the coordinates of point $p_i$.

The set of points is guaranteed to be convex, all points are distinct, the points are ordered in clockwise order, and there will be no three collinear points.


-----Output-----

For each $i$ ($3\leq i\leq n$), output $f(i)$.


-----Examples-----
Input
4
2 4
4 3
3 0
1 3

Output
12 14 
Input
3
0 0
0 2
2 0

Output
8 


-----Note-----

In the first example, for $f(3)$, we consider four possible polygons:   ($p_1, p_2, p_3$), with perimeter $12$.  ($p_1, p_2, p_4$), with perimeter $8$.  ($p_1, p_3, p_4$), with perimeter $12$.  ($p_2, p_3, p_4$), with perimeter $12$. 

For $f(4)$, there is only one option, taking all the given points. Its perimeter $14$.

In the second example, there is only one possible polygon. Its perimeter is $8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the $n$ days of summer. On the $i$-th day, $a_i$ millimeters of rain will fall. All values $a_i$ are distinct.

The mayor knows that citizens will watch the weather $x$ days before the celebration and $y$ days after. Because of that, he says that a day $d$ is not-so-rainy if $a_d$ is smaller than rain amounts at each of $x$ days before day $d$ and and each of $y$ days after day $d$. In other words, $a_d < a_j$ should hold for all $d - x \le j < d$ and $d < j \le d + y$. Citizens only watch the weather during summer, so we only consider such $j$ that $1 \le j \le n$.

Help mayor find the earliest not-so-rainy day of summer.


-----Input-----

The first line contains three integers $n$, $x$ and $y$ ($1 \le n \le 100\,000$, $0 \le x, y \le 7$) — the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after.

The second line contains $n$ distinct integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ denotes the rain amount on the $i$-th day.


-----Output-----

Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.


-----Examples-----
Input
10 2 2
10 9 6 7 8 3 2 1 4 5

Output
3

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

Output
8

Input
5 5 5
100000 10000 1000 100 10

Output
5



-----Note-----

In the first example days $3$ and $8$ are not-so-rainy. The $3$-rd day is earlier.

In the second example day $3$ is not not-so-rainy, because $3 + y = 6$ and $a_3 > a_6$. Thus, day $8$ is the answer. Note that $8 + y = 11$, but we don't consider day $11$, because it is not summer.

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

An international expedition discovered abandoned Buddhist cave temples in a giant cliff standing on the middle of a desert. There were many small caves dug into halfway down the vertical cliff, which were aligned on square grids. The archaeologists in the expedition were excited by Buddha's statues in those caves. More excitingly, there were scrolls of Buddhism sutras (holy books) hidden in some of the caves. Those scrolls, which estimated to be written more than thousand years ago, were of immeasurable value.

The leader of the expedition wanted to collect as many scrolls as possible. However, it was not easy to get into the caves as they were located in the middle of the cliff. The only way to enter a cave was to hang you from a helicopter. Once entered and explored a cave, you can climb down to one of the three caves under your cave; i.e., either the cave directly below your cave, the caves one left or right to the cave directly below your cave. This can be repeated for as many times as you want, and then you can descent down to the ground by using a long rope.

So you can explore several caves in one attempt. But which caves you should visit? By examining the results of the preliminary attempts, a mathematician member of the expedition discovered that (1) the caves can be numbered from the central one, spiraling out as shown in Figure D-1; and (2) only those caves with their cave numbers being prime (let's call such caves prime caves), which are circled in the figure, store scrolls. From the next attempt, you would be able to maximize the number of prime caves to explore.

<image>

Figure D-1: Numbering of the caves and the prime caves


Write a program, given the total number of the caves and the cave visited first, that finds the descending route containing the maximum number of prime caves.

Input

The input consists of multiple datasets. Each dataset has an integer m (1 ≤ m ≤ 106) and an integer n (1 ≤ n ≤ m) in one line, separated by a space. m represents the total number of caves. n represents the cave number of the cave from which you will start your exploration. The last dataset is followed by a line with two zeros.

Output

For each dataset, find the path that starts from the cave n and contains the largest number of prime caves, and output the number of the prime caves on the path and the last prime cave number on the path in one line, separated by a space. The cave n, explored first, is included in the caves on the path. If there is more than one such path, output for the path in which the last of the prime caves explored has the largest number among such paths. When there is no such path that explores prime caves, output "`0 0`" (without quotation marks).

Sample Input


49 22
46 37
42 23
945 561
1081 681
1056 452
1042 862
973 677
1000000 1000000
0 0


Output for the Sample Input


0 0
6 43
1 23
20 829
18 947
10 947
13 947
23 947
534 993541






Example

Input

49 22
46 37
42 23
945 561
1081 681
1056 452
1042 862
973 677
1000000 1000000
0 0


Output

0 0
6 43
1 23
20 829
18 947
10 947
13 947
23 947
534 993541

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that replaces 'two', 'too' and 'to' with the number '2'. Even if the sound is found mid word (like in octopus) or not in lowercase grandma still thinks that should be replaced with a 2. Bless her.

```text
'I love to text' becomes 'I love 2 text'
'see you tomorrow' becomes 'see you 2morrow'
'look at that octopus' becomes 'look at that oc2pus'
```

Note that 'too' should become '2', not '2o'

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