vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array $\mbox{A}$ of size $N$. You are asked to answer $\mbox{Q}$ queries.  

Each query contains a number $\mbox{M}$.  

For each distinct permutation of the array $\mbox{A}$, you need to print the sum of the values returned by the find function.

As the sum can be too large, output it modulo $\mbox{P}$, which is a prime and given in input.  

find(int permutation_A[], int M)
{
    x = Length(permutation_A)
    sum = 0
    for(i = 0; i < x; i++) {
        if (permutation_A[i] <= M)
            sum = sum + permutation_A[i]
        else
            break
    }
    return sum
}

Input Format 

The first line of input contains $\mbox{P}$. 

The second line of input contains $N$. The next line contains $N$ numbers $A[0]\ldots A[N-1]$ separated by single spaces. 

The next line contains $\mbox{Q}$, the number of queries to follow. Each subsequent line contains one positive integer $\mbox{M}$.  

Output Format 

For each query, output as asked above.  

Constraints 

$1000000\leq P\leq2000003$ 

$1\leq N\leq10^5$ 

$1\leq Q\leq10^5$ 

$1\leq A[i],M\leq10^9$

Sample Input

2000003
5
4 2 3 1 4
2
1
2

Sample Output

12
45

Explanation

Query 1: 

Consider all permutations. if the first number is greater than 1, then the loop will break in the beginning itself. There are a total of 60 distinct permutations out of which 48 will give 0. The remaining 12 will fetch 1 each from the function. Thus the answer is 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vova has won $n$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of trophies.

The second line contains $n$ characters, each of them is either G or S. If the $i$-th character is G, then the $i$-th trophy is a golden one, otherwise it's a silver trophy. 


-----Output-----

Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.


-----Examples-----
Input
10
GGGSGGGSGG

Output
7

Input
4
GGGG

Output
4

Input
3
SSS

Output
0



-----Note-----

In the first example Vova has to swap trophies with indices $4$ and $10$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $7$. 

In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $4$. 

In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the year of 3000 travelling around parallel realities became a routine thing. However one has to take into consideration that travelling like that is highly dangerous as you never know beforehand where you're gonna get...

Little Vasya, for instance, found himself in a gaming reality and now he has to successfully complete all levels of a very weird game to get back. The gaming reality is a three-dimensional space where n points are given. The game has m levels and at the beginning of the i-th level the player is positioned at some plane Qi that passes through the origin. On each level Vasya has to use special robots to construct and activate n powerful energy spheres of the equal radius with centers at the given points. The player chooses the radius of the spheres himself. The player has to spend R units of money to construct spheres whose radius equals R (consequently, one can construct spheres whose radius equals zero for free). Besides, once for each level a player can choose any point in space and release a laser ray from there, perpendicular to plane Qi (this action costs nothing). The ray can either be directed towards the plane or from the plane. The spheres that share at least one point with the ray will be immediately activated. The level is considered completed if the player has managed to activate all spheres. Note that the centers of the spheres are the same for all m levels but the spheres do not remain: the player should construct them anew on each new level.

Help Vasya find out what minimum sum of money will be enough to complete each level.

Input

The first line contains two integers n and m (1 ≤ n ≤ 900, 1 ≤ m ≤ 100) — the number of energetic spheres and the number of levels in the game correspondingly. 

Each of the following n lines contains three integers xi, yi, zi (0 ≤ xi, yi, zi ≤ 104) — the coordinates of the center of the i-th sphere. Assume that these points do not change their positions throughout the game.

Then follow m lines, each containing three integers ai, bi, ci (0 ≤ ai, bi, ci ≤ 100, ai2 + bi2 + ci2 > 0). These numbers are the coefficients in the equation of plane Qi (aix + biy + ciz = 0), where the player is positioned at the beginning of the i-th level.

Output

Print m numbers, one per line: the i-th line should contain the minimum sum of money needed to complete the i-th level. The absolute or relative error should not exceed 10 - 6.

Examples

Input

4 1
0 0 0
0 1 0
1 0 0
1 1 0
0 0 1


Output

0.7071067812


Input

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


Output

1.6329931619
1.6366341768
1.5411035007


Input

2 1
0 20 0
0 0 0
0 10 0


Output

0.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, find two permutations:  Permutation p of numbers from 1 to N such that p_{i} ≠ i and p_{i} & i = 0 for all i = 1, 2, ..., N.  Permutation q of numbers from 1 to N such that q_{i} ≠ i and q_{i} & i ≠ 0 for all i = 1, 2, ..., N. 

