vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
<image>

It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has m seedlings, and the j-th seedling needs at least kj minutes of sunlight to grow up.

Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the i-th of which will appear at time moment (minute) li and disappear at time moment ri. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.

Slastyona wants to grow up her muffins as fast as possible. She has exactly C candies, which is the main currency in Sweetland. 

One can dispel any cloud by paying ci candies. However, in order to comply with Sweetland's Department of Meteorology regulations, one can't dispel more than two clouds.

Slastyona hasn't decided yet which of the m seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.

The seedlings start to grow at time moment 0.

Input

The first line contains two integers n and C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – the number of caramel clouds and the number of candies Slastyona has.

The next n lines contain three integers each: li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109), describing one caramel cloud.

The next line contains single integer m (1 ≤ m ≤ 3·105) – the number of seedlings. Each of the seedlings is described with one integer kj (1 ≤ kj ≤ 109) – the required number of sunny minutes.

Output

For each seedling print one integer – the minimum minute Slastyona can grow it up.

Examples

Input

3 5
1 7 1
1 6 2
1 7 1
3
7
2
5


Output

12
7
10


Input

3 15
1 4 17
2 8 6
4 8 9
2
5
1


Output

8
1


Input

2 10
3 7 9
10 90 10
2
10
100


Output

10
104

Note

Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.

<image>

In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.

<image> <image>

If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Adam is shopping for his girlfriend's birthday. His girlfriend loves pearls, but as he has to attend CODEBLAZE , he gives the responsibility to you. 

There are n pearls in a row. Let's number them with integers from 1 to n from the left to the right. The pearl number i has the type ai.

Let's call a sequence of consecutive pearls a segment. Let's call a segment good if it contains two pearls of the same type.

Split the row of the pearls to the maximal number of good segments. 

INPUT

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of pearls in a row.

The second line contains n integers ai (1 ≤ ai ≤ 10^9) – the type of the i-th pearl.

OUTPUT

On the first line print integer k — the maximal number of segments in a partition of the row.

Each of the next k lines should contain two integers lj, rj (1 ≤ lj ≤ rj ≤ n) — the number of the leftmost and the rightmost pearls in the j-th segment.

If there are no correct partitions of the row print the number "-1".

SAMPLE INPUT
7
1 2 1 3 1 2 1

SAMPLE OUTPUT
2
1 3
4 7

Explanation

there are two segments

segment 1:
1 2 1 : contains two 1s

segment 2:
3 1 2 1 : contains two 1s

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Родители Васи хотят, чтобы он как можно лучше учился. Поэтому если он получает подряд три положительные оценки («четвёрки» или «пятёрки»), они дарят ему подарок. Соответственно, оценки «единица», «двойка» и «тройка» родители Васи считают плохими. Когда Вася получает подряд три хорошие оценки, ему сразу вручают подарок, но для того, чтобы получить ещё один подарок, ему вновь надо получить подряд ещё три хорошие оценки.

Например, если Вася получит подряд пять «четвёрок» оценок, а потом «двойку», то ему дадут только один подарок, а вот если бы «четвёрок» было уже шесть, то подарков было бы два. 

За месяц Вася получил n оценок. Вам предстоит посчитать количество подарков, которые получил Вася. Оценки будут даны именно в том порядке, в котором Вася их получал. 


-----Входные данные-----

В первой строке входных данных следует целое положительное число n (3 ≤ n ≤ 1000) — количество оценок, полученных Васей.

Во второй строке входных данных следует последовательность из n чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 5) — оценки, полученные Васей. Оценки заданы в том порядке, в котором Вася их получил. 


-----Выходные данные-----

Выведите одно целое число — количество подарков, полученных Васей.


-----Примеры-----
Входные данные
6
4 5 4 5 4 4

Выходные данные
2

Входные данные
14
1 5 4 5 2 4 4 5 5 4 3 4 5 5

Выходные данные
3



-----Примечание-----

В первом примере Вася получит два подарка — за первые три положительные оценки и за следующую тройку положительных оценок соответственно.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Based on some criterion, Snuke divided the integers from 1 through 12 into three groups as shown in the figure below.
Given two integers x and y (1 ≤ x < y ≤ 12), determine whether they belong to the same group.

-----Constraints-----
 - x and y are integers.
 - 1 ≤ x < y ≤ 12

-----Input-----
Input is given from Standard Input in the following format:
x y

