vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A little weird green frog speaks in a very strange variation of English: it reverses sentence, omitting all puntuation marks  `, ; ( ) - ` except the final exclamation, question or period. We urgently need help with building a proper translator.
To simplify the task, we always use lower-case letters. Apostrophes are forbidden as well.

Translator should be able to process multiple sentences in one go. Sentences are separated by arbitrary amount of spaces.

**Examples**

`you should use python.` -> `python use should you.`

`look, a fly!` -> `fly a look!`

`multisentence is good. is not it?` -> `good is multisentence. it not is?`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
And while Mishka is enjoying her trip...

Chris is a little brown bear. No one knows, where and when he met Mishka, but for a long time they are together (excluding her current trip). However, best friends are important too. John is Chris' best friend.

Once walking with his friend, John gave Chris the following problem:

At the infinite horizontal road of width w, bounded by lines y = 0 and y = w, there is a bus moving, presented as a convex polygon of n vertices. The bus moves continuously with a constant speed of v in a straight Ox line in direction of decreasing x coordinates, thus in time only x coordinates of its points are changing. Formally, after time t each of x coordinates of its points will be decreased by vt.

There is a pedestrian in the point (0, 0), who can move only by a vertical pedestrian crossing, presented as a segment connecting points (0, 0) and (0, w) with any speed not exceeding u. Thus the pedestrian can move only in a straight line Oy in any direction with any speed not exceeding u and not leaving the road borders. The pedestrian can instantly change his speed, thus, for example, he can stop instantly.

Please look at the sample note picture for better understanding.

We consider the pedestrian is hit by the bus, if at any moment the point he is located in lies strictly inside the bus polygon (this means that if the point lies on the polygon vertex or on its edge, the pedestrian is not hit by the bus).

You are given the bus position at the moment 0. Please help Chris determine minimum amount of time the pedestrian needs to cross the road and reach the point (0, w) and not to be hit by the bus.

Input

The first line of the input contains four integers n, w, v, u (3 ≤ n ≤ 10 000, 1 ≤ w ≤ 109, 1 ≤ v, u ≤ 1000) — the number of the bus polygon vertices, road width, bus speed and pedestrian speed respectively.

The next n lines describes polygon vertices in counter-clockwise order. i-th of them contains pair of integers xi and yi ( - 109 ≤ xi ≤ 109, 0 ≤ yi ≤ w) — coordinates of i-th polygon point. It is guaranteed that the polygon is non-degenerate.

Output

Print the single real t — the time the pedestrian needs to croos the road and not to be hit by the bus. The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.

Example

Input

5 5 1 2
1 2
3 1
4 3
3 4
1 4


Output

5.0000000000

Note

Following image describes initial position in the first sample case:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
The itertools module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination. Together, they form an iterator algebra making it possible to construct specialized tools succinctly and efficiently in pure Python.

You are given a list of N lowercase English letters. For a given integer K, you can select any K indices (assume 1-based indexing) with a uniform probability from the list.
Find the probability that at least one of the K indices selected will contain the letter: ''.

=====Input Format=====
The input consists of three lines. The first line contains the integer N, denoting the length of the list. The next line consists of N space-separated lowercase English letters, denoting the elements of the list.
The third and the last line of input contains the integer K, denoting the number of indices to be selected.

=====Output Format=====
Output a single line consisting of the probability that at least one of the K indices selected contains the letter: 'a'.
Note: The answer must be correct up to 3 decimal places. 

=====Constraints=====
1≤N≤10
1≤K≤N

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array (or list) of scores, return the array of _ranks_ for each value in the array.  The largest value has rank 1, the second largest value has rank 2, and so on. Ties should be handled by assigning the same rank to all tied values. For example:

    ranks([9,3,6,10]) = [2,4,3,1]

and

    ranks([3,3,3,3,3,5,1]) = [2,2,2,2,2,1,7]
    
