There are $$n$$ balls along a number line, each ball is represented by a point on the line. Ball $$i$$ moves at velocity $$v_i$$ ($$v_i \neq 0$$) along this number line and is initially at point $$x_i$$.

When two balls collide (occupy the same point along the number line), their velocities switch. For example, if ball $$i$$ with velocity $$2$$ collides with ball $$j$$ with velocity $$-3$$, ball $$i$$ will have velocity $$-3$$ and ball $$j$$ will have velocity $$2$$ after the collision.

Given each ball's initial distinct position and velocity, find for each ball $$i$$ the sum of the floor of the times that ball $$i$$ collides with another ball. Formally, ball $$i$$ collides with another ball $$k$$ times in total at times $$t_1, t_2, \ldots t_k$$. Print, $$\sum_{i=1}^k \lfloor t_i \rfloor$$ for each ball.

It is guaranteed that whenever two balls $$i, j$$ collide, the signs of their velocities will be different ($$v_i \cdot v_j < 0$$).

Input format

• The first line of the input contains a single integer $$t$$ denoting the number of test cases.
• The first line of each test case contains a single integer $$n$$ denoting the number of balls.
• The second line of each test case contains $$n$$ integers $$x_i$$ denoting the initial position of ball $$i$$.
• The third line of each test case contains $$n$$ integers $$v_i$$ denoting the velocity of ball $$i$$.

Output format

Print $$n$$ integers denoting the \(i^{th}\) being the sum of the floors of each time ball $$i$$ collides with another ball.

Constraints

$$1 \leq t \leq 100$$

$$1\leq n \leq 2000$$

$$|x_i| \leq 2000$$

$$0 < |v_i| \leq 2000$$

• It is guaranteed that, in the given input, whenever two balls collide the signs of their velocities will be different.

• It is guaranteed that the sum of $$n$$ over all test cases is less than or equal to $$2000$$.

• No two pairs of balls collide at the same place at the same time.