vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vanja and Miksi really like games. After playing one game for a long time, they decided to invent another game!
In this game, they have a sequence $A_1, A_2, \dots, A_N$ and two numbers $Z_1$ and $Z_2$. The rules of the game are as follows:
- The players take turns alternately, starting with Vanja.
- There is an integer $S$; at the beginning, $S = 0$.
- In each turn, the current player must choose an arbitrary element of $A$ and either add that number to $S$ or subtract it from $S$. Each element can be selected multiple times.
- Afterwards, if $S = Z_1$ or $S = Z_2$, the current player (the player who made $S$ equal to $Z_1$ or $Z_2$) is the winner of the game.
- If the game lasts for $10^{10}$ turns, Vanja and Miksi decide to declare it a tie.
Can you help the boys determine the winner of the game? Please note that the game can end in a tie (if nobody can make $S = Z_1$ or $S = Z_2$ in the first $10^{10}$ moves).
Both players play optimally, i.e. if there is a move which guarantees the current player's victory regardless of the other player's moves, the current player will make such a move. If the current player cannot win and there is a move which guarantees that the game will end in a tie, the current player will make such a move.

-----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 three space-separated integers $N$, $Z_1$ and $Z_2$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
- For each test case, print a single line containing one integer — the final result of the game:
- $1$ if Vanja (the first player) has a winning strategy
- $2$ if Miksi (the second player) has a winning strategy
- $0$ if the game ends in a tie

-----Constraints-----
- $1 \le T \le 50$
- $1 \le N \le 50$
- $|Z_1|, |Z_2| \le 10^9$
- $|A_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (25 points): $N = 2$
Subtask #2 (75 points): original constraints

-----Example Input-----
3
2 6 4
-4 10
1 1 -1
2
2 0 7
3 4

-----Example Output-----
1
0
2

-----Explanation-----
Example case 1: The first player can choose the value $A_1 = -4$, subtract it from $S = 0$ and obtain $S = - (-4) = 4 = Z_2$. The winner is the first player.  
Example case 2: It can be proven that neither player is able to reach $S = Z_1$ or $S = Z_2$. The result is a tie.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The window of Takahashi's room has a width of A. There are two curtains hung over the window, each of which has a horizontal length of B. (Vertically, the curtains are long enough to cover the whole window.)
We will close the window so as to minimize the total horizontal length of the uncovered part of the window.
Find the total horizontal length of the uncovered parts of the window then.

-----Constraints-----
 - 1 \leq A \leq 100
 - 1 \leq B \leq 100
 - A and B are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the total horizontal length of the uncovered parts of the window.

-----Sample Input-----
12 4

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

We have a window with a horizontal length of 12, and two curtains, each of length 4, that cover both ends of the window, for example. The uncovered part has a horizontal length of 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year Ratings Change

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One very well-known internet resource site (let's call it X) has come up with a New Year adventure. Specifically, they decided to give ratings to all visitors.

There are *n* users on the site, for each user we know the rating value he wants to get as a New Year Present. We know that user *i* wants to get at least *a**i* rating units as a present.

The X site is administered by very creative and thrifty people. On the one hand, they want to give distinct ratings and on the other hand, the total sum of the ratings in the present must be as small as possible.

Help site X cope with the challenging task of rating distribution. Find the optimal distribution.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=3·105) — the number of users on the site. The next line contains integer sequence *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print a sequence of integers *b*1,<=*b*2,<=...,<=*b**n*. Number *b**i* means that user *i* gets *b**i* of rating as a present. The printed sequence must meet the problem conditions. 

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

Demo Input:
['3\n5 1 1\n', '1\n1000000000\n']

