vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a tube which is reflective inside represented as two non-coinciding, but parallel to $Ox$ lines. Each line has some special integer points — positions of sensors on sides of the tube.

You are going to emit a laser ray in the tube. To do so, you have to choose two integer points $A$ and $B$ on the first and the second line respectively (coordinates can be negative): the point $A$ is responsible for the position of the laser, and the point $B$ — for the direction of the laser ray. The laser ray is a ray starting at $A$ and directed at $B$ which will reflect from the sides of the tube (it doesn't matter if there are any sensors at a reflection point or not). A sensor will only register the ray if the ray hits exactly at the position of the sensor. [Image] Examples of laser rays. Note that image contains two examples. The $3$ sensors (denoted by black bold points on the tube sides) will register the blue ray but only $2$ will register the red. 

Calculate the maximum number of sensors which can register your ray if you choose points $A$ and $B$ on the first and the second lines respectively.


-----Input-----

The first line contains two integers $n$ and $y_1$ ($1 \le n \le 10^5$, $0 \le y_1 \le 10^9$) — number of sensors on the first line and its $y$ coordinate.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — $x$ coordinates of the sensors on the first line in the ascending order.

The third line contains two integers $m$ and $y_2$ ($1 \le m \le 10^5$, $y_1 < y_2 \le 10^9$) — number of sensors on the second line and its $y$ coordinate. 

The fourth line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \le b_i \le 10^9$) — $x$ coordinates of the sensors on the second line in the ascending order.


-----Output-----

Print the only integer — the maximum number of sensors which can register the ray.


-----Example-----
Input
3 1
1 5 6
1 3
3

Output
3



-----Note-----

One of the solutions illustrated on the image by pair $A_2$ and $B_2$.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Petya loves inequations. Help him find *n* positive integers *a*1,<=*a*2,<=...,<=*a**n*, such that the following two conditions are satisfied:
-  *a*12<=+<=*a*22<=+<=...<=+<=*a**n*2<=≥<=*x*-  *a*1<=+<=*a*2<=+<=...<=+<=*a**n*<=≤<=*y*

Input Specification:
The first line contains three space-separated integers *n*, *x* and *y* (1<=≤<=*n*<=≤<=105,<=1<=≤<=*x*<=≤<=1012,<=1<=≤<=*y*<=≤<=106).

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

Output Specification:
Print *n* positive integers that satisfy the conditions, one integer per line. If such numbers do not exist, print a single number "-1". If there are several solutions, print any of them.

Demo Input:
['5 15 15\n', '2 3 2\n', '1 99 11\n']

Demo Output:
['4\n4\n1\n1\n2\n', '-1\n', '11\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever heard of the unit "○○ tsubo" that expresses the area of ​​land? Since ancient times, one samurai has said the area for making rice to eat in a day.

There is a land of a [m] x b [m]. Enter a and b and create a program that outputs the tsubo area S [tsubo] of the land. 1 tsubo = 3.305785 [m2], and a and b are integers less than or equal to 100.



input


a b


A and b separated by one space are given on one line.

output

Output the tsubo area S in one line. An error of 0.0001 or less is allowed.

Example

Input

15 25


Output

113.437508

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little johny was working on the co-ordinate plane.As he is still a novice he calculates the distance between two points P1 and P2 in the wrong way.He calculates the distance between P1(x1,y1) and P2(x2,y2) as :
D(P1,P2) = |x1 - x2| + |y1 - y2|
His teacher gave him a homework to calculate the area of a circle of radius R. Johny is aware of the definitions of all the figures just like any smart kid is. He knows that a circle is the locus of the point at a fixed radius from the center of the circle in a plane..
 

Input
The first line of input will contain T- number of test cases.It will be followed by T lines each containing the radius R

Output
For every test case output in a separate line the largest integer less than or equal to the area of the circle as calculated by johny..

Constraints

1 ≤ T ≤ 10000
1 ≤ R ≤ 100000000

 

Example
Input:
1
1

Output:
2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob loves everything sweet. His favorite chocolate bar consists of pieces, each piece may contain a nut. Bob wants to break the bar of chocolate into multiple pieces so that each part would contain exactly one nut and any break line goes between two adjacent pieces.

You are asked to calculate the number of ways he can do it. Two ways to break chocolate are considered distinct if one of them contains a break between some two adjacent pieces and the other one doesn't. 

Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 100) — the number of pieces in the chocolate bar.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 1), where 0 represents a piece without the nut and 1 stands for a piece with the nut.


-----Output-----

Print the number of ways to break the chocolate into multiple parts so that each part would contain exactly one nut.


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

Output
1

Input
5
1 0 1 0 1

Output
4



-----Note-----

In the first sample there is exactly one nut, so the number of ways equals 1 — Bob shouldn't make any breaks.

