vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
So, the Berland is at war with its eternal enemy Flatland again, and Vasya, an accountant, was assigned to fulfil his duty to the nation. 

Right now the situation in Berland is dismal — their both cities are surrounded! The armies of flatlanders stand on the borders of circles, the circles' centers are in the surrounded cities. At any moment all points of the flatland ring can begin to move quickly in the direction of the city — that's the strategy the flatlanders usually follow when they besiege cities.

The berlanders are sure that they can repel the enemy's attack if they learn the exact time the attack starts. For that they need to construct a radar that would register any movement at the distance of at most r from it. Thus, we can install a radar at such point, that at least one point of the enemy ring will be in its detecting range (that is, at a distance of at most r). Then the radar can immediately inform about the enemy's attack. 

Due to the newest technologies, we can place a radar at any point without any problems. But the problem is that the berlanders have the time to make only one radar. Besides, the larger the detection radius (r) is, the more the radar costs.

That's why Vasya's task (that is, your task) is to find the minimum possible detection radius for the radar. In other words, your task is to find the minimum radius r (r ≥ 0) such, that a radar with radius r can be installed at some point and it can register the start of the movements of both flatland rings from that point. 

In this problem you can consider the cities as material points, the attacking enemy rings - as circles with centers in the cities, the radar's detection range — as a disk (including the border) with the center at the point where the radar is placed.

Input

The input files consist of two lines. Each line represents the city and the flatland ring that surrounds it as three space-separated integers xi, yi, ri (|xi|, |yi| ≤ 104; 1 ≤ ri ≤ 104) — the city's coordinates and the distance from the city to the flatlanders, correspondingly.

It is guaranteed that the cities are located at different points.

Output

Print a single real number — the minimum detection radius of the described radar. The answer is considered correct if the absolute or relative error does not exceed 10 - 6.

Examples

Input

0 0 1
6 0 3


Output

1.000000000000000

Input

-10 10 3
10 -10 3


Output

11.142135623730951

Note

The figure below shows the answer to the first sample. In this sample the best decision is to put the radar at point with coordinates (2, 0). 

<image>

The figure below shows the answer for the second sample. In this sample the best decision is to put the radar at point with coordinates (0, 0). 

<image>

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2. 

The finals will have *n* questions, *m* of them are auction questions and *n*<=-<=*m* of them are regular questions. Each question has a price. The price of the *i*-th question is *a**i* points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.

Input Specification:
The first line contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100; *m*<=≤<=*min*(*n*,<=30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=107) — the prices of the questions. The third line contains *m* distinct integers *b**i* (1<=≤<=*b**i*<=≤<=*n*) — the numbers of auction questions. Assume that the questions are numbered from 1 to *n*.

Output Specification:
In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.

Demo Input:
['4 1\n1 3 7 5\n3\n', '3 2\n10 3 8\n2 3\n', '2 2\n100 200\n1 2\n']

