vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Gwen loves most numbers. In fact, she loves every number that is not a multiple of $n$ (she really hates the number $n$). For her friends’ birthdays this year, Gwen has decided to draw each of them a sequence of $n-1$ flowers. Each of the flowers will contain between $1$ and $n-1$ flower petals (inclusive). Because of her hatred of multiples of $n$, the total number of petals in any non-empty contiguous subsequence of flowers cannot be a multiple of $n$. For example, if $n = 5$, then the top two paintings are valid, while the bottom painting is not valid since the second, third and fourth flowers have a total of $10$ petals. (The top two images are Sample Input $3$ and $4$.)

Gwen wants her paintings to be unique, so no two paintings will have the same sequence of flowers. To keep track of this, Gwen recorded each painting as a sequence of $n-1$ numbers specifying the number of petals in each flower from left to right. She has written down all valid sequences of length $n-1$ in lexicographical order. A sequence $a_1,a_2,\dots , a_{n-1}$ is lexicographically smaller than $b_1, b_2, \dots , b_{n-1}$ if there exists an index $k$ such that $a_ i = b_ i$ for $i < k$ and $a_ k < b_ k$.

What is the $k$th sequence on Gwen’s list?

-----Input-----
The input consists of a single line containing two integers $n$ ($2 \leq n \leq 1000$), which is Gwen’s hated number, and $k$ ($1 \leq k \leq 10^{18}$), which is the index of the valid sequence in question if all valid sequences were ordered lexicographically. It is guaranteed that there exist at least $k$ valid sequences for this value of $n$.

-----Output-----
Display the $k$th sequence on Gwen’s list.

-----Examples-----
Sample Input 1:
4 3
Sample Output 1:
2 1 2

Sample Input 2:
2 1
Sample Output 2:
1

Sample Input 3:
5 22
Sample Output 3:
4 3 4 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is all about adding numbers.

You will create a function named add. It will return the sum of all the arguments. Sounds easy, doesn't it?

Well Here's the Twist. The inputs will gradually decrease with their index as parameter to the function.

```python
  add(3,4,6) #returns (3/1)+(4/2)+(6/3)=7
```

Remember the function will return 0 if no arguments are passed and it must round the result if sum is a float.

Example
```python
  add() #=> 0
  add(1,2,3) #=> 3
  add(1,4,-6,20) #=> 6
```

Check my another kata here!! http://www.codewars.com/kata/555b73a81a6285b6ce000047

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three bags. Each bag contains a non-empty multiset of numbers. You can perform a number of operations on these bags. In one operation, you can choose any two non-empty bags, and choose one number from each of the bags. Let's say that you choose number $a$ from the first bag and number $b$ from the second bag. Then, you remove $b$ from the second bag and replace $a$ with $a-b$ in the first bag. Note that if there are multiple occurrences of these numbers, then you shall only remove/replace exactly one occurrence.

You have to perform these operations in such a way that you have exactly one number remaining in exactly one of the bags (the other two bags being empty). It can be shown that you can always apply these operations to receive such a configuration in the end. Among all these configurations, find the one which has the maximum number left in the end.


-----Input-----

The first line of the input contains three space-separated integers $n_1$, $n_2$ and $n_3$ ($1 \le n_1, n_2, n_3 \le 3\cdot10^5$, $1 \le n_1+n_2+n_3 \le 3\cdot10^5$) — the number of numbers in the three bags.

The $i$-th of the next three lines contain $n_i$ space-separated integers $a_{{i,1}}$, $a_{{i,2}}$, ..., $a_{{i,{{n_i}}}}$ ($1 \le a_{{i,j}} \le 10^9$) — the numbers in the $i$-th bag.


-----Output-----

Print a single integer — the maximum number which you can achieve in the end.


-----Examples-----

Input
2 4 1
1 2
6 3 4 5
5
Output
20
Input
3 2 2
7 5 4
2 9
7 1
Output
29


-----Note-----

In the first example input, let us perform the following operations:

$[1, 2], [6, 3, 4, 5], [5]$

$[-5, 2], [3, 4, 5], [5]$ (Applying an operation to $(1, 6)$)

$[-10, 2], [3, 4], [5]$ (Applying an operation to $(-5, 5)$)

$[2], [3, 4], [15]$ (Applying an operation to $(5, -10)$)

$[-1], [4], [15]$ (Applying an operation to $(2, 3)$)

$[-5], [], [15]$ (Applying an operation to $(-1, 4)$)

$[], [], [20]$ (Applying an operation to $(15, -5)$)