& is the bitwise AND operation.


-----Input-----

The input consists of one line containing a single integer N (1 ≤ N ≤ 10^5).


-----Output-----

For each subtask, if the required permutation doesn't exist, output a single line containing the word "NO"; otherwise output the word "YES" in the first line and N elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them.


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

Output
NO
NO

Input
6

Output
YES
6 5 4 3 2 1 
YES
3 6 2 5 1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a program that outputs the surface area S of a square cone with a height of h, with a square with one side x as the base. However, assume that the line segment connecting the apex and the center of the base is orthogonal to the base. Also, x and h are positive integers less than or equal to 100.

Input

Given multiple datasets. Each dataset is given in the following format:


x
h


When both x and h are 0, it indicates the end of input.



Output

Output S (real number) on one line for each data set. The output may contain an error of 0.00001 or less.

Example

Input

6
4
7
9
0
0


Output

96.000000
184.192455

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to calculate the sum (indicated by S) of all the k-balanced integers between [L, R]. An integer is called k-balanced when either of #1 or #2 below holds true.

The length of the integer <= k     
Sum of the first k digits (with no leading zeros) is equal to the sum of the last k digits.    

Input format 

L R k

Output format 

S % 1000000007

Constraints 

0 < L <= R < 10^18 

0 < k <= 18

Sample Input 

9 23 1

Sample Output 

42

Explanation 

9, 11 and 22 are the only 3 integers between 9 and 23 ( both included ) that are k-balanced. Hence, the answer is 9+11+22=42

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a secret array. You don't know this array and you have to restore it. However, you know some facts about this array:

  * The array consists of n distinct positive (greater than 0) integers. 
  * The array contains two elements x and y (these elements are known for you) such that x < y. 
  * If you sort the array in increasing order (such that a_1 < a_2 < … < a_n), differences between all adjacent (consecutive) elements are equal (i.e. a_2 - a_1 = a_3 - a_2 = … = a_n - a_{n-1}). 



It can be proven that such an array always exists under the constraints given below.

Among all possible arrays that satisfy the given conditions, we ask you to restore one which has the minimum possible maximum element. In other words, you have to minimize max(a_1, a_2, ..., a_n).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The only line of the test case contains three integers n, x and y (2 ≤ n ≤ 50; 1 ≤ x < y ≤ 50) — the length of the array and two elements that are present in the array, respectively.

Output

For each test case, print the answer: n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of the required array. If there are several answers, you can print any (it also means that the order of elements doesn't matter).

It can be proven that such an array always exists under the given constraints.

Example

Input


5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22


Output


1 49 
20 40 30 50 10
26 32 20 38 44 50 
8 23 18 13 3 
1 10 13 4 19 22 25 16 7 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Math, an improper fraction is a fraction where the numerator (the top number) is greater than or equal to the denominator (the bottom number) For example: ```5/3``` (five third).

A mixed numeral is a whole number and a fraction combined into one "mixed" number. For example: ```1 1/2``` (one and a half) is a mixed numeral.

## Task

Write a function `convertToMixedNumeral` to convert the improper fraction into a mixed numeral.

The input will be given as a ```string``` (e.g. ```'4/3'```).

The output should be a ```string```, with a space in between the whole number and the fraction (e.g. ```'1 1/3'```).  You do not need to reduce the result to its simplest form.

For the purpose of this exercise, there will be no ```0```, ```empty string``` or ```null``` input value. However, the input can be:

- a negative fraction
- a fraction that does not require conversion
- a fraction that can be converted into a whole number

## Example

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions are constraints on $n$ and $k$.

You are messaging in one of the popular social networks via your smartphone. Your smartphone can show at most $k$ most recent conversations with your friends. Initially, the screen is empty (i.e. the number of displayed conversations equals $0$).

Each conversation is between you and some of your friends. There is at most one conversation with any of your friends. So each conversation is uniquely defined by your friend.

You (suddenly!) have the ability to see the future. You know that during the day you will receive $n$ messages, the $i$-th message will be received from the friend with ID $id_i$ ($1 \le id_i \le 10^9$).

If you receive a message from $id_i$ in the conversation which is currently displayed on the smartphone then nothing happens: the conversations of the screen do not change and do not change their order, you read the message and continue waiting for new messages.

Otherwise (i.e. if there is no conversation with $id_i$ on the screen):  Firstly, if the number of conversations displayed on the screen is $k$, the last conversation (which has the position $k$) is removed from the screen.  Now the number of conversations on the screen is guaranteed to be less than $k$ and the conversation with the friend $id_i$ is not displayed on the screen.  The conversation with the friend $id_i$ appears on the first (the topmost) position on the screen and all the other displayed conversations are shifted one position down. 

Your task is to find the list of conversations (in the order they are displayed on the screen) after processing all $n$ messages.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 200)$ — the number of messages and the number of conversations your smartphone can show.

