vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Easy and hard versions are actually different problems, so we advise you to read both statements carefully.

You are given a weighted rooted tree, vertex 1 is the root of this tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex v is the last different from v vertex on the path from the root to the vertex v. Children of vertex v are all vertices for which v is the parent. A vertex is a leaf if it has no children. The weighted tree is such a tree that each edge of this tree has some weight.

The weight of the path is the sum of edges weights on this path. The weight of the path from the vertex to itself is 0.

You can make a sequence of zero or more moves. On each move, you select an edge and divide its weight by 2 rounding down. More formally, during one move, you choose some edge i and divide its weight by 2 rounding down (w_i := \left⌊(w_i)/(2)\right⌋).

Your task is to find the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S. In other words, if w(i, j) is the weight of the path from the vertex i to the vertex j, then you have to make ∑_{v ∈ leaves} w(root, v) ≤ S, where leaves is the list of all leaves.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and S (2 ≤ n ≤ 10^5; 1 ≤ S ≤ 10^{16}) — the number of vertices in the tree and the maximum possible sum of weights you have to obtain. The next n-1 lines describe edges of the tree. The edge i is described as three integers v_i, u_i and w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^6), where v_i and u_i are vertices the edge i connects and w_i is the weight of this edge.

It is guaranteed that the sum of n does not exceed 10^5 (∑ n ≤ 10^5).

Output

For each test case, print the answer: the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S.

Example

Input


3
3 20
2 1 8
3 1 7
5 50
1 3 100
1 5 10
2 3 123
5 4 55
2 100
1 2 409


Output


0
8
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
The square (i, j) has two numbers A_{ij} and B_{ij} written on it.
First, for each square, Takahashi paints one of the written numbers red and the other blue.
Then, he travels from the square (1, 1) to the square (H, W). In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1). He must not leave the grid.
Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W).
Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.
Find the minimum unbalancedness possible.

-----Constraints-----
 - 2 \leq H \leq 80
 - 2 \leq W \leq 80
 - 0 \leq A_{ij} \leq 80
 - 0 \leq B_{ij} \leq 80
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}

-----Output-----
Print the minimum unbalancedness possible.

-----Sample Input-----
2 2
1 2
3 4
3 4
2 1

-----Sample Output-----
0

By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7, respectively, for the unbalancedness of 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jerry is playing a rather plain computer game. The game is played in the 2D Cartesian plane. At the beginning of the game there are some points in the plane. 
The objective of the game is to make a single shot that will eliminate as many of these points as possible. When Jerry takes the shot, it will eliminate all points that (at that moment) lie on the x-axis and also all points that lie on the y-axis.
Before Jerry takes the shot, he may perform a sequence of zero or more actions. Each action can be of either of the following two types:
He may translate all points by any vector (the same for all points). In other words, he may shift all points in the same direction by the same distance.
He may rotate all points around the origin by any angle (the same for all points).
Note that it is possible that after an action some points will have non-integer coordinates.
Find and return the maximum number of points Jerry can eliminate in one shot.
First line contains number of test cases-
In every test first line will contain n(number of points) 
the second line will contain n space separated characters denoting x coordinate of the point.
the third line will contain n space separated characters denoting y coordinate of the point.

Constraints-
1 ≤ T ≤ 20
1 ≤ n ≤ 50
-1,000,000 ≤ x[i] , y[i] ≤ 1,000,000

SAMPLE INPUT
2
2
0 5
0 5
5
0 -1 1 1 -1
0 -1 -1 1 1

SAMPLE OUTPUT
2
5

Explanation

