Problem Description

Given a graph with $N$ vertices, each vertex has a weight $A_i$ and a value $B_i$.

An undirected edge exists between vertices $x$ and $y$ if and only if $A_x \text{ xor } A_y > \max(A_x, A_y)$.

For each $i$ from 1 to $N$, you need to find the sum of the values of all vertices in the connected component that vertex $i$ belongs to.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers $A_i$.

The third line contains $N$ positive integers $B_i$.

Output Format

Output $N$ lines, where the $i$-th line contains an integer representing the sum of the values of all vertices in the connected component that vertex $i$ belongs to.

Sample Input and Output

Sample Input #1

3
2 1 1
20 30 10

Sample Output #1

60
60
60

Sample Input #2

4
5 4 4 5
10 20 30 40

Sample Output #2

10
20
30
40

Sample Input #3

5
1 2 1 7 11
20 10 30 100 100

Sample Output #3

60
60
60
200
200

Notes

[Data Range]

This problem uses batched testing.

• Subtask 1 (8 points): Only one set of data exists, satisfying $N=8$, $A=[6,39,11,63,3,39,1,43]$, $B=[4,8,3,7,9,1,2,2]$.
• Subtask 2 (13 points): Guaranteed $N \leq 200$.
• Subtask 3 (10 points): Guaranteed $N \leq 2000$.
• Subtask 4 (4 points): Guaranteed $A_1=A_2=\cdots=A_n$.
• Subtask 5 (7 points): Guaranteed there exists a non-negative integer $k$ such that $A_i=2^k$.
• Subtask 6 (19 points): $A_i \leq 2^{12}-1$.
• Subtask 7 (39 points): No special restrictions.

For all data, $1 \leq N \leq 10^5$, $1 \leq A_i \leq 2^{30}-1$, $1 \leq B_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分