The second line of the input contains $n$ integers $id_1, id_2, \dots, id_n$ ($1 \le id_i \le 10^9$), where $id_i$ is the ID of the friend which sends you the $i$-th message.


-----Output-----

In the first line of the output print one integer $m$ ($1 \le m \le min(n, k)$) — the number of conversations shown after receiving all $n$ messages.

In the second line print $m$ integers $ids_1, ids_2, \dots, ids_m$, where $ids_i$ should be equal to the ID of the friend corresponding to the conversation displayed on the position $i$ after receiving all $n$ messages.


-----Examples-----
Input
7 2
1 2 3 2 1 3 2

Output
2
2 1 

Input
10 4
2 3 3 1 1 2 1 2 3 3

Output
3
1 3 2 



-----Note-----

In the first example the list of conversations will change in the following way (in order from the first to last message):  $[]$;  $[1]$;  $[2, 1]$;  $[3, 2]$;  $[3, 2]$;  $[1, 3]$;  $[1, 3]$;  $[2, 1]$. 

In the second example the list of conversations will change in the following way:  $[]$;  $[2]$;  $[3, 2]$;  $[3, 2]$;  $[1, 3, 2]$;  and then the list will not change till the end.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now, a ninja is planning to sneak into the castle tower from outside the castle. This ninja can easily run on the ground and swim in the moat, but he is not very good at climbing up from the moat, so he wants to enter the moat as few times as possible.

Create a program that takes a sketch of the castle as input and outputs the minimum number of times you have to crawl up from the moat from outside the castle to the castle tower. The sketch of the castle is given as a two-dimensional grid. The symbols drawn on the sketch show the positions of "&" indicating the position of the castle tower and "#" indicating the position of the moat, and "." (Half-width period) at other points. In addition, it is assumed that there is only one castle tower in the castle, and the ninja moves one square at a time in the north, south, east, and west directions when running or swimming, and does not move diagonally.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


n m
c1,1 c1,2 ... c1, n
c2,1c2,2 ... c2, n
::
cm, 1cm, 2 ... cm, n


The first line gives the east-west width n and the north-south width m (1 ≤ n, m ≤ 100) of the sketch. The following m lines give the information on the i-th line of the sketch. Each piece of information is a character string of length n consisting of the symbols "&", "#", and ".".

The number of datasets does not exceed 50.

Output

Outputs the minimum number of times (integer) that must be climbed from the moat for each dataset on one line.

Examples

Input

5 5
.###.
#...#
#.&.#
#...#
.###.
18 15
..####....####....
####..####....####
#...............##
.#.############.##
#..#..........#.##
.#.#.########.#.##
#..#.#......#.#.##
.#.#....&...#.#.##
#..#........#.#.##
.#.#.########.#.##
#..#..........#.##
.#.############.##
#...............##
.#################
##################
9 10
#########
........#
#######.#
#.....#.#
#.###.#.#
#.#&#.#.#
#.#...#.#
#.#####.#
#.......#
#########
9 3
###...###
#.#.&.#.#
###...###
0 0


Output

1
2
0
0


Input

5 5
.###.
...#
.&.#
...#
.###.
18 15
..####....####....
..####....####
...............##
.#.############.##
..#..........#.##
.#.#.########.#.##
..#.#......#.#.##
.#.#....&...#.#.##
..#........#.#.##
.#.#.########.#.##
..#..........#.##
.#.############.##
...............##
.#################

9 10

........#
.#
.....#.#
.###.#.#
.#&#.#.#
.#...#.#
.#####.#
.......#

9 3
...###
.#.&.#.#
...###
0 0
</pre>


Output

1
2
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. Let A be an N \times N grid such that A_{i, j} = i + N\cdot(j-1) for 1 ≤ i, j ≤ N. For example, if N = 4 the grid looks like:

You start at the top left corner of the grid, i.e, cell (1, 1). You would like to reach the bottom-right corner, cell (N, N). To do so, whenever you are at cell (i, j), you can move to either cell (i+1, j) or cell (i, j+1) provided that the corresponding cell lies within the grid (more informally, you can make one step down or one step right).

The *score* of a path you take to reach (N, N) is the sum of all the numbers on that path.

