Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4053
Couleur

Time Limit: 6 Seconds      Memory Limit: 131072 KB

DreamGrid has an array of $n$ integers. On this array he can perform the following operation: choose an element that was not previously chosen and mark it as unavailable. DreamGrid would like to perform exactly $n$ operations until all the elements are marked.

DreamGrid defines the cost of a subarray as the number of inversions in the subarray. Before performing an operation, DreamGrid would like to know the maximum cost of a subarray that doesn't contain any unavailable elements.

Recall that a subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ is a contiguous subpart of the original array where $1 \le l \le r \le n$. An inversion in a subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ is a pair of indices $(i, j)$ $(l \le i < j \le r)$ such that the inequality $a_i > a_j$ holds.

#### Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a single integer $n$ $(1 \le n \le 10^5)$ -- the length of the array.

The second line contains the $n$ values of the array $a_1,a_2,...,a_n$ $(1 \le a_i \le n)$.

The third line contains a permutation $p_1,p_2,\dots,p_n$, representing the indices of the elements chosen for the operations in order.

Note that the permutation is encrypted and you can get the real permutation using the following method: Let $z_i$ be the answer before the $i$-th operation. The actual index of the $i$-th operation is $p_i \oplus z_i$ where $\oplus$ is bitwise exclusive or operator.

It is guaranteed that the sum of all $n$ does not exceed $10^6$.

#### Output

For each test case, output $n$ integers $z_1, z_2, \dots, z_n$ in a single line seperated by one space, where $z_i$ is the answer before the $i$-th operation.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

#### Sample Input

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10


#### Sample Output

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0


#### Hint

The decoded permutation of each test case is $\{2,4,5,3,1\}$, $\{1,3,8,7,9,2,4,5,10,6\}$ and $\{15,12,2,1,9,6,11,14,3,13,4,5,8,7,10\}$

Author: LIN, Xi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status