You can verify that you cannot achieve a bigger number. Hence, the answer is $20$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Manhattan, roads run where the x or y coordinate is an integer. Both Sunuke-kun's house and Sumeke-kun's house are on the road, and the straight line distance (Euclidean distance) is just d. Find the maximum value that can be considered as the shortest distance when traveling along the road from Sunuke-kun's house to Sumek-kun's house.

Constraints

* 0 <d ≤ 10
* d is given up to exactly three decimal places

Input


d


Output

Print the answer on one line. If the absolute error or relative error is 10-9 or less, the answer is judged to be correct.

Examples

Input

1.000


Output

2.000000000000


Input

2.345


Output

3.316330803765

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sensation, sensation in the two-dimensional kingdom! The police have caught a highly dangerous outlaw, member of the notorious "Pihters" gang. The law department states that the outlaw was driving from the gang's headquarters in his car when he crashed into an ice cream stall. The stall, the car, and the headquarters each occupies exactly one point on the two-dimensional kingdom.

The outlaw's car was equipped with a GPS transmitter. The transmitter showed that the car made exactly *n* movements on its way from the headquarters to the stall. A movement can move the car from point (*x*,<=*y*) to one of these four points: to point (*x*<=-<=1,<=*y*) which we will mark by letter "L", to point (*x*<=+<=1,<=*y*) — "R", to point (*x*,<=*y*<=-<=1) — "D", to point (*x*,<=*y*<=+<=1) — "U".

The GPS transmitter is very inaccurate and it doesn't preserve the exact sequence of the car's movements. Instead, it keeps records of the car's possible movements. Each record is a string of one of these types: "UL", "UR", "DL", "DR" or "ULDR". Each such string means that the car made a single movement corresponding to one of the characters of the string. For example, string "UL" means that the car moved either "U", or "L".

You've received the journal with the outlaw's possible movements from the headquarters to the stall. The journal records are given in a chronological order. Given that the ice-cream stall is located at point (0,<=0), your task is to print the number of different points that can contain the gang headquarters (that is, the number of different possible locations of the car's origin).

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=2·105) — the number of the car's movements from the headquarters to the stall.

Each of the following *n* lines describes the car's possible movements. It is guaranteed that each possible movement is one of the following strings: "UL", "UR", "DL", "DR" or "ULDR". 

All movements are given in chronological order. 

Please do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin and cout stream or the %I64d specifier.

Output Specification:
Print a single integer — the number of different possible locations of the gang's headquarters.

Demo Input:
['3\nUR\nUL\nULDR\n', '2\nDR\nDL\n']

Demo Output:
['9\n', '4\n']

Note:
The figure below shows the nine possible positions of the gang headquarters from the first sample: 

