There is an infinate number of boxes, numbered with consecutive integer values. Initially, there are *N* different boxes with cats in it. The position of i-th box is *X[i]* and it contains a cat with label *P[i]*. All the other boxes are empty. At any moment of time, there can be no two or more cats in the same box.

In a single turn, you can choose any two cats *a* and *b*, where cat with label *b* is located to the right of cat with label *a*. The only restriction is that there should be no other cats in any box between them. The following process occures:

 - The cat with label *b* moves *D[b]* boxes to the left, but he stops if its impossible to move anymore because of an occupied box on this way.
 - Cats *a* and *b* swap their labels.

You can perform this operation no more than *K* times.

You are interested in two values. The first one is the number of inversions of cats labels after all operations, let's call it *A*. The other value is the total sum of squared distances between consecutive cats, lets call it *B*. Your score for a test case the value of *A/B*, and your task is to minimize the score.

**Input format**

The first line of the input contains two integers *N* and *K*. The second line contains *N* space separated integers *X[i]* (sorted in increasing order)  - the initially occupied positions. The third line contains *N* space separated integers *P[i]* - the inital label of cat at position *X[i]*. Finally, the fouth line contains *N* space separated integers *D[i]* - the maximal amount of position a cat with label i can move.

**Output format**

For each event of the second type print the answer to the corresponding event.