vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Peter likes to travel by train. He likes it so much that on the train he falls asleep. 

Once in summer Peter was going by train from city A to city B, and as usual, was sleeping. Then he woke up, started to look through the window and noticed that every railway station has a flag of a particular colour.

The boy started to memorize the order of the flags' colours that he had seen. But soon he fell asleep again. Unfortunately, he didn't sleep long, he woke up and went on memorizing the colours. Then he fell asleep again, and that time he slept till the end of the journey.

At the station he told his parents about what he was doing, and wrote two sequences of the colours that he had seen before and after his sleep, respectively.

Peter's parents know that their son likes to fantasize. They give you the list of the flags' colours at the stations that the train passes sequentially on the way from A to B, and ask you to find out if Peter could see those sequences on the way from A to B, or from B to A. Remember, please, that Peter had two periods of wakefulness.

Peter's parents put lowercase Latin letters for colours. The same letter stands for the same colour, different letters — for different colours.

Input

The input data contains three lines. The first line contains a non-empty string, whose length does not exceed 105, the string consists of lowercase Latin letters — the flags' colours at the stations on the way from A to B. On the way from B to A the train passes the same stations, but in reverse order. 

The second line contains the sequence, written by Peter during the first period of wakefulness. The third line contains the sequence, written during the second period of wakefulness. Both sequences are non-empty, consist of lowercase Latin letters, and the length of each does not exceed 100 letters. Each of the sequences is written in chronological order. 

Output

Output one of the four words without inverted commas: 

  * «forward» — if Peter could see such sequences only on the way from A to B; 
  * «backward» — if Peter could see such sequences on the way from B to A; 
  * «both» — if Peter could see such sequences both on the way from A to B, and on the way from B to A; 
  * «fantasy» — if Peter could not see such sequences. 

Examples

Input

atob
a
b


Output

forward


Input

aaacaaa
aca
aa


Output

both

Note

It is assumed that the train moves all the time, so one flag cannot be seen twice. There are no flags at stations A and B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two numbers A and B.

In one operation, Chef can choose either A or B and multiply it by 2.

Determine whether he can make both A and B equal after any number (possibly, zero) of moves.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two space-separated integers A and B.

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

For each test case, output YES if Chef can make both numbers equal, NO otherwise.

Note that the checker is case-insensitive i.e. YES, Yes, yes, yES are all considered same.

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

$1 ≤ T ≤ 2500$
$1 ≤ A, B ≤ 50$

----- Sample Input 1 ------ 
4
5 20
6 6
12 2
50 20

----- Sample Output 1 ------ 
YES
YES
NO
NO

----- explanation 1 ------ 
Test case $1$: Chef can multiply $A$ by $2$ twice and both $A$ and $B$ will become $20$.

Test case $2$: Both numbers are already equal.

Test case $3$: It can be shown that $A$ and $B$ cannot be made equal.

Test case $4$: It can be shown that $A$ and $B$ cannot be made equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Petya is preparing for the first contact with aliens. He knows that alien spaceships have shapes of non-degenerate triangles and there will be exactly 4 ships. Landing platform for a ship can be made of 3 special columns located at some points of a Cartesian plane such that these 3 points form a triangle equal to the ship with respect to rotations, translations (parallel shifts along some vector) and reflections (symmetries along the edges). The ships can overlap after the landing.

Each column can be used to land more than one ship, for example, if there are two equal ships, we don't need to build 6 columns to land both ships, 3 will be enough. Petya wants to know what minimum number of columns will be enough to land all ships. 

Input

Each of 4 lines will contain 6 integers x1 y1 x2 y2 x3 y3 (0 ≤ x1, y1, x2, y2, x3, y3 ≤ 20), representing 3 points that describe the shape of each of 4 ships. It is guaranteed that 3 points in each line will represent a non-degenerate triangle.

Output

First line should contain minimum number of columns enough to land all spaceships.

Examples

Input

0 0 1 0 1 2
0 0 0 2 2 2
0 0 3 0 1 2
0 0 3 0 2 2


