G. Rocket Dust
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ rockets on a straight line.

The $$$i$$$-th rocket starts at position $$$x_i$$$, has direction $$$d_i$$$, and speed $$$v_i$$$.

The direction $$$d_i$$$ is either L or R. If $$$d_i = \texttt{L}$$$, the rocket moves to the left. If $$$d_i = \texttt{R}$$$, the rocket moves to the right.

It is guaranteed that all starting positions are distinct.

At the beginning, the rockets are not moving. At time $$$0$$$, Moon presses a dangerous button, and all rockets start moving at the same time.

If at the same moment two or more rockets are at the same position, all of these rockets explode into dust. After a rocket explodes, it disappears and will not affect any other rocket.

For each rocket, determine the time at which it explodes, or determine that it will never explode.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of rockets.

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^9$$$) — the starting positions of the rockets.

The third line of each test case contains a string $$$d$$$ of length $$$n$$$ ($$$d_i \in \{\texttt{L}, \texttt{R}\}$$$) — the directions of the rockets.

The fourth line of each test case contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — the speeds of the rockets.

It is guaranteed that all $$$x_i$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one line containing $$$n$$$ values.

The $$$i$$$-th value should be the explosion time of the $$$i$$$-th rocket.

If the rocket never explodes, print $$$-1$$$.

Otherwise, print the explosion time as a real number.

Your answer will be considered correct if its relative error does not exceed $$$10^{-6}$$$.

Example
Input
3
4
0 4 10 12
RLLR
1 1 2 1
3
0 4 6
RLL
1 1 2
2
0 5
RL
2 1
Output
2.0000000000 2.0000000000 -1 -1
2.0000000000 2.0000000000 2.0000000000
1.6666666667 1.6666666667
Note

In the first test case, the first rocket moves to the right with speed $$$1$$$, and the second rocket moves to the left with speed $$$1$$$.

They meet at position $$$2$$$ after $$$2$$$ seconds, so both of them explode at time $$$2$$$.

The third rocket moves to the left, and the fourth rocket moves to the right. They never meet, so both of them do not explode.

In the second test case, after $$$2$$$ seconds, all three rockets are at position $$$2$$$.

Therefore, all of them explode at time $$$2$$$.

In the third test case, the first rocket moves to the right with speed $$$2$$$, and the second rocket moves to the left with speed $$$1$$$.

They meet after $$$\frac{5}{3}$$$ seconds, so both of them explode at time $$$\frac{5}{3}$$$.