Demo Output:
['18\n', '40\n', '400\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The positive integer a is a divisor of the positive integer b if and only if there exists a positive integer c such that a × c = b. 

King Astyages thinks a positive integer x is extraordinarily nice if the number of its even divisors is equal to the number of its odd divisors.

For example 3 has two positive divisors 3 and 1, both of which are odd, so 3 is not extraordinarily nice. On the other hand 2 is only divisible by 2 and 1, so it has one odd and one even divisor. Therefore 2 is extraordinarily nice.

Given a positive integer x determine whether it's extraordinarily nice.

Input

The input contains only a single integer x (1 ≤ x ≤ 103).

Output

Write a single yes or no. Write yes if the number is extraordinarily nice and no otherwise.

You don't need to care about capital or small letters. The output is case-insensitive.

Examples

Input

2


Output

yes


Input

3


Output

no

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* points on a plane. All points are different.

Find the number of different groups of three points (*A*,<=*B*,<=*C*) such that point *B* is the middle of segment *AC*. 

The groups of three points are considered unordered, that is, if point *B* is the middle of segment *AC*, then groups (*A*,<=*B*,<=*C*) and (*C*,<=*B*,<=*A*) are considered the same.

Input Specification:
The first line contains a single integer *n* (3<=≤<=*n*<=≤<=3000) — the number of points. 

Next *n* lines contain the points. The *i*-th line contains coordinates of the *i*-th point: two space-separated integers *x**i*,<=*y**i* (<=-<=1000<=≤<=*x**i*,<=*y**i*<=≤<=1000).

It is guaranteed that all given points are different.

Output Specification:
Print the single number — the answer to the problem.

Demo Input:
['3\n1 1\n2 2\n3 3\n', '3\n0 0\n-1 0\n0 1\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Sagheer and Apple Tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sagheer is playing a game with his best friend Soliman. He brought a tree with *n* nodes numbered from 1 to *n* and rooted at node 1. The *i*-th node has *a**i* apples. This tree has a special property: the lengths of all paths from the root to any leaf have the same parity (i.e. all paths have even length or all paths have odd length).

Sagheer and Soliman will take turns to play. Soliman will make the first move. The player who can't make a move loses.

In each move, the current player will pick a single node, take a non-empty subset of apples from it and do one of the following two things:
 1.  eat the apples, if the node is a leaf. 1.  move the apples to one of the children, if the node is non-leaf. 
Before Soliman comes to start playing, Sagheer will make exactly one change to the tree. He will pick two different nodes *u* and *v* and swap the apples of *u* with the apples of *v*.

Can you help Sagheer count the number of ways to make the swap (i.e. to choose *u* and *v*) after which he will win the game if both players play optimally? (*u*,<=*v*) and (*v*,<=*u*) are considered to be the same pair.

Input Specification:
The first line will contain one integer *n* (2<=≤<=*n*<=≤<=105) — the number of nodes in the apple tree.

The second line will contain *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=107) — the number of apples on each node of the tree.

The third line will contain *n*<=-<=1 integers *p*2,<=*p*3,<=...,<=*p**n* (1<=≤<=*p**i*<=≤<=*n*) — the parent of each node of the tree. Node *i* has parent *p**i* (for 2<=≤<=*i*<=≤<=*n*). Node 1 is the root of the tree.

It is guaranteed that the input describes a valid tree, and the lengths of all paths from the root to any leaf will have the same parity.

Output Specification:
On a single line, print the number of different pairs of nodes (*u*,<=*v*), *u*<=≠<=*v* such that if they start playing after swapping the apples of both nodes, Sagheer will win the game. (*u*,<=*v*) and (*v*,<=*u*) are considered to be the same pair.

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

Demo Output:
['1\n', '0\n', '4\n']

Note:
In the first sample, Sagheer can only win if he swapped node 1 with node 3. In this case, both leaves will have 2 apples. If Soliman makes a move in a leaf node, Sagheer can make the same move in the other leaf. If Soliman moved some apples from a root to a leaf, Sagheer will eat those moved apples. Eventually, Soliman will not find a move.

In the second sample, There is no swap that will make Sagheer win the game.

Note that Sagheer must make the swap even if he can win with the initial tree.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Given an array of size n, you have to answer queries of the form :  L R k . For each query, you have to find an element which occurs consecutively in the subarray [L,R] more than or equal to k times. k will always be greater than floor((R-L+1)/2). If no such element exists, print -1.

------ Input ------ 

First line of the input contains 2 space separated N and M, denoting the size of the array and the number of queries. 
The next line contains N space separated integers, where the i-th integer A_{i} denotes the ith element of the array.
Each of the next M lines contains 3 integers space separated integers L, R and k.

------ Output ------ 

Output M lines where each line contains the answer to the i-th query.

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

$1 ≤ N, M ≤ 10^{5}$
$1 ≤ L ≤ R ≤ N$
$floor((R-L+1)/2) < k ≤ R-L+1$    
$0 ≤ A_{i} ≤ 10^{9}$

------ Subtasks ------ 

Subtask #1 (10 points):
$1 ≤ A_{i} ≤ 3$ 
$1 ≤ M ≤ 10$    

Subtask #2 (30 points):
$1 ≤ N ≤ 1000$

Subtask #3 (60 points):
$No other constraints$

----- Sample Input 1 ------ 
5 1
1 2 2 2 2
1 5 3
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
The element 2 occurs more than 3 times in the range [1,5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lyra Belacqua is a very gifted girl. She is one of a very small set of people capable of reading an alethiometer, more commonly known as The Golden Compass. It has one specific use: to tell the truth. The name in fact, is derived from "Aletheia" meaning truth, and "-ometer", meaning "measuring device".

The alethiometer had four needles, out of which the user would direct three of them to lie over symbols on the face of the device to ask a question. The fourth needle then swung into action and pointed to various symbols one after another, thus telling the answer.

For this problem, consider the alethiometer consisting of symbols : digits '0'-'9' and letters 'A'-'Z'. Learned scholars were debating the age of the Universe, and they requested Lyra to find out the age from the alethiometer. Having asked the question, the fourth needle started spouting out symbols, which Lyra quickly recorded. In that long string of characters, she knows that some substring corresponds to the age of the Universe. She also knows that the alethiometer could have wrongly pointed out atmost one digit (0-9) as a letter (A-Z). She then wonders what is the maximum possible age of the Universe.

Given the set of symbols the alethiometer pointed out, help her find the maximum age of the Universe, which could correspond to a substring of the original string with atmost one letter changed.

Note: We consider a substring to be a contiguous part of the string S 

Also, the alethiometer wrongly reports only a letter. All the digits remain as they are.

-----Input-----

Each input consists of a single string S which is what Lyra recorded from the fourth needle's pointing.

-----Output-----

Output one number, the maximum possible answer.

-----Constraints-----
-  1  ≤ |S|  ≤ 1,000
-  S will only contain digits 0-9 and uppercase Latin letters. 

-----Example-----
Input1:
06454

Input2:
C0D3C43F

Output1:
6454

Output2:
3943

-----Explanation-----

In the first example, there is no choice as to what the number can be. It has to be 6,454.

In the second example, there are a total of 41 possible strings (one for the original, and 10 for changing each letter). You can verify that the maximum number as a substring is got by making the string "C0D3943F".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its NU-Tech'15 and participants are pouring in large numbers. Its the first day of the fest and everybody has gathered around the registration desks but are confused on receiving a set of very large numbers on the registration slip. They are later told by the volunteers that in order to get their respective registration numbers, they are supposed to add all the numbers, then add the digits of the sum and the then again add the digits of the new sum and continue till the answer consists of a single digit. That digit is their Registration ID. Help the participants to decipher their NU-Tech Ids.

Input:

First line contains an integer n. n lines follow each containing a "Large Number".

Output:

Print the Registration IDs of the student.

Constraints:

1 ≤ n ≤500

1 ≤ Large Number ≤ 2^1000

SAMPLE INPUT
2
23
99

SAMPLE OUTPUT
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most football fans love it for the goals and excitement. Well, this Kata doesn't.
You are to handle the referee's little notebook and count the players who were sent off for fouls and misbehavior.

The rules:
Two teams, named "A" and "B" have 11 players each; players on each team are numbered from 1 to 11.
Any player may be sent off the field by being given a red card.
A player can also receive a yellow warning card, which is fine, but if he receives another yellow card, he is sent off immediately (no need for a red card in that case). 
If one of the teams has less than 7 players remaining, the game is stopped immediately by the referee, and the team with less than 7 players loses. 

A `card` is a string with the team's letter ('A' or 'B'), player's number, and card's color ('Y' or 'R') - all concatenated and capitalized.
e.g the card `'B7Y'` means player #7 from team B received a yellow card.

The task: Given a list of cards (could be empty), return the number of remaining players on each team at the end of the game (as a tuple of 2 integers, team "A" first).
If the game was terminated by the referee for insufficient number of players, you are to stop the game immediately, and ignore any further possible cards.

Note for the random tests: If a player that has already been sent off receives another card - ignore it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice's school is planning to take some students from her class on a field trip. Alice is really excited about it. There are a total of S students in her class. But due to budget constraints, the school is planning to take only N students for the trip. These students will be picked randomly. And each student has equal chance of being picked.
Alice's friend circle has M students including her. Though she is excited about the field trip, she will enjoy it only if there are atleast K of her friends with her on the trip. She is wondering what are the chances of that happening. She needs your help. Tell her the probability that she will enjoy given that she goes on the trip.

-----Input:-----
First line of input contains a single integer T, the number of test cases.

Each test starts with a single line having 4 space separated integers, S, N, M and K.

-----Output:-----
For each test case, output a line containing the required probability. The answer will be accepted if the relative error is not more than 10-6.

-----Constraints:-----
1 ≤ T ≤ 100
1 ≤ S ≤ 1000
1 ≤ N ≤ S
1 ≤ M ≤ S
0 ≤ K < M

-----Example:-----Input:
3
10 10 5 3
10 4 6 4
3 2 2 1

Output:
1.000000
0.000000
0.500000

-----Explanation:-----Case #1:
Every student will be taken to the trip. So all her 4 friends will accompany her to the trip no matter what. 
Case #2:
Alice wants 4 out of her 5 friends to come along with her which isn't possible because the school is willing to pick only 4 students for the trip.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The employees of the R1 company often spend time together: they watch football, they go camping, they solve contests. So, it's no big deal that sometimes someone pays for someone else.

Today is the day of giving out money rewards. The R1 company CEO will invite employees into his office one by one, rewarding each one for the hard work this month. The CEO knows who owes money to whom. And he also understands that if he invites person x to his office for a reward, and then immediately invite person y, who has lent some money to person x, then they can meet. Of course, in such a situation, the joy of person x from his brand new money reward will be much less. Therefore, the R1 CEO decided to invite the staff in such an order that the described situation will not happen for any pair of employees invited one after another.

However, there are a lot of employees in the company, and the CEO doesn't have a lot of time. Therefore, the task has been assigned to you. Given the debt relationships between all the employees, determine in which order they should be invited to the office of the R1 company CEO, or determine that the described order does not exist.


-----Input-----

The first line contains space-separated integers n and m $(2 \leq n \leq 3 \cdot 10^{4} ; 1 \leq m \leq \operatorname{min}(10^{5}, \frac{n(n - 1)}{2}))$ — the number of employees in R1 and the number of debt relations. Each of the following m lines contains two space-separated integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}), these integers indicate that the person number a_{i} owes money to a person a number b_{i}. Assume that all the employees are numbered from 1 to n.