Output

4


Input

0 0 0 1 1 1
0 0 0 2 2 2
0 0 0 5 5 5
0 0 0 17 17 17


Output

9

Note

In the first test case columns can be put in these points: (0, 0), (1, 0), (3, 0), (1, 2). Note that the second ship can land using last 3 columns.

In the second test case following points can be chosen: (0, 0), (0, 1), (1, 0), (0, 2), (2, 0), (0, 5), (5, 0), (0, 17), (17, 0). It is impossible to use less than 9 columns.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John loves prime numbers. One day he was playing a game "primcia" with his wife alicia. The game is as follows, John write a number N on a table.

The number is of the form:

N =  (P1^A1) * (P2^A2) * .............. * (Px^Ax).

Where Pi are prime numbers and Ai are its corresponding powers.

Now, he asks Alicia to find the sum of all the numbers which are less than or equal to N and also contain all prime numbers which N contains in its prime factorization. For small numbers, Alicia can solve easily but it becomes too hard for large numbers. Help her to answer the query of john.

Input:
First Line contains T test cases. Each test case contains 3 lines, 1st line contain X numbers of primes in N, 2nd line contains X distinct prime numbers and 3rd line contain X powers. Each power Ai is power of Pi.

Output:
Output the Answer Modulo 10^9 +7.

Constraints:
1 ≤ T ≤ 10
1 ≤ X ≤ 100000
0 < Pi ≤1000000
1 ≤  Ai ≤ 1000000000

SAMPLE INPUT
1
3
2 3 5
2 1 1

SAMPLE OUTPUT
90

Explanation

In given test case, The N will be 60.
So,  Numbers less than and equal to 60 having same prime numbers in its factorization are 60, 30, and So, sum=90.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently *n* students from city S moved to city P to attend a programming camp.

They moved there by train. In the evening, all students in the train decided that they want to drink some tea. Of course, no two people can use the same teapot simultaneously, so the students had to form a queue to get their tea.

*i*-th student comes to the end of the queue at the beginning of *l**i*-th second. If there are multiple students coming to the queue in the same moment, then the student with greater index comes after the student with lesser index. Students in the queue behave as follows: if there is nobody in the queue before the student, then he uses the teapot for exactly one second and leaves the queue with his tea; otherwise the student waits for the people before him to get their tea. If at the beginning of *r**i*-th second student *i* still cannot get his tea (there is someone before him in the queue), then he leaves the queue without getting any tea. 

For each student determine the second he will use the teapot and get his tea (if he actually gets it).

Input Specification:
The first line contains one integer *t* — the number of test cases to solve (1<=≤<=*t*<=≤<=1000).

Then *t* test cases follow. The first line of each test case contains one integer *n* (1<=≤<=*n*<=≤<=1000) — the number of students.

Then *n* lines follow. Each line contains two integer *l**i*, *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=5000) — the second *i*-th student comes to the end of the queue, and the second he leaves the queue if he still cannot get his tea.

It is guaranteed that for every  condition *l**i*<=-<=1<=≤<=*l**i* holds.

The sum of *n* over all test cases doesn't exceed 1000.

Note that in hacks you have to set *t*<==<=1.

Output Specification:
For each test case print *n* integers. *i*-th of them must be equal to the second when *i*-th student gets his tea, or 0 if he leaves without tea.

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

Demo Output:
['1 2 \n1 0 2 \n']

Note:
The example contains 2 tests:
 1.  During 1-st second, students 1 and 2 come to the queue, and student 1 gets his tea. Student 2 gets his tea during 2-nd second. 1.  During 1-st second, students 1 and 2 come to the queue, student 1 gets his tea, and student 2 leaves without tea. During 2-nd second, student 3 comes and gets his tea.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera has array *a*, consisting of *n* integers *a*0,<=*a*1,<=...,<=*a**n*<=-<=1, and function *f*(*x*), taking an integer from 0 to 2*n*<=-<=1 as its single argument. Value *f*(*x*) is calculated by formula , where value *bit*(*i*) equals one if the binary representation of number *x* contains a 1 on the *i*-th position, and zero otherwise.