Demo Output:
['5 1 2\n', '1000000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is a very brilliant student. He considers '4' and '7' as Magic numbers. The numbers containing only magic numbers are also magical. Given a magic number N ,he wants to know what could be the next magical number greater than the given number.

-----Input-----

First line of input contains number of test cases T. For each test case, there is exits only one line containing a magic number N. 

-----Output-----

For each test case,  output a single line containing the next greater magical number.

-----Constraints-----
1<=T<=1000
4<= N<=10^100

-----Example-----
Input:
2
4
47

Output:
7
74

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Akash has his maths test tomorrow. He secretly found out one of the questions from the test.
As the test is online, he wants to write a code that solves the question. However, he is not good at coding and thus, wants Chef to help him with that.

Chef is given a function F(X) such that the condition:
F(X) = F(2\cdot X)  
holds true for all X, where X is a positive integer.

For a given positive integer N, find the maximum number of distinct elements in the array [F(1), F(2), F(3), \ldots, F(N)].

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

- First line will contain T - the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, one integer N.

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

For each test case, output in a single line, the maximum number of distinct elements in the array [F(1), F(2), F(3), \ldots, F(N)].

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (30 points): $1 ≤ N ≤ 1000$
Subtask 2 (70 points): Original Constraints.

----- Sample Input 1 ------ 
2
2
5
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
Test case $1$: Let $X = 1$. Thus, $2 = 2\cdot 1 = 2\cdot X$. Therefore, $F(1) = F(2)$. So, in the array $[F(1), F(2)]$, there is only $1$ distinct element.

Test case $2$: Here, we can take $X = 1$. Thus $F(1) = F(2)$. Similarly, if we take $X = 2$, $F(2) = F(4)$. This means that $F(1) = F(2) = F(4)$.  
However, it can be possible that the values $F(1), F(3),$ and $F(5)$ are distinct. Hence, the maximum number of distinct elements in the array $[F(1), F(2), F(3), F(4), F(5)]$ is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Calendars in widespread use today include the Gregorian calendar, which is the de facto international standard, and is used almost everywhere in the world for civil purposes. The Gregorian reform modified the Julian calendar's scheme of leap years as follows:

 Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100; the centurial years that are exactly divisible by 400 are still leap years. For example, the year 1900 is not a leap year; the year 2000 is a leap year.  [Image] 

In this problem, you have been given two dates and your task is to calculate how many days are between them. Note, that leap years have unusual number of days in February.

Look at the sample to understand what borders are included in the aswer.


-----Input-----

The first two lines contain two dates, each date is in the format yyyy:mm:dd (1900 ≤ yyyy ≤ 2038 and yyyy:mm:dd is a legal date).


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
1900:01:01
2038:12:31

Output
50768

Input
1996:03:09
1991:11:12

Output
1579

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jimmy is performing in ByteLand today! Anthony the Ant is a huge fan of Jimmy’s music, so he can’t wait to get to the concert.

ByteLand consists of of $N$ intersections and $M$ roads. Every road is bidirectional and connects two distinct intersections. Anthony is currently on intersection $s$ and the concert is being held at intersection $t$. Anthony must get to the concert in $T$ seconds and he can travel at $1$ meter/second.

Unfortunately for Anthony, he has a huge fear of spiders and ByteLand is full of spiders. Spiders reside at certain intersections in ByteLand. Anthony will choose a path from $s$ to $t$ that maximizes $D$, the minimum distance between any intersection on the path and any spider, such that the path can be travelled in no more than $T$ seconds.

-----Input-----
The first line contains three integers $N$ ($2\leq N\leq 100000$), $M$ ($1\leq M\leq \min (200000, n(n-1)/2)$), and $T$ ($1\leq T\leq 10^9$).

Each of the next $M$ lines specify the roads. A road is described by three integers $u, v$ ($0\leq u, v\leq N-1$ and $u\neq v$) and $d$ ($1\leq d\leq 10000$), which means that a $d$ meters long road connects intersections $u$ and $v$. It is guaranteed that at most one road connect any two intersections, and that there exists a path between any two intersections.

The next line contains $s, t$ ($0\leq s, t\leq N-1$ and $s\neq t$, representing Anthony’s current location and the location of the concert. You may assume Anthony can always travel from $s$ to $t$ in no more than $T$ seconds.

The last line contains a integer $1\leq K\leq N$, denoting the number of intersections occupied by spiders, followed by $K$ integers $0\leq a_ i\leq N-1$ denoting the intersections with spiders.

-----Output-----
Print the maximum $D$ (as defined earlier) for the path Anthony takes.

-----Examples-----
Sample Input:
4 4 3000
0 1 1
1 3 1
2 0 2018
2 3 42
0 3
1 1
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Would you want to fight against bears riding horses? Me neither.

Limak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course.

Cavalry of Bearland consists of n warriors and n horses. i-th warrior has strength wi and i-th horse has strength hi. Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all n units. Good assignment of warriors and horses makes cavalry truly powerful.

Initially, i-th warrior has i-th horse. You are given q queries. In each query two warriors swap their horses with each other.

General Limak must be ready for every possible situation. What if warriors weren't allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for n ≥ 2 there is always at least one correct assignment).

Note that we can't leave a warrior without a horse.

Input

The first line contains two space-separated integers, n and q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

The second line contains n space-separated integers, w1, w2, ..., wn (1 ≤ wi ≤ 106) — strengths of warriors.

The third line contains n space-separated integers, h1, h2, ..., hn (1 ≤ hi ≤ 106) — strengths of horses.

Next q lines describe queries. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), indices of warriors who swap their horses with each other.

Output

Print q lines with answers to queries. In i-th line print the maximum possible strength of cavalry after first i queries.

Examples

Input

4 2
1 10 100 1000
3 7 2 5
2 4
2 4


Output

5732
7532


Input

3 3
7 11 5
3 2 1
1 2
1 3
2 3


Output

44
48
52


Input

7 4
1 2 4 8 16 32 64
87 40 77 29 50 11 18
1 5
2 7
6 2
5 6


Output

9315
9308
9315
9315

Note

Clarification for the first sample:

Warriors: 1 10 100 1000

Horses: 3 7 2 5 

After first query situation looks like the following:

Warriors: 1 10 100 1000

Horses: 3 5 2 7 

We can get 1·2 + 10·3 + 100·7 + 1000·5 = 5732 (note that no hussar takes his own horse in this assignment).

After second query we get back to initial situation and optimal assignment is 1·2 + 10·3 + 100·5 + 1000·7 = 7532.

Clarification for the second sample. After first query:

Warriors: 7 11 5

Horses: 2 3 1

Optimal assignment is 7·1 + 11·2 + 5·3 = 44.

Then after second query 7·3 + 11·2 + 5·1 = 48.

Finally 7·2 + 11·3 + 5·1 = 52.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a rooted tree with $n$ nodes, numbered $1..n$. Each node will have a fixed integer $b$, and for each, a uniform random real number is chosen in the interval $[0..b]$.

What is the probability that the random numbers chosen cause the tree to form a Heap (i.e., the random value in each node is less than the random values in its children)?

This probability can always be expressed as a rational number $\frac{P}{Q}$, with $Q{\not\equiv }0 \pmod{10^9{+}7}$. You are to output the probability as $P{\cdot }Q^{-1} \bmod {10^9{+}7}$, where $Q^{-1}$ is an integer, which is the multiplicative inverse of $Q$ modulo $10^9{+}7$ ($Q\! \cdot \! Q^{-1}\! \equiv \! 1 \pmod{10^9{+}7}$). (Note: $P{\cdot }Q^{-1}\bmod {10^9{+}7}$ does not depend on whether $P$ and $Q$ are relatively prime, only on their ratio $\frac{P}{Q}$.)

-----Input-----
Each test case will begin with a line with a single integer $n$ ($1\! \le \! n\! \le \! 300$), which is the number of nodes in the tree.

Each of the next $n$ lines will contain a pair of space-separated integers $b$ ($1\! \le \! b\! \le \! 10^9$) and $p$ ($0\! \le \! p\! \le \! n$) describing a node of the tree, where $b$ is the fixed integer value in the node and $p$ is the node number of its parent. The nodes are listed in order; node $1$ is first, then node $2$, and so on. A single node will have a parent $p{=}0$. This is the root of the tree.

-----Output-----
Output a single integer, which is the probability expressed as $(P{\cdot }Q^{-1}) \bmod ({10^9{+}7})$.

-----Examples-----
Sample Input:
2
1000000000 0
1000000000 1
Sample Output:
500000004

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
F: Substring decomposition

problem

Given the two strings S and T and the integer k. Considering consecutive substrings of length k or more of T, determine if S can be constructed by concatenating them.

Where the string s = s_1 s_2 ... s_n is a contiguous substring s [l, r] = s_l s_ {l + 1} ... s_r (1 \ leq l \ leq r \ leq n) , S refers to a character string created by cutting out the l-th to r-th characters of s, and its length is r --l + 1.

Input format


S
T
k


Constraint

* S and T consist of lowercase alphabets
* 1 \ leq | S |, | T | \ leq 2 \ times 10 ^ 5
* 1 \ leq k \ leq | T |



Output format

Print `Yes` when S can be configured, and` No` on one line otherwise.

Input example 1


abracadabra
cadabra
Four


Output example 1


Yes

You can construct `abracadabra` by concatenating` abra` and `cadabra`, which are substrings of T with a length of 4 or more, which is a string equal to S.

Input example 2


abcd
zcba
1


Output example 2


No

Input example 3


abc
zcba
1


Output example 3


Yes

Input example 4


abcdefg
abcddefg
Four


Output example 4


No





Example

Input

abracadabra
cadabra
4


Output

Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of Chef's friends offered him a deal: during $D$ days, they are going to exchange money. For each $i$ ($1 \le i \le D$), on the $i$-th day, Chef's friend would give Chef $A$ rupees, while Chef would give his friend $2^{i-1}$ rupees ($1$ rupee on day $1$, $2$ rupees on day $2$, $4$ rupees on day $3$, and so on). Chef's profit from the deal is the total number of rupees he received from his friend minus the total number of rupees he gave his friend.
Chef decided to ask for your advice before accepting the deal. You want to help him by telling him two numbers $D_1$ and $D_2$, where $D_1$ is the maximum value of $D$ such that Chef should accept the deal, i.e. his profit from the deal is positive if $D = D_1$, and $D_2$ is the value of $D$ that leads to the maximum possible profit for Chef. If there are multiple values of $D$ that lead to the maximum profit, $D_2$ is the smallest of these values.

-----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 and only line of each test case contains a single integer $A$.

-----Output-----
For each test case, print a single line containing two space-separated integers $D_1$ and $D_2$.

-----Constraints-----
- $1 \le T \le 100,000$
- $5 \le A \le 10^9$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
4
5
8
9
1000000000

-----Example Output-----
4 3
5 3
5 4
35 30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rectangular grid of lattice points from (0, 0) to (n, m) inclusive. You have to choose exactly 4 different points to build a polyline possibly with self-intersections and self-touching. This polyline should be as long as possible.

A polyline defined by points p1, p2, p3, p4 consists of the line segments p1 p2, p2 p3, p3 p4, and its length is the sum of the lengths of the individual line segments.

Input

The only line of the input contains two integers n and m (0 ≤ n, m ≤ 1000). It is guaranteed that grid contains at least 4 different points.

Output

Print 4 lines with two integers per line separated by space — coordinates of points p1, p2, p3, p4 in order which represent the longest possible polyline.

Judge program compares your answer and jury's answer with 10 - 6 precision.

Examples

Input

1 1


Output

1 1
0 0
1 0
0 1


Input

0 10


Output

0 1
0 10
0 0
0 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikhil has some boxes and balls. He now wonders how large a ball he can fit in a given box. Given the dimensions of a box, help Nikhil determine the radius of the largest ball that he can fit in the box. Assume that an inflated ball will be spherical.

Input:-

The first line of the input will be T, the number of test cases. Next follows T lines each containing three space separated integers (L, B, H) which are the length, breadth and height of the box respectively.

Output:-

Print T lines each consisting of the radius(correct to 1 decimal place) of the largest ball that Nikhil can fit in the box of dimensions corresponding to each test case.

Constraints:

1 ≤ T ≤ 10^5 
1 ≤ L, B, H ≤ 10^18

SAMPLE INPUT
2
1 2 3
3 3 7

SAMPLE OUTPUT
0.5
1.5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of gears.

The second line contains n digits a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1) — the sequence of active teeth: the active tooth of the i-th gear contains number a_{i}.


