vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given simple (without self-intersections) n-gon. It is not necessary convex. Also you are given m lines. For each line find the length of common part of the line and the n-gon.

The boundary of n-gon belongs to polygon. It is possible that n-gon contains 180-degree angles.


-----Input-----

The first line contains integers n and m (3 ≤ n ≤ 1000;1 ≤ m ≤ 100). The following n lines contain coordinates of polygon vertices (in clockwise or counterclockwise direction). All vertices are distinct.

The following m lines contain line descriptions. Each of them contains two distict points of a line by their coordinates.

All given in the input coordinates are real numbers, given with at most two digits after decimal point. They do not exceed 10^5 by absolute values.


-----Output-----

Print m lines, the i-th line should contain the length of common part of the given n-gon and the i-th line. The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


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

Output
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer n and an integer start.
Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.
Return the bitwise XOR of all elements of nums.
 
Example 1:
Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:
Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.
Example 3:
Input: n = 1, start = 7
Output: 7

Example 4:
Input: n = 10, start = 5
Output: 2

 
Constraints:

1 <= n <= 1000
0 <= start <= 1000
n == nums.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary number (of $N$ bits) $X$. Find the highest power of 2 that divides this number.
Note: If the binary number is "100" then the highest power of 2 that divides it is 2 (as $2^{2}$ = 4)

------ Input: ------ 

The first line contains N the number of bits in the number
The next line contains a binary number of N bits

------ Output: ------ 

The first and only line contains the max power of 2 that divides the given number

------ Constraints: ------ 

$ $1 ≤ N ≤10^{5}$$
$ $1≤ X$$

----- Sample Input 1 ------ 
5
10100
----- Sample Output 1 ------ 
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The currency system in the Kingdom of Yoax-Musty is strange and fairly inefficient. Like other countries, the kingdom has its own currencty unit denoted by K $ (kingdom dollar). However, the Ministry of Finance issues bills for every value between 1 K $ and (231 - 1) K $ worth.

On the other hand, this system often enables people to make many different values just with a small number of bills. For example, if you have four bills of 1 K $, 2 K $, 4 K $, and 8 K $ worth respectively, you can make any values from 1 K #36; to 15 K $.

In this problem, you are requested to write a program that finds the minimum value that cannot be made with a given set (multiset in a mathematical sense) of bills. For the case with the four bills (1 K $, 2 K $, 4 K $, and 8 K $), since you can make any values up to 15 K $, your program should report 16 K $.



Input

The input consists of two lines. The first line contains an integer N (1 ≤ N ≤ 10000), the number of bills. The second line contains N integers, each of which represents the value of a bill in K $. There may be multiple bills of the same value.

Output

Print the minimum value unable to be made on a line. The value should be given in K $ and without any currency sign or name.

Example

Input




Output

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid:

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string *s* which consists of 27 upper-case English letters. Each English letter occurs at least once in *s*. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string *s*. If there’s no solution, print "Impossible" (without the quotes).

Input Specification:
The only line of the input contains the string *s*, consisting of 27 upper-case English letters. Each English letter occurs at least once in *s*.

Output Specification:
Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".

Demo Input:
['ABCDEFGHIJKLMNOPQRSGTUVWXYZ\n', 'BUVTYZFQSNRIWOXXGJLKACPEMDH\n']