In the second sample you can break the bar in four ways:

10|10|1

1|010|1

10|1|01

1|01|01

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n triangles. 

You are required to find how many triangles are unique out of given triangles.
For each triangle you are given three integers a,b,c , the sides of a
triangle.

A triangle is said to be unique if there is no other triangle with same set of sides.

Note : It is always possible to form triangle with given sides.

INPUT:

First line contains n, the number of triangles. Each of next n lines contain
three integers a,b,c (sides of a triangle).

Output:

print single integer, the number of unique triangles.

Constraints:

1 ≤ n ≤ 10^5
1 ≤ a,b,c ≤ 10^15

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

SAMPLE OUTPUT
1

Explanation

only triangle with sides 8, 2, 9 is unique

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation.

The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that isn't enough for Xenia. She is only beginning to count, so she can calculate a sum only if the summands follow in non-decreasing order. For example, she can't calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3.

You've got the sum that was written on the board. Rearrange the summans and print the sum in such a way that Xenia can calculate the sum.


-----Input-----

The first line contains a non-empty string s — the sum Xenia needs to count. String s contains no spaces. It only contains digits and characters "+". Besides, string s is a correct sum of numbers 1, 2 and 3. String s is at most 100 characters long.


-----Output-----

Print the new sum that Xenia can count.


-----Examples-----
Input
3+2+1

Output
1+2+3

Input
1+1+3+1+3

Output
1+1+1+3+3

Input
2

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata, you will be given a string of text and valid parentheses, such as `"h(el)lo"`. You must return the string, with only the text inside parentheses reversed, so `"h(el)lo"` becomes `"h(le)lo"`. However, if said parenthesized text contains parenthesized text itself, then that too must reversed back, so it faces the original direction. When parentheses are reversed, they should switch directions, so they remain syntactically correct (i.e. `"h((el)l)o"` becomes `"h(l(el))o"`). This pattern should repeat for however many layers of parentheses. There may be multiple groups of parentheses at any level (i.e. `"(1) (2 (3) (4))"`), so be sure to account for these.

For example:
```python
reverse_in_parentheses("h(el)lo") == "h(le)lo"
reverse_in_parentheses("a ((d e) c b)") == "a (b c (d e))"
reverse_in_parentheses("one (two (three) four)") == "one (ruof (three) owt)"
reverse_in_parentheses("one (ruof ((rht)ee) owt)") == "one (two ((thr)ee) four)"
```

Input parentheses will always be valid (i.e. you will never get "(()").

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n points with integer coordinates on the plane. Points are given in a way such that there is no triangle, formed by any three of these n points, which area exceeds S.

Alyona tried to construct a triangle with integer coordinates, which contains all n points and which area doesn't exceed 4S, but, by obvious reason, had no success in that. Please help Alyona construct such triangle. Please note that vertices of resulting triangle are not necessarily chosen from n given points.

Input

In the first line of the input two integers n and S (3 ≤ n ≤ 5000, 1 ≤ S ≤ 1018) are given — the number of points given and the upper bound value of any triangle's area, formed by any three of given n points.

The next n lines describes given points: ith of them consists of two integers xi and yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of ith point.

It is guaranteed that there is at least one triple of points not lying on the same line.

Output

Print the coordinates of three points — vertices of a triangle which contains all n points and which area doesn't exceed 4S.

Coordinates of every triangle's vertex should be printed on a separate line, every coordinate pair should be separated by a single space. Coordinates should be an integers not exceeding 109 by absolute value.

It is guaranteed that there is at least one desired triangle. If there is more than one answer, print any of them.

Example

Input

4 1
0 0
1 0
0 1
1 1


Output

-1 0
2 0
0 2

Note

<image>

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A dice is a cube, its faces contain distinct integers from 1 to 6 as black points. The sum of numbers at the opposite dice faces always equals 7. Please note that there are only two dice (these dices are mirror of each other) that satisfy the given constraints (both of them are shown on the picture on the left).

Alice and Bob play dice. Alice has built a tower from *n* dice. We know that in this tower the adjacent dice contact with faces with distinct numbers. Bob wants to uniquely identify the numbers written on the faces of all dice, from which the tower is built. Unfortunately, Bob is looking at the tower from the face, and so he does not see all the numbers on the faces. Bob sees the number on the top of the tower and the numbers on the two adjacent sides (on the right side of the picture shown what Bob sees).

Help Bob, tell whether it is possible to uniquely identify the numbers on the faces of all the dice in the tower, or not.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of dice in the tower.

The second line contains an integer *x* (1<=≤<=*x*<=≤<=6) — the number Bob sees at the top of the tower. Next *n* lines contain two space-separated integers each: the *i*-th line contains numbers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=6; *a**i*<=≠<=*b**i*) — the numbers Bob sees on the two sidelong faces of the *i*-th dice in the tower.