First Test Case-
At the beginning of the game there are two points: one at (0, 0) and the other at (5, 5). Jerry can shift both points by 5 in the negative y direction. This will move the points to (0, -5) and (5, 0). Then Jerry can take the shot and eliminate both points. Therefore, the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been appointed as the designer for your school's computer network.
In total, there are N computers in the class, and M computer-to-computer connections need to be made. Also, there are three mandatory conditions the design should fulfill.
The first requirement is that any computer in the network should be able to communicate with any other computer through the connections, possibly, through some other computers.
Network attacks are possible, so the second requirement is that even if any one computer from the network gets disabled so that the rest of the computers are unable to communicate with it, the rest of the computers can still communicate with each other. In other words, the first requirement still holds for any subset of (N-1) computers.
The third requirement is that there shouldn't be any irrelevant connections in the network. We will call a connection irrelevant if and only if after its' removal, the above two requirements are still held.
Given N, M, please build a network with N computers and M connections, or state that it is impossible.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a pair of space-separated integers N and M denoting the number of computers and the number of connections.

-----Output-----
Output T blocks.
If it is impossible to construct a network with the given parameters for the corresponding test case, output just -1 -1. Otherwise, output M lines, each of which contains a space-separated pairs of integers denoting the IDs of the computers that should be connected. Note that multiple connections between any pair of computers and connections connecting a computer to itself are implicitly not allowed due to the third requirement.

-----Constraints-----

- 1 ≤ T ≤ 1000
- 1 ≤ M ≤ N * (N - 1) / 2
- 1 ≤ Sum of all N ≤ 1000
- Subtask 1 (21 point): 1 ≤ N ≤ 4
- Subtask 2 (79 points): 1 ≤ N ≤ 100

-----Example-----
Input:2
10 1
5 5

Output:-1 -1
1 2
2 3
3 4
4 5
5 1

-----Explanation-----
Example case 1. There are not enough connections even to satisfy the first requirement.
Example case 2. The obtained network satisfies all the requirements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let be `n` an integer prime with `10` e.g. `7`. 

`1/7 = 0.142857 142857 142857 ...`.

We see that the decimal part has a cycle: `142857`. The length of this cycle is `6`. In the same way:

`1/11 = 0.09 09 09 ...`. Cycle length is `2`.

# Task

Given an integer n (n > 1), the function cycle(n) returns the length of the cycle if n and 10 are coprimes, otherwise returns -1.