-----Output-----
If x and y belong to the same group, print Yes; otherwise, print No.

-----Sample Input-----
1 3

-----Sample Output-----
Yes


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Daenerys Targaryen wants to fund her war efforts but she is short of money. Given her financial needs, she was advised by her advisers to visit Braavos and seek funding from the Iron Bank. When she reached Braavos, she came across a member of Faceless Men. The member invited her for a betting game and said that if she wins in this, he will give double the amount she has betted.

The game is a two player turn-based game(i.e. each player gets his turn one by one) and consists of four piles. Each pile has some number of discs. Each player, in his turn, can take any number of discs from at most two piles and has to take at least one disc from any pile. The Faceless Men further refused to tell her the number of discs in each piles but agreed to tell her sum total of discs in all piles and also agreed her to be the first player in the game. He also agreed to play T number of games with her. Being tight on finances, she would like to play only few of the T games. 

Danerys assumed that given N, the total number of discs, any configuration of four distinguishable piles is equally likely. She also assumes that both she and the Faceless men will play optimally for each configuration. She wants to calculate her probability of winning given her assumption is correct(i.e. fraction of games she will win if all possible configurations of four distinguishable piles for a given N are equally likely and both players play optimally). Can you help her to calculate this probability?

Input

The first line contains T, the number of games.

Each test case contains only one integer N denoting the total number of discs.

Output

The output should contain 1 real number per test case denoting the probability of winning of Daenerys given that she is first player in the game described above.

Constraints

1 ≤ T ≤ 10^6

1 ≤ N ≤ 10^5

Note

Output value should be within 1e-6 of the correct value(Output should be printed to exactly six places of decimal precision).

Partial Marks are awarded if some of the test cases pass ( Beware that passing the first test case will not give you any marks).

SAMPLE INPUT
1
1

SAMPLE OUTPUT
1.000000

Explanation

There are four configurations possible for four distinct piles as shown:

Configuration 1: 1 0 0 0

Configuration 2: 0 1 0 0

Configuration 3: 0 0 1 0

Configuration 4: 0 0 0 1

As Daenerys is the first player, she wins in all the above four possible games. Thus her probability of winning is 1.000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2\leq i \leq N ) is Vertex P_i ( P_i < i ). There is a number, 0 or 1, written on each vertex. The number written on Vertex i is V_i.

Snuke would like to arrange the vertices of this tree in a horizontal row. Here, for every vertex, there should be no ancestor of that vertex to the right of that vertex.

After arranging the vertices, let X be the sequence obtained by reading the numbers written on the vertices from left to right in the arrangement. Snuke would like to minimize the inversion number of X. Find the minimum possible inversion number of X.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq P_i < i ( 2 \leq i \leq N )
* 0 \leq V_i \leq 1 ( 1 \leq i \leq N )
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
P_2 P_3 ... P_N
V_1 V_2 ... V_N


Output

Print the minimum possible inversion number of X.

Examples

Input

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


Output

4


Input

1

0


Output

0


Input

15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0


Output

31

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A car travels from a starting position to a destination which is target miles east of the starting position.
Along the way, there are gas stations.  Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it.  It uses 1 liter of gas per 1 mile that it drives.
When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
What is the least number of refueling stops the car must make in order to reach its destination?  If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there.  If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
 

Example 1:
Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.


Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).


Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

 
Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark. 

Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.


-----Input-----

The first line of the input contains one integer, n (1 ≤ n ≤ 100 000). The next line contains n space separated integers given to Wet Shark. Each of these integers is in range from 1 to 10^9, inclusive. 


-----Output-----

Print the maximum possible even sum that can be obtained if we use some of the given integers. 


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

Output
6
Input
5
999999999 999999999 999999999 999999999 999999999

Output
3999999996


-----Note-----

In the first sample, we can simply take all three integers for a total sum of 6.

In the second sample Wet Shark should take any four out of five integers 999 999 999.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasily has a number a, which he wants to turn into a number b. For this purpose, he can do two types of operations:  multiply the current number by 2 (that is, replace the number x by 2·x);  append the digit 1 to the right of current number (that is, replace the number x by 10·x + 1). 

You need to help Vasily to transform the number a into the number b using only the operations described above, or find that it is impossible.

Note that in this task you are not required to minimize the number of operations. It suffices to find any way to transform a into b.


-----Input-----