For example, the following movements can get the car from point (1, 0) to point (0, 0):

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An agent called Cypher is decrypting a message, that contains a [composite number](https://en.wikipedia.org/wiki/Composite_number) n. All divisors of n, which are greater than 1, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases. Next t lines describe each test case.

In a single line of each test case description, there is a single composite number n (4 ≤ n ≤ 10^9) — the number from the message.

It's guaranteed that the total number of divisors of n for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case in the first line output the initial order of divisors, which are greater than 1, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.

Example

Input


3
6
4
30


Output


2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0

Note

In the first test case 6 has three divisors, which are greater than 1: 2, 3, 6. Regardless of the initial order, numbers 2 and 3 are adjacent, so it's needed to place their least common multiple between them. After that the circle becomes 2, 6, 3, 6, and every two adjacent numbers are not coprime.

In the second test case 4 has two divisors greater than 1: 2, 4, and they are not coprime, so any initial order is correct, and it's not needed to place any least common multiples.

In the third test case all divisors of 30 greater than 1 can be placed in some order so that there are no two adjacent numbers that are coprime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Saurabh and Pranav play the popular game of Hungry Birds on windows and android phones respectively.

The game goal is to destroy birds in the Hungry Birds Game. A certain number of points is given for destroying each bird depending on the bird type and the current factor value.

There are n types of Hungry Birds. The number of birds of type ai and bird cost ci is known for each bird type. A player gets ci.f points for destroying one bird of type i, where f is the current factor. The factor value can be an integer number from 1 to t + 1, inclusive. At the beginning of the game the factor value is equal to 1. The factor is set to i + 1 after destruction of pi (1 ≤ i ≤ t) birds, so the (pi + 1)-th bird to be destroyed is considered with factor equal to i+1.

Your task is to determine the maximum number of points Saurabh and Pranav can get after they destroy all birds. Take into account that they are so tough that they can destroy birds in any order chosen by them individually on their respective phones. 

Input :
The first line contains the only integer number n (1 ≤ n ≤ 100) — the number of bird types.

Each of the following n lines contains two integer numbers ai and ci (1 ≤ ai ≤ 10^9, 0 ≤ ci ≤ 1000), separated with space — the number of birds of the i-th type and the cost of one i-type bird, correspondingly.

The next line contains the only integer number t (1 ≤ t ≤ 100) — the number that describe the factor's changes.

The next line contains t integer numbers pi (1 ≤ p1 < p2 < ... < pt ≤ 10^12), separated with spaces. 

Output :
Print the only number — the maximum number of points they can get. 

SAMPLE INPUT
2
3 8
5 10
1
20

SAMPLE OUTPUT
74

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two integer sequences existed initially, one of them was strictly increasing, and another one — strictly decreasing.

Strictly increasing sequence is a sequence of integers $[x_1 < x_2 < \dots < x_k]$. And strictly decreasing sequence is a sequence of integers $[y_1 > y_2 > \dots > y_l]$. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

Elements of increasing sequence were inserted between elements of the decreasing one (and, possibly, before its first element and after its last element) without changing the order. For example, sequences $[1, 3, 4]$ and $[10, 4, 2]$ can produce the following resulting sequences: $[10, \textbf{1}, \textbf{3}, 4, 2, \textbf{4}]$, $[\textbf{1}, \textbf{3}, \textbf{4}, 10, 4, 2]$. The following sequence cannot be the result of these insertions: $[\textbf{1}, 10, \textbf{4}, 4, \textbf{3}, 2]$ because the order of elements in the increasing sequence was changed.

Let the obtained sequence be $a$. This sequence $a$ is given in the input. Your task is to find any two suitable initial sequences. One of them should be strictly increasing, and another one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO".


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line, print a sequence of $n$ integers $res_1, res_2, \dots, res_n$, where $res_i$ should be either $0$ or $1$ for each $i$ from $1$ to $n$. The $i$-th element of this sequence should be $0$ if the $i$-th element of $a$ belongs to the increasing sequence, and $1$ otherwise. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.


-----Examples-----
Input
9
5 1 3 6 8 2 9 0 10

Output
YES
1 0 0 0 0 1 0 1 0 

Input
5
1 2 4 0 2

Output
NO

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

The [Fibonacci](http://en.wikipedia.org/wiki/Fibonacci_number) sequence is traditionally used to explain tree recursion.  

```python
def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
```

This algorithm serves welll its educative purpose but it's [tremendously inefficient](http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2), not only because of recursion, but because we invoke the fibonacci function twice, and the right branch of recursion (i.e. `fibonacci(n-2)`) recalculates all the Fibonacci numbers already calculated by the left branch (i.e. `fibonacci(n-1)`).

This algorithm is so inefficient that the time to calculate any Fibonacci number over 50 is simply too much. You may go for a cup of coffee or go take a nap while you wait for the answer. But if you try it here in Code Wars you will most likely get a code timeout before any answers.

For this particular Kata we want to **implement the memoization solution**. This will be cool because it will let us *keep using the tree recursion* algorithm while still keeping it sufficiently optimized to get an answer very rapidly.

The trick of the memoized version is that we will keep a cache data structure (most likely an associative array) where we will store the Fibonacci numbers as we calculate them. When a Fibonacci number is calculated, we first look it up in the cache, if it's not there, we calculate it and put it in the cache, otherwise we returned the cached number.

Refactor the function into a recursive Fibonacci function that using  a memoized data structure avoids the deficiencies of tree recursion Can you make it so the memoization cache is private to this function?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that accepts two arguments: an array/list of integers and another integer (`n`). 

Determine the number of times where two integers in the array have a difference of `n`.

For example:
```
[1, 1, 5, 6, 9, 16, 27], n=4  -->  3  # (1,5), (1,5), (5,9)
[1, 1, 3, 3], n=2             -->  4  # (1,3), (1,3), (1,3), (1,3)
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Students went into a class to write a test and sat in some way. The teacher thought: "Probably they sat in this order to copy works of each other. I need to rearrange them in such a way that students that were neighbors are not neighbors in a new seating."

The class can be represented as a matrix with n rows and m columns with a student in each cell. Two students are neighbors if cells in which they sit have a common side.

Let's enumerate students from 1 to n·m in order of rows. So a student who initially sits in the cell in row i and column j has a number (i - 1)·m + j. You have to find a matrix with n rows and m columns in which all numbers from 1 to n·m appear exactly once and adjacent numbers in the original matrix are not adjacent in it, or determine that there is no such matrix.

Input

The only line contains two integers n and m (1 ≤ n, m ≤ 105; n·m ≤ 105) — the number of rows and the number of columns in the required matrix.

Output

If there is no such matrix, output "NO" (without quotes). 

Otherwise in the first line output "YES" (without quotes), and in the next n lines output m integers which form the required matrix.

Examples

Input

2 4


Output

YES
5 4 7 2 
3 6 1 8 


Input

2 1


Output

NO

Note

In the first test case the matrix initially looks like this:
    
    
      
    1 2 3 4  
    5 6 7 8  
    

It's easy to see that there are no two students that are adjacent in both matrices.

In the second test case there are only two possible seatings and in both of them students with numbers 1 and 2 are neighbors.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vova is again playing some computer game, now an RPG. In the game Vova's character received a quest: to slay the fearsome monster called Modcrab.

After two hours of playing the game Vova has tracked the monster and analyzed its tactics. The Modcrab has *h*2 health points and an attack power of *a*2. Knowing that, Vova has decided to buy a lot of strong healing potions and to prepare for battle.

Vova's character has *h*1 health points and an attack power of *a*1. Also he has a large supply of healing potions, each of which increases his current amount of health points by *c*1 when Vova drinks a potion. All potions are identical to each other. It is guaranteed that *c*1<=&gt;<=*a*2.

The battle consists of multiple phases. In the beginning of each phase, Vova can either attack the monster (thus reducing its health by *a*1) or drink a healing potion (it increases Vova's health by *c*1; Vova's health can exceed *h*1). Then, if the battle is not over yet, the Modcrab attacks Vova, reducing his health by *a*2. The battle ends when Vova's (or Modcrab's) health drops to 0 or lower. It is possible that the battle ends in a middle of a phase after Vova's attack.

Of course, Vova wants to win the fight. But also he wants to do it as fast as possible. So he wants to make up a strategy that will allow him to win the fight after the minimum possible number of phases.

Help Vova to make up a strategy! You may assume that Vova never runs out of healing potions, and that he can always win.

Input Specification:
The first line contains three integers *h*1, *a*1, *c*1 (1<=≤<=*h*1,<=*a*1<=≤<=100, 2<=≤<=*c*1<=≤<=100) — Vova's health, Vova's attack power and the healing power of a potion.

The second line contains two integers *h*2, *a*2 (1<=≤<=*h*2<=≤<=100, 1<=≤<=*a*2<=&lt;<=*c*1) — the Modcrab's health and his attack power.

Output Specification:
In the first line print one integer *n* denoting the minimum number of phases required to win the battle.

Then print *n* lines. *i*-th line must be equal to HEAL if Vova drinks a potion in *i*-th phase, or STRIKE if he attacks the Modcrab.

The strategy must be valid: Vova's character must not be defeated before slaying the Modcrab, and the monster's health must be 0 or lower after Vova's last action.

If there are multiple optimal solutions, print any of them.

Demo Input:
['10 6 100\n17 5\n', '11 6 100\n12 5\n']

Demo Output:
['4\nSTRIKE\nHEAL\nSTRIKE\nSTRIKE\n', '2\nSTRIKE\nSTRIKE\n']

Note:
In the first example Vova's character must heal before or after his first attack. Otherwise his health will drop to zero in 2 phases while he needs 3 strikes to win.

In the second example no healing needed, two strikes are enough to get monster to zero health and win with 6 health left.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given positive integer n denote its k-rounding as the minimum positive integer x, such that x ends with k or more zeros in base 10 and is divisible by n.

For example, 4-rounding of 375 is 375·80 = 30000. 30000 is the minimum integer such that it ends with 4 or more zeros and is divisible by 375.

Write a program that will perform the k-rounding of n.


-----Input-----

The only line contains two integers n and k (1 ≤ n ≤ 10^9, 0 ≤ k ≤ 8).


-----Output-----

Print the k-rounding of n.


-----Examples-----
Input
375 4

Output
30000

Input
10000 1

Output
10000

Input
38101 0

Output
38101

Input
123456789 8

Output
12345678900000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of N elements and Q queries. Each query containing an integer X. For each query print the X^th smallest number of the input array. 

Note : Don't use any predefined function. Try to make your own code.
Constraints
1 ≤ N ≤ 10^5
1 ≤ Value of element of array ≤ 10^18
1 ≤ Q ≤ 10^6
1 ≤ X ≤ N

Input
First line contains value N. Next line contains N integers separated by a single space. Third line contains value Q. Next line contains Q integers separated by a space.

SAMPLE INPUT
8
5 6 9 7 4 1 5 1
5
8 5 4 1 3

SAMPLE OUTPUT
9
5
5
1
4

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