# Examples:
```
cycle(5) = -1
cycle(13) = 6 -> 0.076923 076923 0769
cycle(21) = 6 -> 0.047619 047619 0476
cycle(27) = 3 -> 0.037 037 037 037 0370
cycle(33) = 2 -> 0.03 03 03 03 03 03 03 03
cycle(37) = 3 -> 0.027 027 027 027 027 0
cycle(94) = -1 

cycle(22) = -1 since 1/22 ~ 0.0 45 45 45 45 ...
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let f(A, B) be the exclusive OR of A, A+1, ..., B. Find f(A, B).
What is exclusive OR?
The bitwise exclusive OR of integers c_1, c_2, ..., c_n (let us call it y) is defined as follows:
 - When y is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if, the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place, is odd, and 0 if that count is even.
For example, the exclusive OR of 3 and 5 is 6. (When written in base two: the exclusive OR of 011 and 101 is 110.)

-----Constraints-----
 - All values in input are integers.
 - 0 \leq A \leq B \leq 10^{12}

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Compute f(A, B) and print it.

-----Sample Input-----
2 4

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

2, 3, 4 are 010, 011, 100 in base two, respectively.
The exclusive OR of these is 101, which is 5 in base ten.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon loves summing up something for no reason. One day he obtains two integers a and b occasionally. He wants to calculate the sum of all nice integers. Positive integer x is called nice if $\operatorname{mod}(x, b) \neq 0$ and $\frac{\operatorname{div}(x, b)}{\operatorname{mod}(x, b)} = k$, where k is some integer number in range [1, a].

By $\operatorname{div}(x, y)$ we denote the quotient of integer division of x and y. By $\operatorname{mod}(x, y)$ we denote the remainder of integer division of x and y. You can read more about these operations here: http://goo.gl/AcsXhT.

The answer may be large, so please print its remainder modulo 1 000 000 007 (10^9 + 7). Can you compute it faster than Dreamoon?


-----Input-----

The single line of the input contains two integers a, b (1 ≤ a, b ≤ 10^7).


-----Output-----

Print a single integer representing the answer modulo 1 000 000 007 (10^9 + 7).


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

Output
0

Input
2 2

Output
8



-----Note-----

For the first sample, there are no nice integers because $\operatorname{mod}(x, 1)$ is always zero.

For the second sample, the set of nice integers is {3, 5}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Link to Russian translation of the problem.

Kevin has an array A of N integers, but he doesn't like it - he only likes an array if all its neighboring elements are different (e.g. he likes the array [2,4,2,5,3,2,4], but not [1,2,3,3,4]).

Kevin can reverse any contiguous subarray of his array any number of times. For example, if he has the array [2,4,2,5,3,2,4] and reverses the subarray from 2^nd to 5^th element, he will obtain the array [2,3,5,2,4,2,4]. 

Now, Kevin wants to know the minimum number of reversals necessary to transform his array into an array he likes - if it's possible.

Input format:

The first line of the input will contain an integer N. The second line will contain N space-separated integers - the elements of A.

Output format:

If it's impossible to transform Kevin's array into an array he likes, print "-1" (without the quotes). Otherwise, print one number - the minimum number of reversals necessary.

Constraints:
1 ≤ N ≤ 10^5 
1 ≤ Ai ≤ 10^5
N ≤ 5 in test data worth 15% of all points
N ≤ 10^3 in test data worth 40% of all points

SAMPLE INPUT
7
1 3 2 2 4 4 4


SAMPLE OUTPUT
2

Explanation

First, Kevin reverses the subarray from the 3^rd to the 6^th element and gets the array [1,3,4,4,2,2,4]. Next, he reverses the elements from 4^th to 5^th and gets the array [1,3,4,2,4,2,4], which he likes. There's no way to create an array which Kevin likes using only one reversal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On the well-known testing system MathForces, a draw of $n$ rating units is arranged. The rating will be distributed according to the following algorithm: if $k$ participants take part in this event, then the $n$ rating is evenly distributed between them and rounded to the nearest lower integer, At the end of the drawing, an unused rating may remain — it is not given to any of the participants.

For example, if $n = 5$ and $k = 3$, then each participant will recieve an $1$ rating unit, and also $2$ rating units will remain unused. If $n = 5$, and $k = 6$, then none of the participants will increase their rating.

Vasya participates in this rating draw but does not have information on the total number of participants in this event. Therefore, he wants to know what different values of the rating increment are possible to get as a result of this draw and asks you for help.

For example, if $n=5$, then the answer is equal to the sequence $0, 1, 2, 5$. Each of the sequence values (and only them) can be obtained as $\lfloor n/k \rfloor$ for some positive integer $k$ (where $\lfloor x \rfloor$ is the value of $x$ rounded down): $0 = \lfloor 5/7 \rfloor$, $1 = \lfloor 5/5 \rfloor$, $2 = \lfloor 5/2 \rfloor$, $5 = \lfloor 5/1 \rfloor$.

Write a program that, for a given $n$, finds a sequence of all possible rating increments.


-----Input-----

The first line contains integer number $t$ ($1 \le t \le 10$) — the number of test cases in the input. Then $t$ test cases follow.

Each line contains an integer $n$ ($1 \le n \le 10^9$) — the total number of the rating units being drawn.


-----Output-----

Output the answers for each of $t$ test cases. Each answer should be contained in two lines.

In the first line print a single integer $m$ — the number of different rating increment values that Vasya can get.

In the following line print $m$ integers in ascending order — the values of possible rating increments.


-----Example-----
Input
4
5
11
1
3

Output
4
0 1 2 5 
6
0 1 2 3 5 11 
2
0 1 
3
0 1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
G: Treasure Hunter

problem

There are N treasure trove, each of which is numbered from 1 to N. A treasure of value p_i lies in the i-th mountain, and this treasure can be obtained when you visit the mountain. Once you get the treasure, you can only get the treasure once, because the treasure will disappear from the mountain.

You must use the road to move to different mountains. There are a total of N-1 roads between the mountains, and the i-th road connects the mountains u_i and v_i in both directions. Assuming that all roads are passable without problems, we know that any two mountains can travel to and from each other.

Since all roads have not been passed by anyone for a long time and cannot be crossed without repair, it is necessary to pay c_i yen to construct and make them passable when crossing the i-th road for the first time. Once the road is constructed, it can be passed without paying any more money.

As a treasure hunter, you have a budget of W Yen for road construction costs. Your goal is to maximize the total value of the treasure you get by first deciding on any one mountain to land on and then constructing a road for a total of less than W yen to move to a different mountain. How much value can you get at the maximum?

Please note that the treasure cannot be used as a construction cost because the treasure cannot be redeemed on the way.

Input format

The input is given in the following format.


N W
p_1 p_2 ... p_N
u_1 v_1 c_1
::
u_ {N-1} v_ {N-1} c_ {N-1}


* In the first line, the number of mountains N and the construction cost budget W are given.
* The second line gives the treasure value p_i sleeping on the i-th mountain.
* From the 3rd line to the N + 1th line, the road information is given. The 2 + i line represents the information of the i-th road, and indicates that there is a road with construction cost c_i between the mountains u_i and v_i.



Constraint

* 1 \ leq N \ leq 10 ^ 2
* 1 \ leq W \ leq 10 ^ 5
* 1 \ leq p_i \ leq 10 ^ 9
* 1 \ leq u_i \ lt v_i \ leq N
* If i \ neq j, u_i \ neq u_j or v_i \ neq v_j
* 1 \ leq c_i \ leq 10 ^ 5
* All given inputs are integers



Output format

Print the maximum total value of the treasure you get on one line. Don't forget the newline at the end.

Input example 1


3 10
6 8 2
one two Three
2 3 8


Output example 1


14

* It is best to land on Mountain 1 or 2 and build a road connecting Mountain 1 and Mountain 2 to get the treasures on Mountain 1 and Mountain 2. Since the construction cost budget is 10, it is not possible to construct both roads.



Input example 2


3 15
10 10 12
1 2 6
1 3 4


Output example 2


32

* You can get all the treasures.



Input example 3


5 1
4 8 8 2 10
one two Three
2 4 5
2 5 2
1 3 7


Output example 3


Ten

* In some cases, the budget is insufficient and no road can be constructed.





Example

Input

3 10
6 8 2
1 2 3
2 3 8


Output

14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array a consisting of n integers. As soon as he remembers all elements of a the game begins. Vasya closes his eyes and Petya does q actions of one of two types:

1) Petya says 4 integers l1, r1, l2, r2 — boundaries of two non-intersecting segments. After that he swaps one random element from the [l1, r1] segment with another random element from the [l2, r2] segment.

2) Petya asks Vasya the sum of the elements of a in the [l, r] segment.

Vasya is a mathematician so he answers Petya the mathematical expectation of the sum of the elements in the segment.

Your task is to write a program which will answer the second type questions as Vasya would do it. In other words your program should print the mathematical expectation of the sum of the elements of a in the [l, r] segment for every second type query.

Input

The first line contains two integers n, q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — the number of elements in the array and the number of queries you need to handle.

The second line contains n integers ai (1 ≤ ai ≤ 109) — elements of the array.

The next q lines contain Petya's actions of type 1 or 2.

If it is a type 1 action then the line contains 5 integers 1, l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).

If it is a type 2 query then the line contains 3 integers 2, l, r (1 ≤ l ≤ r ≤ n).

It is guaranteed that there is at least one type 2 query and segments [l1, r1], [l2, r2] don't have common elements. 

Output

For each type 2 query print one real number — the mathematical expectation of the sum of elements in the segment.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4 — formally, the answer is correct if <image> where x is jury's answer and y is yours.

Examples

Input

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


Output

3.0000000
3.0000000


Input

10 5
1 1 1 1 1 2 2 2 2 2
1 1 5 6 10
2 1 5
1 1 5 6 10
1 1 5 6 10
2 6 10


Output

6.0000000
8.0400000


Input

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


Output

23.0000000
14.0000000
28.0133333
21.5733333
55.0000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:


       "123"
       "132"
       "213"
       "231"
       "312"
       "321"


Given n and k, return the kth permutation sequence.

Note:


       Given n will be between 1 and 9 inclusive.
       Given k will be between 1 and n! inclusive.


Example 1:


Input: n = 3, k = 3
Output: "213"


Example 2:


Input: n = 4, k = 9
Output: "2314"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya works as a DJ in the best Berland nightclub, and he often uses dubstep music in his performance. Recently, he has decided to take a couple of old songs and make dubstep remixes from them.

Let's assume that a song consists of some number of words. To make the dubstep remix of this song, Vasya inserts a certain number of words "WUB" before the first word of the song (the number may be zero), after the last word (the number may be zero), and between words (at least one between any pair of neighbouring words), and then the boy glues together all the words, including "WUB", in one string and plays the song at the club.

For example, a song with words "I AM X" can transform into a dubstep remix as "WUBWUBIWUBAMWUBWUBX" and cannot transform into "WUBWUBIAMWUBX".

Recently, Petya has heard Vasya's new dubstep track, but since he isn't into modern music, he decided to find out what was the initial song that Vasya remixed. Help Petya restore the original song.

Input

The input consists of a single non-empty string, consisting only of uppercase English letters, the string's length doesn't exceed 200 characters. It is guaranteed that before Vasya remixed the song, no word contained substring "WUB" in it; Vasya didn't change the word order. It is also guaranteed that initially the song had at least one word.

Output

Print the words of the initial song that Vasya used to make a dubsteb remix. Separate the words with a space.

Examples

Input

WUBWUBABCWUB


Output

ABC 

Input

WUBWEWUBAREWUBWUBTHEWUBCHAMPIONSWUBMYWUBFRIENDWUB


Output

WE ARE THE CHAMPIONS MY FRIEND 

Note

In the first sample: "WUBWUBABCWUB" = "WUB" + "WUB" + "ABC" + "WUB". That means that the song originally consisted of a single word "ABC", and all words "WUB" were added by Vasya.

In the second sample Vasya added a single word "WUB" between all neighbouring words, in the beginning and in the end, except for words "ARE" and "THE" — between them Vasya added two "WUB".

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

Given a sequence A with n elements, a sequence B with m elements, q queries each consisting of an integer c.
For each query
The absolute value of the difference between the sum of all [la, ra] in sequence A and the sum of all [lb, rb] in sequence B is c. La, ra, lb, rb (0 ≤ la ≤ ra ≤ ra ≤ Find the number of combinations of n−1, 0 ≤ lb ≤ rb ≤ m−1, sequence numbers start from 0).

Constraints

* 1 ≤ n, m ≤ 4 × 104
* 1 ≤ q ≤ 105
* 1 ≤ ai, bi ≤ 5
* 0 ≤ ci ≤ 2 × 105

Input


n m q
a0 a1 ... an−1
b0 b1 ... bm−1
c0
c1
...
cq−1


All inputs are given as integers.
The number of elements n and m in the sequence and the number of queries q are given in the first row.
The elements of sequence A are given in the second row, and the elements of sequence B are given in the third row, separated by blanks.
The value ci of each query is given from the 4th line to the q line.

Output

The output consists of q lines. Print the number of combinations for each query in turn on one line.

Examples

Input

3 3 1
1 2 3
3 1 2
3


Output

6


Input

5 4 2
1 2 3 4 5
2 2 2 2
11
12


Output

3
4

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