The first line contains two positive integers a and b (1 ≤ a < b ≤ 10^9) — the number which Vasily has and the number he wants to have.


-----Output-----

If there is no way to get b from a, print "NO" (without quotes).

Otherwise print three lines. On the first line print "YES" (without quotes). The second line should contain single integer k — the length of the transformation sequence. On the third line print the sequence of transformations x_1, x_2, ..., x_{k}, where:  x_1 should be equal to a,  x_{k} should be equal to b,  x_{i} should be obtained from x_{i} - 1 using any of two described operations (1 < i ≤ k). 

If there are multiple answers, print any of them.


-----Examples-----
Input
2 162

Output
YES
5
2 4 8 81 162 

Input
4 42

Output
NO

Input
100 40021

Output
YES
5
100 200 2001 4002 40021

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One beautiful day Vasily the bear painted 2m circles of the same radius R on a coordinate plane. Circles with numbers from 1 to m had centers at points (2R - R, 0), (4R - R, 0), ..., (2Rm - R, 0), respectively. Circles with numbers from m + 1 to 2m had centers at points (2R - R, 2R), (4R - R, 2R), ..., (2Rm - R, 2R), respectively. 

Naturally, the bear painted the circles for a simple experiment with a fly. The experiment continued for m2 days. Each day of the experiment got its own unique number from 0 to m2 - 1, inclusive. 

On the day number i the following things happened: 

  1. The fly arrived at the coordinate plane at the center of the circle with number <image> (<image> is the result of dividing number x by number y, rounded down to an integer). 
  2. The fly went along the coordinate plane to the center of the circle number <image> (<image> is the remainder after dividing number x by number y). The bear noticed that the fly went from the center of circle v to the center of circle u along the shortest path with all points lying on the border or inside at least one of the 2m circles. After the fly reached the center of circle u, it flew away in an unknown direction. 



Help Vasily, count the average distance the fly went along the coordinate plane during each of these m2 days.

Input

The first line contains two integers m, R (1 ≤ m ≤ 105, 1 ≤ R ≤ 10).

Output

In a single line print a single real number — the answer to the problem. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6.

Examples

Input

1 1


Output

2.0000000000


Input

2 2


Output

5.4142135624

Note

<image>

Figure to the second sample

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tired of the overpopulated world, Miu - The introverted cat visits a new continent in search for a new house.  
There are $N$ houses lying on the X-axis.

Their positions are given by $X$$i$ , where $i$ refers to the $i$th house. ( $1 <= i <= N$ )

Each of these positions are pairwise distinct 
Miu is supposed to choose one of these houses for herself.

Miu defines a term - The Distance of Peace,  as the minimum distance from her house to any other house.  
Miu wonders what is maximum Distance of Peace she can obtain. Can you help her?

-----Input:-----
- The first line of the input consists of a single integer $T$, denoting the number of test cases  
- The first line of each test case consists of a single integer $N$ 
- The second line of each test case consists of $N$ space-separated integers
$X$$1$ $X$$2$ $X$$3$ … $X$$N$

-----Output:-----
- For each test case print the answer in a single line, the maximum Distance of Peace Miu can obtain

-----Constraints-----
- 1 <= $T$ <= 100  
- 2 <= $N$ <= 105 
- -109 <= $X$$i$ <= 109 
- Sum of $N$ over all test cases does not exceed 106 

-----Subtasks-----
Subtask #1 (30 points): 
- $N$ <= 103 
Subtask #2 (70 points): 
- Original Constraints

-----Sample Input:-----
2

6

7 -1 2 13 -5 15

4

6 10 3 12  

-----Sample Output:-----
5

3  

-----EXPLANATION:-----
Test Case 1:

The $1$st house has the maximum Distance of Peace, which is from the $3$rd house:
$| 7 - 2 | = 5$

Hence, the answer is $5$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Finally it is a day when Arthur has enough money for buying an apartment. He found a great option close to the center of the city with a nice price.

Plan of the apartment found by Arthur looks like a rectangle *n*<=×<=*m* consisting of squares of size 1<=×<=1. Each of those squares contains either a wall (such square is denoted by a symbol "*" on the plan) or a free space (such square is denoted on the plan by a symbol ".").

Room in an apartment is a maximal connected area consisting of free squares. Squares are considered adjacent if they share a common side.