It is guaranteed that each pair of people p, q is mentioned in the input data at most once. In particular, the input data will not contain pairs p, q and q, p simultaneously.


-----Output-----

Print -1 if the described order does not exist. Otherwise, print the permutation of n distinct integers. The first number should denote the number of the person who goes to the CEO office first, the second number denote the person who goes second and so on.

If there are multiple correct orders, you are allowed to print any of them.


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

Output
2 1 

Input
3 3
1 2
2 3
3 1

Output
2 1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bn] of length n each which he uses to ask people some quite peculiar questions.

To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select k numbers P = [p1, p2, ..., pk] such that 1 ≤ pi ≤ n for 1 ≤ i ≤ k and elements in P are distinct. Sequence P will represent indices of elements that you'll select from both sequences. He calls such a subset P "unfair" if and only if the following conditions are satisfied: 2·(ap1 + ... + apk) is greater than the sum of all elements from sequence A, and 2·(bp1 + ... + bpk) is greater than the sum of all elements from the sequence B. Also, k should be smaller or equal to <image> because it will be to easy to find sequence P if he allowed you to select too many elements!

Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the sequences. 

On the second line there are n space-separated integers a1, ..., an (1 ≤ ai ≤ 109) — elements of sequence A.

On the third line there are also n space-separated integers b1, ..., bn (1 ≤ bi ≤ 109) — elements of sequence B.

Output

On the first line output an integer k which represents the size of the found subset. k should be less or equal to <image>.

On the next line print k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the elements of sequence P. You can print the numbers in any order you want. Elements in sequence P should be distinct.

Example

Input

5
8 7 4 8 3
4 2 5 3 7


Output

3
1 4 5

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