Bessie is making a show called Moojutsu Cowsen. For one episode, she invites $n$ sorcerers and lines them up from left to right. The initial skill level of the $i$-th sorcerer is $a_i$.

The sorcerers compete in a king-of-the-hill tournament. The leftmost remaining sorcerer starts as the champion, and his current skill is equal to his initial skill.

Then, the champion faces each remaining sorcerer to his right, one by one. Suppose the current champion has skill $s$, and the next sorcerer has skill $x$.

If $s \lt x$, the champion forfeits. The next sorcerer becomes the new champion with skill $x$.

Otherwise, the champion fights and wins (the champion still wins when $s = x$). In this case, the champion's current skill becomes $s+x$.

Bessie finds forfeits boring, so before running the tournament, she may remove some sorcerers from the lineup.

You are given a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$. For each $0 \le i \le n-1$, Bessie removes sorcerers $p_1,p_2,\ldots,p_i$ from the lineup. If $i=0$, no sorcerers are removed. The relative order of all remaining sorcerers does not change.

For each such $i$, determine how many forfeits happen when Bessie runs the tournament using only the remaining sorcerers.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).

The third line of each test case contains a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$.

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

Output

For each test case, output $n$ integers.

The $i$-th integer should be the number of forfeits after removing sorcerers $p_1,p_2,\ldots,p_{i-1}$.

Note

For the first test case, the answers are $2,1,0,0$.

Before any removals, the array is $[1,2,4,3]$. The champion with skill $1$ forfeits against skill $2$, and then the champion with skill $2$ forfeits against skill $4$. The champion with skill $4$ defeats skill $3$, so there are $2$ forfeits.

After removing sorcerer $1$, the remaining array is $[2,4,3]$. The champion with skill $2$ forfeits against skill $4$, and then the champion with skill $4$ defeats skill $3$, so there is $1$ forfeit.

After removing sorcerers $1$ and $2$, the remaining array is $[4,3]$. The champion defeats the only remaining sorcerer, so there are $0$ forfeits. After removing sorcerers $1$, $2$, and $3$, only one sorcerer remains, so there are also $0$ forfeits.

For the second test case, the answers are $1,0,2,1,0$.

Before any removals, the array is $[3,1,7,2,6]$. The champion with skill $3$ defeats skill $1$ and gains one skill point, then forfeits against skill $7$. After that, the champion defeats skills $2$ and $6$, so there is $1$ forfeit.

After removing sorcerer $3$, whose skill is $7$, the remaining array is $[3,1,2,6]$. The champion defeats every remaining sorcerer, so there are $0$ forfeits.

After also removing sorcerer $1$, the remaining array is $[1,2,6]$ The champion with skill $1$ forfeits against skill $2$, and then the champion with skill $2$ forfeits against skill $6$, so there are $2$ forfeits.

After also removing sorcerer $5$, the remaining array is $[1,2]$. There is $1$ forfeit. Finally, after also removing sorcerer $2$, only one sorcerer remains, so there are $0$ forfeits.