The old Arthur dream is to live in an apartment where all rooms are rectangles. He asks you to calculate minimum number of walls you need to remove in order to achieve this goal. After removing a wall from a square it becomes a free square. While removing the walls it is possible that some rooms unite into a single one.

Input Specification:
The first line of the input contains two integers *n*,<=*m* (1<=≤<=*n*,<=*m*<=≤<=2000) denoting the size of the Arthur apartments.

Following *n* lines each contain *m* symbols — the plan of the apartment.

If the cell is denoted by a symbol "*" then it contains a wall.

If the cell is denoted by a symbol "." then it this cell is free from walls and also this cell is contained in some of the rooms.

Output Specification:
Output *n* rows each consisting of *m* symbols that show how the Arthur apartment plan should look like after deleting the minimum number of walls in order to make each room (maximum connected area free from walls) be a rectangle. 

If there are several possible answers, output any of them.

Demo Input:
['5 5\n.*.*.\n*****\n.*.*.\n*****\n.*.*.\n', '6 7\n***.*.*\n..*.*.*\n*.*.*.*\n*.*.*.*\n..*...*\n*******\n', '4 5\n.....\n.....\n..***\n..*..\n']

Demo Output:
['.*.*.\n*****\n.*.*.\n*****\n.*.*.\n', '***...*\n..*...*\n..*...*\n..*...*\n..*...*\n*******\n', '.....\n.....\n.....\n.....\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen. Initially the children stood in the order they entered the canteen. However, after a while the boys started feeling awkward for standing in front of the girls in the queue and they started letting the girls move forward each second. 

Let's describe the process more precisely. Let's say that the positions in the queue are sequentially numbered by integers from 1 to n, at that the person in the position number 1 is served first. Then, if at time x a boy stands on the i-th position and a girl stands on the (i + 1)-th position, then at time x + 1 the i-th position will have a girl and the (i + 1)-th position will have a boy. The time is given in seconds.

You've got the initial position of the children, at the initial moment of time. Determine the way the queue is going to look after t seconds.


-----Input-----

The first line contains two integers n and t (1 ≤ n, t ≤ 50), which represent the number of children in the queue and the time after which the queue will transform into the arrangement you need to find. 

The next line contains string s, which represents the schoolchildren's initial arrangement. If the i-th position in the queue contains a boy, then the i-th character of string s equals "B", otherwise the i-th character equals "G".


-----Output-----

Print string a, which describes the arrangement after t seconds. If the i-th position has a boy after the needed time, then the i-th character a must equal "B", otherwise it must equal "G".


-----Examples-----
Input
5 1
BGGBG

Output
GBGGB

Input
5 2
BGGBG

Output
GGBGB

Input
4 1
GGGB

Output
GGGB

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 mathematical string and your task will be to remove all braces as follows:

```Haskell
solve("x-(y+z)") = "x-y-z"
solve("x-(y-z)") = "x-y+z"
solve("u-(v-w-(x+y))-z") = "u-v+w+x+y-z"
solve("x-(-y-z)") = "x+y+z"
```

There are no spaces in the expression. Only two operators are given: `"+" or "-"`. 

More examples in test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The doorman Bruno at the popular night club Heaven is having a hard time fulfilling his duties. He was told by the owner that when the club is full, the number of women and men let into the club should be roughly the same. When the night club opens, people wanting to enter the club are already lined up in a queue, and Bruno can only let them in one-by-one. He lets them in more-or-less in the order they are lined up. He can however decide to let the second person in the queue cut the line and slip into the club before the person in front. This will no doubt upset the person first in line, especially when this happens multiple times, but Bruno is quite a big guy and is capable of handling troublemakers.

Unfortunately though, he is not that strong on mental calculations under these circumstances. He finds keeping track of the difference of the number of women and number of men let into the club a challenging task. As soon as the absolute difference gets too big, he loses track of his counting and must declare to the party people remaining in the queue that the club is full.

-----Input-----
The first line of input contains a positive integer $X<100$ describing the largest absolute difference between the number of women and number of men let into the club that Bruno can handle.

The second line contains a string consisting solely of the characters ’W’ and ’M’ of length at most $100$, describing the genders of the people in the queue, in order of their arrrival. The leftmost character of the string is the gender of the person first in line.

You may assume that the club is large enough to hold all the people in the queue.

-----Output-----
The maximum number of people Bruno can let into the club without losing track of his counting.

-----Examples-----
Sample Input:
1
MWWMWMMWM
Sample Output:
9

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