Consider the dice in the tower indexed from top to bottom from 1 to *n*. That is, the topmost dice has index 1 (the dice whose top face Bob can see). It is guaranteed that it is possible to make a dice tower that will look as described in the input.

Output Specification:
Print "YES" (without the quotes), if it is possible to to uniquely identify the numbers on the faces of all the dice in the tower. If it is impossible, print "NO" (without the quotes).

Demo Input:
['3\n6\n3 2\n5 4\n2 4\n', '3\n3\n2 6\n4 1\n5 3\n']

Demo Output:
['YES', 'NO']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 2013, the writers of Berland State University should prepare problems for n Olympiads. We will assume that the Olympiads are numbered with consecutive integers from 1 to n. For each Olympiad we know how many members of the jury must be involved in its preparation, as well as the time required to prepare the problems for her. Namely, the Olympiad number i should be prepared by p_{i} people for t_{i} days, the preparation for the Olympiad should be a continuous period of time and end exactly one day before the Olympiad. On the day of the Olympiad the juries who have prepared it, already do not work on it.

For example, if the Olympiad is held on December 9th and the preparation takes 7 people and 6 days, all seven members of the jury will work on the problems of the Olympiad from December, 3rd to December, 8th (the jury members won't be working on the problems of this Olympiad on December 9th, that is, some of them can start preparing problems for some other Olympiad). And if the Olympiad is held on November 3rd and requires 5 days of training, the members of the jury will work from October 29th to November 2nd.

In order not to overload the jury the following rule was introduced: one member of the jury can not work on the same day on the tasks for different Olympiads. Write a program that determines what the minimum number of people must be part of the jury so that all Olympiads could be prepared in time.


-----Input-----

The first line contains integer n — the number of Olympiads in 2013 (1 ≤ n ≤ 100). Each of the following n lines contains four integers m_{i}, d_{i}, p_{i} and t_{i} — the month and day of the Olympiad (given without leading zeroes), the needed number of the jury members and the time needed to prepare the i-th Olympiad (1 ≤ m_{i} ≤ 12, d_{i} ≥ 1, 1 ≤ p_{i}, t_{i} ≤ 100), d_{i} doesn't exceed the number of days in month m_{i}. The Olympiads are given in the arbitrary order. Several Olympiads can take place in one day.

Use the modern (Gregorian) calendar in the solution. Note that all dates are given in the year 2013. This is not a leap year, so February has 28 days. Please note, the preparation of some Olympiad can start in 2012 year.


-----Output-----

Print a single number — the minimum jury size.


-----Examples-----
Input
2
5 23 1 2
3 13 2 3

Output
2

Input
3
12 9 2 1
12 8 1 3
12 8 2 2

Output
3

Input
1
1 10 1 13

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $N$ followed by $N$ email addresses. Your task is to print a list containing only valid email addresses in lexicographical order.

Valid email addresses must follow these rules:

It must have the username@websitename.extension format type.
The username can only contain letters, digits, dashes and underscores $[a-z],[A-Z],[0-9],[\text{_}-]$. 
The website name can only have letters and digits $[a-z],[A-Z],[0-9]$. 
The extension can only contain letters $[a-z],[A-Z]$.   
The maximum length of the extension is $3$.

Concept

A filter takes a function returning True or False and applies it to a sequence, returning a list of only those members of the sequence where the function returned True. A Lambda function can be used with filters.

Let's say you have to make a list of the squares of integers from $\mbox{0}$ to $\mbox{9}$ (both included).

>> l = list(range(10))
>> l = list(map(lambda x:x*x, l))

Now, you only require those elements that are greater than $10$ but less than $80$.

>> l = list(filter(lambda x: x > 10 and x < 80, l))

Easy, isn't it?

Example   

Complete the function fun in the editor below.   

fun has the following paramters:   

string s: the string to test   

Returns   

boolean: whether the string is a valid email or not   

Input Format

The first line of input is the integer $N$, the number of email addresses. 

$N$ lines follow, each containing a string.

Constraints

Each line is a non-empty string.

Sample Input
3
lara@hackerrank.com
brian-23@hackerrank.com
britts_54@hackerrank.com

Sample Output
['brian-23@hackerrank.com', 'britts_54@hackerrank.com', 'lara@hackerrank.com']

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yraglac really hates early winter. So he was greatly annoyed when it snowed early this year. His friend however claimed that summer is always too short in Galcary so there’s nothing to complain about.

Yraglac doesn’t believe his friend. So he decides to look up the historical weather report for the past $n$ years to figure out when it usually starts snowing. For each year in the past $n$ years, the historical weather report records $d_ i$, the number of days between the end of summer and the first day of snow on the $i^\textrm {th}$ year. You may assume it never snows during summer in Galcary, as that would be absurd.

Given the historical data, Yraglac would like to know the number of consecutive years right before the current year with a larger gap between the end of summer and the first day of snow. More formally, suppose the current year is $m$. Then he’d like to determine the largest integer $k$ for which $d_{m-1}, d_{m-2},\ldots ,d_{m-k}> d_ m$, or determine that it had never snowed this early in the last $n$ years.

-----Input-----
The first line of the input contains two integers $n$ and $d_ m$. It is guaranteed that $1\leq n\leq 100$ and $0\leq d_ m\leq 100$.

The next line of the input contains $n$ integers. The $i^\textrm {th}$ integer denotes $d_{m-i}$. It is guaranteed that $0\leq d_{m-i}\leq 100$.

-----Output-----
If there exists an integer $k$ for which $d_{m-k}\leq d_ m$, print “It hadn’t snowed this early in $k$ years!” (without quotes). Otherwise, print “It had never snowed this early!” (without quotes).

-----Examples-----
Sample Input 1:
4 2
3 3 3 2
Sample Output 1:
It hadn't snowed this early in 3 years!

Sample Input 2:
2 10
0 100
Sample Output 2:
It hadn't snowed this early in 0 years!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr consisting of integers of size n and 2 additional integers k and x, you need to find the number of subsets of this array of size k, where Absolute difference between the Maximum and Minimum number of the subset is at most x.
Note: As this number that you need to find can be rather large, print it Modulo 10^{9}+7
 
Example 1:
Input:
n = 5, k = 3, x = 5
arr[] = {1, 2, 3, 4, 5}
Output:
10
Explanation :
Possible subsets of size 3 are :-
{1,2,3} {1,2,4} {1,2,5} {1,3,4}
{1,3,5} {1,4,5} {2,3,4} {2,3,5}
{2,4,5} {3,4,5} having difference
of maximum and minimum
element less than equal to 5.
 
Example 2:
Input:
n = 8, k = 4, x = 6
arr[] = {2, 4, 6, 8, 10, 12, 14, 16}
Output:
5
Explanation :
Possible subsets of size 4 are:-
{2,4,6,8} {4,6,8,10} {6,8,10,12}
{8,10,12,14} {10,12,14,16} having
difference of maximum and minimum 
element less than equal to 6.
Your Task:
You don't have to print anything, printing is done by the driver code itself. Your task is to complete the function getAnswer() which takes the array arr[], its size n and two integers k and x as inputs and returns the required result, Modulo 10^{9}+7.
 
Expected Time Complexity: O(n. log(n))
Expected Auxiliary Space: O(n)
 
Constraints:
1 ≤ n ≤ 5×10^{5}
1 ≤ k ≤ n
1 ≤ arr[i], x ≤ 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.
Given two anagrams A and B, return the smallest K for which A and B are K-similar.
Example 1:
Input: A = "ab", B = "ba"
Output: 1


Example 2:
Input: A = "abc", B = "bca"
Output: 2


Example 3:
Input: A = "abac", B = "baca"
Output: 2


Example 4:
Input: A = "aabc", B = "abca"
Output: 2



Note:

1 <= A.length == B.length <= 20
A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
You are given a weighted undirected graph. The vertices are enumerated from 1 to *n*. Your task is to find the shortest path between the vertex 1 and the vertex *n*.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*<=≤<=105,<=0<=≤<=*m*<=≤<=105), where *n* is the number of vertices and *m* is the number of edges. Following *m* lines contain one edge each in form *a**i*, *b**i* and *w**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=1<=≤<=*w**i*<=≤<=106), where *a**i*,<=*b**i* are edge endpoints and *w**i* is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output Specification:
Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

Demo Input:
['5 6\n1 2 2\n2 5 5\n2 3 4\n1 4 1\n4 3 3\n3 5 1\n', '5 6\n1 2 2\n2 5 5\n2 3 4\n1 4 1\n4 3 3\n3 5 1\n']

Demo Output:
['1 4 3 5 ', '1 4 3 5 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S, convert it into a magical string.
A string can be made into a magical string if the alphabets are swapped in the given manner: a->z or z->a, b->y or y->b, and so on.  
 
Note: All the alphabets in the string are in lowercase.
 
Example 1:
Input:
S = varun
Output:
ezifm
Explanation:
Magical string of "varun" 
will be "ezifm" 
since v->e , a->z , 
r->i , u->f and n->m.
 
Example 2:
Input:
S = akshay
Output:
zphszb
Explanation:
Magical string of "akshay" 
will be "zphszb" 
since a->z , k->p , s->h , 
h->s , a->z and y->b.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function magicalString() which takes the string S and returns the magical string.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
 
Constraints:
1<=Length of String<=100

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