Bob is playing a Tower Defense Game. The game is so hard that Bob has spent several hours on it.

At the start of the game, Bob will build n towers. For every i (1 ≤ i ≤ n), a tower with height h_i will be built at position x_i. In each round, the monster will attack the leftmost or the rightmost tower with equal probabilities until all the towers are destroyed.

After being attacked, the tower will fall left with probability p or fall right with probability 1 - p. For a tower at position x_i, the [x_i - h_i, x_i] will be covered by stones if it falls left and cannot build the tower anymore. Similar to this, the [x_i, x_i + h_i] will be covered if it falls right. What's more, if there's another tower strictly in the covered range, it will be hit and fall in the same direction of the falling tower as domino. Note that a tower will not be hit when it is located at position [x_i - h_i] or [x_i + h_i].

Unfortunately, it seems the boss in one of the levels is impossible to defeat. After wasting several hours in challenging this level, Bob started to do something to escape from this cruel reality. He wanted to know the expected length of the ground covered with stones.

There are multiple cases.
The first line of input is an integer T (1 ≤ T ≤ 20) which indicates the cases of test data.
The first line of each case contains a positive integer n (1 ≤ n ≤ 200) and a float p (0 ≤ p ≤ 1). The second line contains exactly n integers h_i (1 ≤ h_i ≤ 20). The third line contains exactly n integers x_i (1 ≤ x_i ≤ 10⁶). x_i ≠ x_j for every i ≠ j.

For each case, please print the answer in a single line. Your answer will be accepted if its absolute error or relative error is less than 10^-6.