Problem Description

You are given a graph with $N$ vertices. Each vertex has a weight $A_i$ and a value $B_i$.

There is an undirected edge between two vertices $x, y$ if and only if $A_x\text{ xor }A_y>\max(A_x,A_y)$.

You need to compute, for $i=1,2,\cdots n$ in order, the sum of values of all vertices in the connected component that contains vertex $i$.

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. The $i$-th line contains an integer representing the sum of values of all vertices in the connected component that contains vertex $i$.

3
2 1 1
20 30 10

60
60
60

4
5 4 4 5
10 20 30 40

10
20
30
40

5
1 2 1 7 11
20 10 30 100 100

60
60
60
200
200

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (8 points): There is only one test case, with $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 that 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 testdata, $1 \leq N \leq 10^5$, $1 \leq A_i \leq 2^{30}-1$, $1 \leq B_i \leq 10^9$.

Translated by ChatGPT 5