For example, if *n*<==<=4 and *x*<==<=11 (11<==<=20<=+<=21<=+<=23), then *f*(*x*)<==<=*a*0<=+<=*a*1<=+<=*a*3.

Help Valera find the maximum of function *f*(*x*) among all *x*, for which an inequality holds: 0<=≤<=*x*<=≤<=*m*.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of array elements. The next line contains *n* space-separated integers *a*0,<=*a*1,<=...,<=*a**n*<=-<=1 (0<=≤<=*a**i*<=≤<=104) — elements of array *a*.

The third line contains a sequence of digits zero and one without spaces *s*0*s*1... *s**n*<=-<=1 — the binary representation of number *m*. Number *m* equals .

Output Specification:
Print a single integer — the maximum value of function *f*(*x*) for all .

Demo Input:
['2\n3 8\n10\n', '5\n17 0 10 2 1\n11010\n']

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

Note:
In the first test case *m* = 2<sup class="upper-index">0</sup> = 1, *f*(0) = 0, *f*(1) = *a*<sub class="lower-index">0</sub> = 3.

In the second sample *m* = 2<sup class="upper-index">0</sup> + 2<sup class="upper-index">1</sup> + 2<sup class="upper-index">3</sup> = 11, the maximum value of function equals *f*(5) = *a*<sub class="lower-index">0</sub> + *a*<sub class="lower-index">2</sub> = 17 + 10 = 27.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Mr. Chanek wants to buy a flamingo to accompany his chickens on his farm. Before going to the pet shop, Mr. Chanek stops at an animal festival to have fun. It turns out there is a carnival game with a flamingo as the prize.

There are N mysterious cages, which are numbered from 1 to N. Cage i has A_i (0 ≤ A_i ≤ 10^3) flamingoes inside (1 ≤ i ≤ N). However, the game master keeps the number of flamingoes inside a secret. To win the flamingo, Mr. Chanek must guess the number of flamingoes in each cage.

Coincidentally, Mr. Chanek has N coins. Each coin can be used to ask once, what is the total number of flamingoes inside cages numbered L to R inclusive? With L < R.

Input

Use standard input to read the responses of your questions.

Initially, the judge will give an integer N (3 ≤ N ≤ 10^3), the number of cages, and the number of coins Mr. Chanek has.

For each of your questions, the jury will give an integer that denotes the number of flamingoes from cage L to R inclusive.

If your program does not guess the flamingoes or ask other questions, you will get "Wrong Answer". Of course, if your program asks more questions than the allowed number, your program will get "Wrong Answer".

Output

To ask questions, your program must use standard output.

Then, you can ask at most N questions. Questions are asked in the format "? L R", (1 ≤ L < R ≤ N). 

To guess the flamingoes, print a line that starts with "!" followed by N integers where the i-th integer denotes the number of flamingo in cage i. After answering, your program must terminate or will receive the "idle limit exceeded" verdict. You can only guess the flamingoes once.

Examples

Input

6
 
5
 
15
 
10
 

Output

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

Note

In the sample input, the correct flamingoes amount is [1, 4, 4, 6, 7, 8].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an infinite array with two rows, the numbers in the top row are denoted

`. . . , A[−2], A[−1], A[0], A[1], A[2], . . .`

and the numbers in the bottom row are denoted

`. . . , B[−2], B[−1], B[0], B[1], B[2], . . .`

For each integer `k`, the entry `A[k]` is directly above
the entry `B[k]` in the array, as shown:


...|A[-2]|A[-1]|A[0]|A[1]|A[2]|...
...|B[-2]|B[-1]|B[0]|B[1]|B[2]|...



For each integer `k`, `A[k]` is the average of the entry to its left, the entry to its right,
and the entry below it; similarly, each entry `B[k]` is the average of the entry to its
left, the entry to its right, and the entry above it.