because there is one 1st place value, a five-way tie for 2nd place, and one in 7th place.

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
A new cottage village called «Flatville» is being built in Flatland. By now they have already built in «Flatville» *n* square houses with the centres on the *Оx*-axis. The houses' sides are parallel to the coordinate axes. It's known that no two houses overlap, but they can touch each other.

The architect bureau, where Peter works, was commissioned to build a new house in «Flatville». The customer wants his future house to be on the *Оx*-axis, to be square in shape, have a side *t*, and touch at least one of the already built houses. For sure, its sides should be parallel to the coordinate axes, its centre should be on the *Ox*-axis and it shouldn't overlap any of the houses in the village.

Peter was given a list of all the houses in «Flatville». Would you help him find the amount of possible positions of the new house?

Input Specification:
The first line of the input data contains numbers *n* and *t* (1<=≤<=*n*,<=*t*<=≤<=1000). Then there follow *n* lines, each of them contains two space-separated integer numbers: *x**i* *a**i*, where *x**i* — *x*-coordinate of the centre of the *i*-th house, and *a**i* — length of its side (<=-<=1000<=≤<=*x**i*<=≤<=1000, 1<=≤<=*a**i*<=≤<=1000).

Output Specification:
Output the amount of possible positions of the new house.

Demo Input:
['2 2\n0 4\n6 2\n', '2 2\n0 4\n5 2\n', '2 3\n0 4\n5 2\n']

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

Note:
It is possible for the *x*-coordinate of the new house to have non-integer value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Regular Tic-Tac-Toe is boring.

That's why in this Kata you will be playing  Tic-Tac-Toe in **3D** using a 4 x 4 x 4 matrix!



# Kata Task

Play the game. Work out who wins.

Return a string

* `O wins after  moves`
* `X wins after  moves`
* `No winner`

# Rules

* Player `O` always goes first
* Input `moves` is list/array/tuple of `[x,y,z]` (zero based)
* Each player takes a turn until you find a winner, or there are no moves left
* Four of the same symbols in a row wins
* There may be more moves provided than are necessary to finish the game - that is for you to figure out



Good Luck!
DM

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus is the director of a large corporation. There are *n* secretaries working for the corporation, each of them corresponds via the famous Spyke VoIP system during the day. We know that when two people call each other via Spyke, the Spyke network assigns a unique ID to this call, a positive integer session number.

One day Polycarpus wondered which secretaries are talking via the Spyke and which are not. For each secretary, he wrote out either the session number of his call or a 0 if this secretary wasn't talking via Spyke at that moment.

Help Polycarpus analyze these data and find out the number of pairs of secretaries that are talking. If Polycarpus has made a mistake in the data and the described situation could not have taken place, say so.

Note that the secretaries can correspond via Spyke not only with each other, but also with the people from other places. Also, Spyke conferences aren't permitted — that is, one call connects exactly two people.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=103) — the number of secretaries in Polycarpus's corporation. The next line contains *n* space-separated integers: *id*1,<=*id*2,<=...,<=*id**n* (0<=≤<=*id**i*<=≤<=109). Number *id**i* equals the number of the call session of the *i*-th secretary, if the secretary is talking via Spyke, or zero otherwise.

Consider the secretaries indexed from 1 to *n* in some way.

Output Specification:
Print a single integer — the number of pairs of chatting secretaries, or -1 if Polycarpus's got a mistake in his records and the described situation could not have taken place.

Demo Input:
['6\n0 1 7 1 7 10\n', '3\n1 1 1\n', '1\n0\n']

Demo Output:
['2\n', '-1\n', '0\n']

Note:
In the first test sample there are two Spyke calls between secretaries: secretary 2 and secretary 4, secretary 3 and secretary 5.

In the second test sample the described situation is impossible as conferences aren't allowed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the symmetric difference of two sets $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and $B = \\{b_0, b_1, ..., b_{m-1}\\}$.

Constraints