You are given an integer K that is either 0 or 1. Is there a path reaching (N, N) such that the parity of its score is K?

Recall that the parity of an integer is the (non-negative) remainder obtained when dividing it by 2. For example, the parity of 246 is 0 and the parity of 11 is 1. In other words, an even number has parity 0 and an odd number has parity 1.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers N and K.

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

- For each test case, output the answer on a new line — YES if such a path exists, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the strings YES, yEs, and yes will all be treated as identical.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$
$K \in \{0, 1\}$

----- Sample Input 1 ------ 
4
1 0
2 0
2 1
3 1

----- Sample Output 1 ------ 
No
Yes
Yes
Yes

----- explanation 1 ------ 
Test case $1$: There is only one possible path, which starts and ends at the same cell. The score of this path is $1$, which is odd. An even score is impossible.

Test case $2$: The following path has an even score for $N = 2$:

Test case $3$: The following path has an odd score for $N = 2$:

Test case $4$: The following path has an odd score for $N = 3$:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array arr of distinct integers and an integer k.
A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.
Return the integer which will win the game.
It is guaranteed that there will be a winner of the game.
 
Example 1:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:
Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:
Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:
Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

 
Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Frank N. Stein is a very conservative high-school teacher. He wants to take some of his students on an excursion, but he is afraid that some of them might become couples. While you can never exclude this possibility, he has made some rules that he thinks indicates a low probability two persons will become a couple:
 - Their height differs by more than $40$ cm.
 - They are of the same sex.
 - Their preferred music style is different.
 - Their favourite sport is the same (they are likely to be fans of different teams and that would result in fighting).

So, for any two persons that he brings on the excursion, they must satisfy at least one of the requirements above. Help him find the maximum number of persons he can take, given their vital information.

-----Input-----
The first line of input consists of an integer $1 \le N \le 1000$ giving the number of pupils. Next there will be one line for each pupil consisting of four space-separated data items:
 - an integer $h$ ($0 \le h \le 3000$) giving the height in cm;
 - a character ‘F’ for female or ‘M’ for male;
 - a string describing the preferred music style;
 - a string with the name of the favourite sport.

The strings in the input are of length at at least $1$ and at most $20$ characters, and contain only upper and lower case letters, digits, and dashes.

-----Output-----
For each test case in the input there should be one line with an integer giving the maximum number of eligible pupils.

-----Examples-----
Sample Input:
4
35 M classicism programming
0 M baroque skiing
43 M baroque chess
30 F baroque soccer
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $a$ and $b$. You may perform any number of operations on them (possibly zero).

During each operation you should choose any positive integer $x$ and set $a := a - x$, $b := b - 2x$ or $a := a - 2x$, $b := b - x$. Note that you may choose different values of $x$ in different operations.

Is it possible to make $a$ and $b$ equal to $0$ simultaneously?

Your program should answer $t$ independent test cases.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Then the test cases follow, each test case is represented by one line containing two integers $a$ and $b$ for this test case ($0 \le a, b \le 10^9$).


-----Output-----

For each test case print the answer to it — YES if it is possible to make $a$ and $b$ equal to $0$ simultaneously, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
3
6 9
1 1
1 2

Output
YES
NO
YES



-----Note-----

In the first test case of the example two operations can be used to make both $a$ and $b$ equal to zero:  choose $x = 4$ and set $a := a - x$, $b := b - 2x$. Then $a = 6 - 4 = 2$, $b = 9 - 8 = 1$;  choose $x = 1$ and set $a := a - 2x$, $b := b - x$. Then $a = 2 - 2 = 0$, $b = 1 - 1 = 0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have two permutations P and Q of size N (that is, P and Q are both rearrangements of (1,~2,~...,~N)).
There are N! possible permutations of size N. Among them, let P and Q be the a-th and b-th lexicographically smallest permutations, respectively. Find |a - b|.

-----Notes-----
For two sequences X and Y, X is said to be lexicographically smaller than Y if and only if there exists an integer k such that X_i = Y_i~(1 \leq i < k) and X_k < Y_k.

-----Constraints-----
 - 2 \leq N \leq 8
 - P and Q are permutations of size N.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 P_2 ... P_N
Q_1 Q_2 ... Q_N

-----Output-----
Print |a - b|.

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

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

There are 6 permutations of size 3: (1,~2,~3), (1,~3,~2), (2,~1,~3), (2,~3,~1), (3,~1,~2), and (3,~2,~1). Among them, (1,~3,~2) and (3,~1,~2) come 2-nd and 5-th in lexicographical order, so the answer is |2 - 5| = 3.

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