Given `A[0], A[1], A[2] and A[3]`, determine the value of `A[n]`. (Where range of n is -1000 Inputs and Outputs in BigInt!** 

Adapted from 2018 Euclid Mathematics Contest.
https://www.cemc.uwaterloo.ca/contests/past_contests/2018/2018EuclidContest.pdf

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N cities in a two-dimensional plane. The coordinates of the i-th city is (x_i, y_i). Initially, the amount of water stored in the i-th city is a_i liters.

Snuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries l liters of water from the s-th city to the t-th city, only max(l-d_{s,t}, 0) liters of water remains when he arrives at the destination. Here d_{s,t} denotes the (Euclidean) distance between the s-th city and the t-th city. He can perform arbitrary number of operations of this type.

Snuke wants to maximize the minimum amount of water among the N cities. Find the maximum X such that he can distribute at least X liters of water to each city.

Constraints

* 1 ≤ N ≤ 15
* 0 ≤ x_i, y_i, a_i ≤ 10^9
* All values in the input are integers.
* No two cities are at the same position.

Input

The input is given from Standard Input in the following format:


N
x_1 y_1 a_1
:
x_N y_N a_N


Output

Print the maximum of the minimum amount of water among the N cities. The absolute error or the relative error must be at most 10^{-9}.

Examples

Input

3
0 0 10
2 0 5
0 5 8


Output

6.500000000000


Input

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447


Output

434666178.237122833729

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ksusha is a vigorous mathematician. She is keen on absolutely incredible mathematical riddles. 

Today Ksusha came across a convex polygon of non-zero area. She is now wondering: if she chooses a pair of distinct points uniformly among all integer points (points with integer coordinates) inside or on the border of the polygon and then draws a square with two opposite vertices lying in the chosen points, what will the expectation of this square's area be?

A pair of distinct points is chosen uniformly among all pairs of distinct points, located inside or on the border of the polygon. Pairs of points p, q (p ≠ q) and q, p are considered the same.

Help Ksusha! Count the required expectation.

Input

The first line contains integer n (3 ≤ n ≤ 105) — the number of vertices of Ksusha's convex polygon. Next n lines contain the coordinates of the polygon vertices in clockwise or counterclockwise order. The i-th line contains integers xi, yi (|xi|, |yi| ≤ 106) — the coordinates of the vertex that goes i-th in that order.

Output

Print a single real number — the required expected area. 

The answer will be considered correct if its absolute and relative error doesn't exceed 10 - 6.

Examples

Input

3
0 0
5 5
5 0


Output

4.6666666667


Input

4
-1 3
4 5
6 2
3 -5


Output

8.1583333333


Input

3
17 136
859 937
16 641


Output

66811.3704155169

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the computer world, a train of the length N can be represented as an array A of the same length.
Such an array A contains integer elements between 1 and K, inclusive.
Each element in A represents the quality of one carriage.
Note that there are exactly K^N distinct trains.

Mike loves to travel and today he is going to do it with his friends.
They want to occupy exactly L consecutive carriages.
Of course, they want chosen L carriages to be of equal quality.

Someone saw a train and thus knows an array A.
He said that there are exactly T ways for them to choose L consecutive carriages of equal quality.
Now, Mike wants to know how many trains satisfy this description.
Your task is to count them modulo 10^9+7.

Input format
The only line of the input contains four space-separated integers N, L, T and K.

Output format
Find the number of trains satisfying the given description.
Print it modulo 10^9+7 in a single line.

Constraints
1 ≤ L ≤ N ≤ 3333
0 ≤ T ≤ N - L + 1
1 ≤ K ≤ 10^9

SAMPLE INPUT
5 2 1 2


SAMPLE OUTPUT
8


Explanation

For the sample test the only possible arrays are: 
{1, 1, 2, 1, 2}, 
{1, 2, 1, 1, 2}, 
{1, 2, 1, 2, 2}, 
{1, 2, 2, 1, 2}, 
{2, 1, 1, 2, 1}, 
{2, 1, 2, 1, 1}, 
{2, 1, 2, 2, 1}, 
{2, 2, 1, 2, 1}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string of characters, or numbers. Find the minimum number of characters to be inserted into the string in order to obtain a palindrome. 
A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed. 

For example, the string abcbd can be transformed into a palindrome ("dabcbad" or "adbcbda"). However, inserting fewer than 2 characters will not produce a palindrome.

Input Format:

First line contains test cases and second line contains an integer 'n' specifying the length of the string, where 3 ≤ n ≤ 20
Second line contains a string of length n. 

Note:

Upper-case and lower-case characters are considered as different. Elements of the string are either English alphabets or numerals.

Output Format:

One line containing the minimum number of insertions required to make the string a palindrome

SAMPLE INPUT
2
5
nitin
7
aabbaab

SAMPLE OUTPUT
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oliver and Nova are true lovers. Inspite of knowing that Nova will die Oliver married her at the lake where they met. But they had a conflict about even and odd numbers. Nova likes the odd numbers and Oliver prefers even. One day they went to a fair where Oliver bought some square shaped marshmallows and Nova bought some round shaped. Then they decided to play a game. They will pick a natural number N . Nova will sum up the odd numbers from 1 to N and and she will notedown LCM of R(R is defined in the picture) and the sum she calculated before. And Oliver will sum up the even numbers from 1 to N and and he will notedown LCM of S(S is defined in the picture) and the sum he calculated before. You must use the ceil value of R and S.

Now  whose LCM is strictly greater than the other will win.If both of their LCM is equal Nova will win because Oliver is afraid of Nova.
$N.B.$ define the value of pi with $acos(-1)$.
$N.B.$ Sum of all odd number and sum of all even number will not exceed 10^18. 

-----Input:-----
The first line contains an integer $T$  — the number of test cases in the input. Next, T test cases are given, one per line.
Each test case is a positive integer $N$  . 

-----Output:-----
Print T answers to the test cases.
In each test cases,
If Oliver wins the game, print "Nova's gonna kill me" (without quotes) .
If Nova wins the game, print "YESS(sunglass emo)" (without quotes) .

-----Constraints-----
- $1 \leq T \leq 2000$
- $1 \leq N \leq 1845271$

-----Sample Input:-----
1
111

-----Sample Output:-----
YESS(sunglass emo)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.

We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Constraints

* 1 ≤ K ≤ N ≤ 200000
* 1 ≤ p_i ≤ 1000
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
p_1 ... p_N


Output

Print the maximum possible value of the expected value of the sum of the numbers shown.

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

Examples

Input

5 3
1 2 2 4 5


Output

7.000000000000


Input

4 1
6 6 6 6


Output

3.500000000000


Input

10 4
17 13 13 12 15 20 10 13 17 11


Output

32.000000000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahubina is tired of so many complicated languages, so she decided to invent a new, simple language. She already made a dictionary consisting of *n* 3-words. A 3-word is a sequence of exactly 3 lowercase letters of the first 24 letters of the English alphabet (*a* to *x*). She decided that some of the letters are vowels, and all the others are consonants. The whole language is based on a simple rule: any word that contains at least one vowel is correct.

Iahubina forgot which letters are the vowels, and wants to find some possible correct sets of vowels. She asks Iahub questions. In each question, she will give Iahub a set of letters considered vowels (in this question). For each question she wants to know how many words of the dictionary are correct, considering the given set of vowels.

Iahubina wants to know the *xor* of the squared answers to all the possible questions. There are 224 different questions, they are all subsets of the set of the first 24 letters of the English alphabet. Help Iahub find that number.

Input Specification:
The first line contains one integer, *n* (1<=≤<=*n*<=≤<=104). Each of the next *n* lines contains a 3-word consisting of 3 lowercase letters. There will be no two identical 3-words.

Output Specification:
Print one number, the *xor* of the squared answers to the queries.

Demo Input:
['5\nabc\naaa\nada\nbcd\ndef\n']

Demo Output:
['0\n']

Note:
none

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