-----Output-----

In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.


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

Output
Yes

Input
5
4 2 1 4 3

Output
Yes

Input
4
0 2 3 1

Output
No



-----Note-----

In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gerald got tired of playing board games with the usual six-sided die, and he bought a toy called Randomizer. It functions as follows.

A Randomizer has its own coordinate plane on which a strictly convex polygon is painted, the polygon is called a basic polygon. If you shake a Randomizer, it draws some nondegenerate (i.e. having a non-zero area) convex polygon with vertices at some vertices of the basic polygon. The result of the roll (more precisely, the result of the shaking) is considered to be the number of points with integer coordinates, which were strictly inside (the points on the border are not considered) the selected polygon. Now Gerald is wondering: what is the expected result of shaking the Randomizer?

During the shaking the Randomizer considers all the possible non-degenerate convex polygons with vertices at the vertices of the basic polygon. Let's assume that there are k versions of the polygons. Then the Randomizer chooses each of them with probability <image>.

Input

The first line of the input contains a single integer n (3 ≤ n ≤ 100 000) — the number of vertices of the basic polygon. 

Next n lines contain the coordinates of the vertices of the basic polygon. The i-th of these lines contain two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th vertex of the polygon. The vertices are given in the counter-clockwise order.

Output

Print the sought expected value with absolute or relative error at most 10 - 9.

Examples

Input

4
0 0
2 0
2 2
0 2


Output

0.2


Input

5
0 0
2 0
2 2
1 3
0 2


Output

0.8125

Note

A polygon is called strictly convex if it is convex and no its vertices lie on the same line.

Let's assume that a random variable takes values x1, ..., xn with probabilities p1, ..., pn, correspondingly. Then the expected value of this variable equals to <image>.

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