* $1 \leq n, m \leq 200,000$
* $0 \leq a_0 < a_1 < ... < a_{n-1} \leq 10^9$
* $0 \leq b_0 < b_1 < ... < b_{m-1} \leq 10^9$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ... \; a_{n-1}$
$m$
$b_0 \; b_1 \; ... \; b_{m-1}$


Elements in $A$ and $B$ are given in ascending order. There are no duplicate elements in each set.

Output

Print elements in the symmetric difference in ascending order. Print an element in a line.

Example

Input

7
1 2 3 4 5 6 7
4
2 4 6 8


Output

1
3
5
7
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an array $A=[a_0,a_1,...,a_{n-1}]$ of $n$ integers. We perform $\textit{q}$ queries of the following type on $\mbox{A}$:

Sort all the elements in the subsegment $a_{l_i},a_{l_i+1},\ldots,a_{r_i}$.

Given $\mbox{A}$, can you find and print the value at index $\boldsymbol{\mbox{k}}$ (where $0\leq k<n$) after performing $\textit{q}$ queries?

Input Format

The first line contains three positive space-separated integers describing the respective values of $n$ (the number of integers in $\mbox{A}$), $\textit{q}$ (the number of queries), and $\boldsymbol{\mbox{k}}$ (an index in $\mbox{A}$). 

The next line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$. 

Each line $j$ of the $\textit{q}$ subsequent lines contain two space-separated integers describing the respective $l_{j}$ and $r_j$ values for query $j$.

Constraints

$1\leq n,q\leq75000$
$0\leq k\leq n-1$
$-10^9\leq a_i\leq10^9$
$0\leq l_i\leq r_i<n$

Output Format

Print a single integer denoting the value of $a_{k}$ after processing all $\textit{q}$ queries.

Sample Input 0

3 1 1
3 2 1
0 1

Sample Output 0

3

Explanation 0

$A=[3,2,1]$ 

There is only one query to perform. When we sort the subarray ranging from index $\mbox{0}$ to index $\mbox{1}$, we get $A'=[2,3,1]$. We then print the element at index $\mbox{1}$, which is $3$. 

Sample Input 1

4 2 0
4 3 2 1
0 2
1 3

Sample Output 1

2 

Explanation 1       

$A=[4,3,2,1]$ 

There are $q=2$ queries:

When we sort the subarray ranging from index $\mbox{0}$ to index $2$, we get $A'=[2,3,4,1]$. 
When we sort the subarray of $\mbox{A'}$ from index $\mbox{1}$ to index $3$, we get $A''=[2,1,3,4]$.

Having performed all of the queries, we print the element at index $\mbox{0}$, which is $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area. 

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.


-----Input-----

The first line of the input contains six positive integers x_1, y_1, x_2, y_2, x_3, y_3 (1 ≤ x_1, y_1, x_2, y_2, x_3, y_3 ≤ 100), where x_{i} and y_{i} determine the length and width of the logo of the i-th company respectively.


-----Output-----

If it is impossible to place all the three logos on a square shield, print a single integer "-1" (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters "A", "B" or "C". The sets of the same letters should form solid rectangles, provided that:  the sizes of the rectangle composed from letters "A" should be equal to the sizes of the logo of the first company,  the sizes of the rectangle composed from letters "B" should be equal to the sizes of the logo of the second company,  the sizes of the rectangle composed from letters "C" should be equal to the sizes of the logo of the third company, 

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn't have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.


-----Examples-----
Input
5 1 2 5 5 2

Output
5
AAAAA
BBBBB
BBBBB
CCCCC
CCCCC

Input
4 4 2 6 4 2

Output
6
BBBBBB
BBBBBB
AAAACC
AAAACC
AAAACC
AAAACC

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $4n$ sticks, the length of the $i$-th stick is $a_i$.

You have to create $n$ rectangles, each rectangle will consist of exactly $4$ sticks from the given set. The rectangle consists of four sides, opposite sides should have equal length and all angles in it should be right. Note that each stick can be used in only one rectangle. Each stick should be used as a side, you cannot break the stick or use it not to the full length.

You want to all rectangles to have equal area. The area of the rectangle with sides $a$ and $b$ is $a \cdot b$.

Your task is to say if it is possible to create exactly $n$ rectangles of equal area or not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 500$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 100$) — the number of rectangles.

The second line of the query contains $4n$ integers $a_1, a_2, \dots, a_{4n}$ ($1 \le a_i \le 10^4$), where $a_i$ is the length of the $i$-th stick.


-----Output-----

For each query print the answer to it. If it is impossible to create exactly $n$ rectangles of equal area using given sticks, print "NO". Otherwise print "YES".


-----Example-----
Input
5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000

Output
YES
YES
NO
YES
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Annie has gotten bored of winning every coding contest and farming unlimited rating. Today, she is going to farm potatoes instead.

Annie's garden is an infinite 2D plane. She has n potatoes to plant, and the i-th potato must be planted at (x_i,y_i). Starting at the point (0, 0), Annie begins walking, in one step she can travel one unit right or up (increasing her x or y coordinate by 1 respectively). At any point (X,Y) during her walk she can plant some potatoes at arbitrary points using her potato gun, consuming max(|X-x|,|Y-y|) units of energy in order to plant a potato at (x,y). Find the minimum total energy required to plant every potato.

Note that Annie may plant any number of potatoes from any point.

Input

The first line contains the integer n (1 ≤ n ≤ 800 000).

The next n lines contain two integers x_i and y_i (0 ≤ x_i,y_i ≤ 10^9), representing the location of the i-th potato. It is possible that some potatoes should be planted in the same location.

Output

Print the minimum total energy to plant all potatoes.

Examples

Input


2
1 1
2 2


Output


0


Input


2
1 1
2 0


Output


1


Input


3
5 5
7 7
4 9


Output


2


Input


10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5


Output


19


Input


10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1


Output


6

Note

In example 1, Annie can travel to each spot directly and plant a potato with no energy required.

In example 2, moving to (1,0), Annie plants the second potato using 1 energy. Next, she travels to (1,1) and plants the first potato with 0 energy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bizon the Champion is called the Champion for a reason. 

Bizon the Champion has recently got a present — a new glass cupboard with n shelves and he decided to put all his presents there. All the presents can be divided into two types: medals and cups. Bizon the Champion has a_1 first prize cups, a_2 second prize cups and a_3 third prize cups. Besides, he has b_1 first prize medals, b_2 second prize medals and b_3 third prize medals. 

Naturally, the rewards in the cupboard must look good, that's why Bizon the Champion decided to follow the rules:  any shelf cannot contain both cups and medals at the same time;  no shelf can contain more than five cups;  no shelf can have more than ten medals. 

Help Bizon the Champion find out if we can put all the rewards so that all the conditions are fulfilled.


-----Input-----

The first line contains integers a_1, a_2 and a_3 (0 ≤ a_1, a_2, a_3 ≤ 100). The second line contains integers b_1, b_2 and b_3 (0 ≤ b_1, b_2, b_3 ≤ 100). The third line contains integer n (1 ≤ n ≤ 100).

The numbers in the lines are separated by single spaces.


-----Output-----

Print "YES" (without the quotes) if all the rewards can be put on the shelves in the described manner. Otherwise, print "NO" (without the quotes).


-----Examples-----
Input
1 1 1
1 1 1
4

Output
YES

Input
1 1 3
2 3 4
2

Output
YES

Input
1 0 0
1 0 0
1

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phone represents a password as a string of two lowercase English letters.

Mu-mu's enemy Kashtanka wants to unlock Mu-mu's phone to steal some sensible information, but it can only bark n distinct words, each of which can be represented as a string of two lowercase English letters. Kashtanka wants to bark several words (not necessarily distinct) one after another to pronounce a string containing the password as a substring. Tell if it's possible to unlock the phone in this way, or not.


-----Input-----

The first line contains two lowercase English letters — the password on the phone.

The second line contains single integer n (1 ≤ n ≤ 100) — the number of words Kashtanka knows.

The next n lines contain two lowercase English letters each, representing the words Kashtanka knows. The words are guaranteed to be distinct.


-----Output-----

Print "YES" if Kashtanka can bark several words in a line forming a string containing the password, and "NO" otherwise.

You can print each letter in arbitrary case (upper or lower).


-----Examples-----
Input
ya
4
ah
oy
to
ha

Output
YES

Input
hp
2
ht
tp

Output
NO

Input
ah
1
ha

Output
YES



-----Note-----

In the first example the password is "ya", and Kashtanka can bark "oy" and then "ah", and then "ha" to form the string "oyahha" which contains the password. So, the answer is "YES".

In the second example Kashtanka can't produce a string containing password as a substring. Note that it can bark "ht" and then "tp" producing "http", but it doesn't contain the password "hp" as a substring.

In the third example the string "hahahaha" contains "ah" as a substring.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a height h, count the maximum number of balanced binary trees possible with height h. Print the result modulo 10^{9} + 7.
Note : A balanced binary tree is one in which for every node, the difference between heights of left and right subtree is not more than 1.
Example 1:
Input: h = 2
Output: 3 
Explanation: The maximum number of balanced 
binary trees possible with height 2 is 3. 
Example 2:
Input: h = 3
Output: 15
Explanation: The maximum number of balanced
binary trees possible with height 3 is 15. 
Your Task:  
You dont need to read input or print anything. Complete the function countBT() which takes h as input parameter and returns the maximum number of balanced binary trees possible with height h. 
Expected Time Complexity: O(h)
Expected Auxiliary Space: O(h)
Constraints:
1<= n <=10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N positive integers A1, A2, ... AN. Find the number of ways to distribute them in 2 groups in such a way that sum of numbers in each group is greater or equal K. The answer can be large so output it modulo 10^9 + 7.

Input
The first line contains two space-separated integers N and K.
The second line contains N space-separated integers: A1, A2, ... AN.

Output
Output one integer - answer for the question modulo 10^9 + 7.

Constraints
 0 < N  ≤ 100
 0 < Ai  ≤ 10^9
 0 < K  ≤ 10^5
 0 < N  ≤ 20 in 28 % of the test data.

SAMPLE INPUT
2 5
6 6


SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In another Kata I came across a weird `sort` function to implement. We had to sort characters as usual ( 'A' before 'Z' and 'Z' before 'a' ) except that the `numbers` had to be sorted **after** the `letters` ( '0' after 'z') !!!

(After a couple of hours trying to solve this unusual-sorting-kata I discovered final tests used **usual** sort (digits  **before** letters :-)

So, the `unusualSort/unusual_sort` function you'll have to code will sort `letters` as usual, but will put `digits` (or one-digit-long `numbers` ) **after** `letters`.

## Examples
```python
unusual_sort(["a","z","b"])  # -> ["a","b","z"]  as usual
unusual_sort(["a","Z","B"])  # -> ["B","Z","a"]  as usual

//... but ...
unusual_sort(["1","z","a"])  # -> ["a","z","1"]
unusual_sort(["1","Z","a"])  # -> ["Z","a","1"]
unusual_sort([3,2,1"a","z","b"])  # -> ["a","b","z",1,2,3]
unusual_sort([3,"2",1,"a","c","b"])  # -> ["a","b","c",1,"2",3]
```
**Note**: `digits` will be sorted **after** "`same-digit-numbers`", eg: `1` is before `"1"`, `"2"` after `2`.
```python
unusual_sort([3,"2",1,"1","3",2])  # -> [1,"1",2,"2",3,"3"]
```

You may assume that **argument** will always be an `array/list` of **characters** or **one-digit-long numbers**.

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