Demo Output:
['YXWVUTGHIJKLM\nZABCDEFSRQPON\n', 'Impossible\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ms. Hall wants to teach her class about common factors. She arranges her students in a circle and assigns each student an integer in the range $[2,10^9]$. She also provides the students with crepe paper streamers. The students are to stretch these streamers between pairs of students, and pull them tight. But, there are some rules.
 - Two students can stretch a streamer between them if and only if their assigned integers share a factor other than $1$.
 - There is exactly one path, going from streamer to streamer, between any two students in the circle.
 - No streamers may cross.
 - Any given student may hold an end of arbitrarily many streamers.

Suppose Ms. Hall has four students, and she gives them the numbers $2$, $3$, $30$ and $45$. In this arrangement, there is one way to stretch the streamers:

In this arrangement, there are three ways to stretch the streamers:  

In how many ways can the students hold the streamers subject to Ms. Hall’s rules? Two ways are different if and only if there is a streamer between two given students one way, but none between those two students the other way.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($2 \le n \le 300$), which is the number of Ms. Hall’s students.

Each of the next $n$ lines will hold an integer $x$ ($2 \le x \le 10^9$). These are the numbers held by the students, in order. Remember, the students are standing in a circle, so the last student is adjacent to the first student.

-----Output-----
Output a single integer, which is the number of ways Ms. Hall’s students can satisfy her rules. Since this number may be very large, output it modulo $10^9+7$.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are participating in a contest which has $11$ problems (numbered $1$ through $11$). The first eight problems (i.e. problems $1, 2, \ldots, 8$) are scorable, while the last three problems ($9$, $10$ and $11$) are non-scorable ― this means that any submissions you make on any of these problems do not affect your total score.
Your total score is the sum of your best scores for all scorable problems. That is, for each scorable problem, you look at the scores of all submissions you made on that problem and take the maximum of these scores (or $0$ if you didn't make any submissions on that problem); the total score is the sum of the maximum scores you took.
You know the results of all submissions you made. Calculate your total score.

-----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 integer $N$ denoting the number of submissions you made.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains two space-separated integers $p_i$ and $s_i$, denoting that your $i$-th submission was on problem $p_i$ and it received a score $s_i$.

-----Output-----
For each test case, print a single line containing one integer ― your total score.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 1,000$
- $1 \le p_i \le 11$ for each valid $i$
- $0 \le s_i \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (15 points): all submissions are on the same problem, i.e. $p_1 = p_2 = \ldots = p_N$
Subtask #2 (15 points): there is at most one submission made on each problem, i.e. $p_i \neq p_j$ for each valid $i, j$ ($i \neq j$)
Subtask #3 (70 points): original constraints

-----Example Input-----
2
5
2 45
9 100
8 0
2 15
8 90
1
11 1

-----Example Output-----
135
0

-----Explanation-----
Example case 1: The scorable problems with at least one submission are problems $2$ and $8$. For problem $2$, there are two submissions and the maximum score among them is $45$. For problem $8$, there are also two submissions and the maximum score is $90$. Hence, the total score is $45 + 90 = 135$.
Example case 2: No scorable problem is attempted, so the total score is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Given two integers n and k, construct a permutation a of numbers from 1 to n which has exactly k peaks. An index i of an array a of size n is said to be a peak if 1 < i < n and a_i \gt a_{i-1} and a_i \gt a_{i+1}. If such permutation is not possible, then print -1.

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases.

Then t lines follow, each containing two space-separated integers n (1 ≤ n ≤ 100) and k (0 ≤ k ≤ n) — the length of an array and the required number of peaks.

Output

Output t lines. For each test case, if there is no permutation with given length and number of peaks, then print -1. Otherwise print a line containing n space-separated integers which forms a permutation of numbers from 1 to n and contains exactly k peaks. 

If there are multiple answers, print any.

Example

Input


5
1 0
5 2
6 6
2 1
6 1


Output


1 
2 4 1 5 3 
-1
-1
1 3 6 5 4 2

Note

In the second test case of the example, we have array a = [2,4,1,5,3]. Here, indices i=2 and i=4 are the peaks of the array. This is because (a_{2} \gt a_{1} , a_{2} \gt a_{3}) and (a_{4} \gt a_{3}, a_{4} \gt a_{5}). 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

Output

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

2
100 30
40 10


Output

942477.796077000


Input

4
1 1
9 7
1 4
10 7


Output

3983.539484752

Note

In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings $s$ and $t$. In a single move, you can choose any of two strings and delete the first (that is, the leftmost) character. After a move, the length of the string decreases by $1$. You can't choose a string if it is empty.

For example:  by applying a move to the string "where", the result is the string "here",  by applying a move to the string "a", the result is an empty string "". 

You are required to make two given strings equal using the fewest number of moves. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the initial strings.

Write a program that finds the minimum number of moves to make two given strings $s$ and $t$ equal.


-----Input-----

The first line of the input contains $s$. In the second line of the input contains $t$. Both strings consist only of lowercase Latin letters. The number of letters in each string is between 1 and $2\cdot10^5$, inclusive.


-----Output-----

Output the fewest number of moves required. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the given strings.


-----Examples-----
Input
test
west

Output
2

Input
codeforces
yes

Output
9

Input
test
yes

Output
7

Input
b
ab

Output
1



-----Note-----

In the first example, you should apply the move once to the first string and apply the move once to the second string. As a result, both strings will be equal to "est".

In the second example, the move should be applied to the string "codeforces" $8$ times. As a result, the string becomes "codeforces" $\to$ "es". The move should be applied to the string "yes" once. The result is the same string "yes" $\to$ "es".

In the third example, you can make the strings equal only by completely deleting them. That is, in the end, both strings will be empty.

In the fourth example, the first character of the second string should be deleted.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A non-empty string *s* is called binary, if it consists only of characters "0" and "1". Let's number the characters of binary string *s* from 1 to the string's length and let's denote the *i*-th character in string *s* as *s**i*.

Binary string *s* with length *n* is periodical, if there is an integer 1<=≤<=*k*<=&lt;<=*n* such that: 
 -  *k* is a divisor of number *n* -  for all 1<=≤<=*i*<=≤<=*n*<=-<=*k*, the following condition fulfills: *s**i*<==<=*s**i*<=+<=*k* 
For example, binary strings "101010" and "11" are periodical and "10" and "10010" are not.

A positive integer *x* is periodical, if its binary representation (without leading zeroes) is a periodic string.

Your task is to calculate, how many periodic numbers are in the interval from *l* to *r* (both ends are included).

Input Specification:
The single input line contains two integers *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=1018). The numbers are separated by a space.

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

Output Specification:
Print a single integer, showing how many periodic numbers are in the interval from *l* to *r* (both ends are included).

Demo Input:
['1 10\n', '25 38\n']

Demo Output:
['3\n', '2\n']

Note:
In the first sample periodic numbers are 3, 7 and 10.

In the second sample periodic numbers are 31 and 36.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a series of numbers  3,10,21,36 …., and series starting from N = 1, find the pattern and output the N'th value of the above series.
Example 1:
Input:
N = 1
Output:
3
Explanation:
3 is the first term of the series.
Example 2:
Input:
N = 2
Output:
10
Explanation:
10 is the second term of the series.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function differenceSeries() which takes an integer N as input parameter and returns the N'th term of the series.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock considers a string to be valid if all characters of the string appear the same number of times.  It is also valid if he can remove just $1$ character at $1$ index in the string, and the remaining characters will occur the same number of times.  Given a string $s$, determine if it is valid.  If so, return YES, otherwise return NO.

Example 

$s=abc$

This is a valid string because frequencies are $\{a:1,b:1,c:1\}$.  

$s=abcc$  

This is a valid string because we can remove one $c$ and have $1$ of each character in the remaining string.  

$s=abccc$  

This string is not valid as we can only remove $1$ occurrence of $c$.  That leaves character frequencies of $\{a:1,b:1,c:2\}$.  

Function Description  

Complete the isValid function in the editor below.  

isValid has the following parameter(s):  

string s: a string  

Returns  

string: either YES or NO

Input Format

A single string $s$.

Constraints

$1\leq|s|\leq10^5$   
Each character $s[i]\in ascii[a-z]$

Sample Input 0
aabbcd

Sample Output 0
NO

Explanation 0

Given $s="aabbcd"$, we would need to remove two characters, both c and d $\rightarrow$ aabb or a and b $\rightarrow$ abcd, to make it valid. We are limited to removing only one character, so $s$ is invalid.

Sample Input 1
aabbccddeefghi

Sample Output 1
NO

Explanation 1

Frequency counts for the letters are as follows:  

{'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2, 'f': 1, 'g': 1, 'h': 1, 'i': 1}

There are two ways to make the valid string:

Remove $4$ characters with a frequency of $1$: $\{\mbox{fghi}\}$.   
Remove $5$ characters of frequency $2$: $\{\textsf{abcde}\}$.  

Neither of these is an option.

Sample Input 2
abcdefghhgfedecba

Sample Output 2
YES

Explanation 2

All characters occur twice except for $e$ which occurs $3$ times.  We can delete one instance of $e$ to have a valid string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A tennis tournament is about to take place with $N$ players participating in it.
Every player plays with every other player exactly once and there are no ties. That is, every match has a winner and a loser. 
With Naman's birthday approaching, he wants to make sure that each player wins the same number of matches so that nobody gets disheartened.  
Your task is to determine if such a scenario can take place and if yes find one such scenario.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single integer $N$ denoting number of players.

-----Output:-----
- If it's impossible for everyone to win the same number of matches, print "NO" (without quotes).
- Otherwise print "YES" (without quotes) and then print $N$ lines , each line should consist of a string containing only 0s and 1s and should be of size $N$. 
- If the jth character in the ith line is 1 then it means in the match between $i$ and $j$ , $i$ wins. 
- You will get a WA if the output does not correspond to a valid tournament, or if the constraints are not satisfied.
- You will get also WA verdict if any 2 lines have contradicting results or if a player beats himself.

-----Constraints-----
- $1 \leq T \leq 100$
- $2 \leq N \leq 100$

-----Subtasks-----
- 10 points : $2 \leq N \leq 6$
- 90 points :  Original Constraints. 

-----Sample Input:-----
2
3
2

-----Sample Output:-----
YES
010
001
100
NO

-----Explanation:-----
One such scenario for $N$ = $3$ is when player $1$ beats player $2$, player $2$ to beats player $3$ and player $3$ beats player $1$. Here all players win exactly $1$ match.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $n$. You have to construct a permutation of size $n$.

A permutation is an array where each integer from $1$ to $s$ (where $s$ is the size of permutation) occurs exactly once. For example, $[2, 1, 4, 3]$ is a permutation of size $4$; $[1, 2, 4, 5, 3]$ is a permutation of size $5$; $[1, 4, 3]$ is not a permutation (the integer $2$ is absent), $[2, 1, 3, 1]$ is not a permutation (the integer $1$ appears twice).

A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $[2, 1, 4, 3]$ has $10$ subsegments: $[2]$, $[2, 1]$, $[2, 1, 4]$, $[2, 1, 4, 3]$, $[1]$, $[1, 4]$, $[1, 4, 3]$, $[4]$, $[4, 3]$ and $[3]$.

The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $[2, 1, 4, 3]$ is $3$ since the subsegments $[2, 1]$, $[1]$ and $[2, 1, 4, 3]$ are permutations.

You have to construct a permutation of size $n$ with minimum possible value among all permutations of size $n$.


-----Input-----

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

Then, $t$ lines follow. The $i$-th of them contains one integer $n$ ($3 \le n \le 50$) representing the $i$-th test case.


-----Output-----

For each test case, print $n$ integers — the permutation of size $n$ with minimum possible value. If there are multiple such permutations, print any of them.


-----Examples-----

Input
2
5
6
Output
1 4 3 5 2
4 1 6 2 5 3


-----Note-----

In the first example, the permutation $[1, 4, 3, 5, 2]$ is one of the possible answers; its value is $2$.

In the second example, the permutation $[4, 1, 6, 2, 5, 3]$ is one of the possible answers; its value is $2$.

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