题目描述

给定一张 $N$ 个点的图，每个点有权值 $A_i$ 和价值 $B_i$。

两个点 $x,y$ 之间存在一条无向边当且仅当 $A_x\text{ xor }A_y>\max(A_x,A_y)$。

你需要对于 $i=1,2,\cdots n$ 依次求出点 $i$ 所在连通块中所有点的价值和。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $A_i$。

第三行输入 $N$ 个正整数 $B_i$。

输出格式

输出 $N$ 行，第 $i$ 行包含一个整数，代表点 $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

提示

【数据范围】

本题采用捆绑测试。

• Subtask 1（8 points）：只存在一组数据，满足 $N=8$，$A=[6,39,11,63,3,39,1,43]$，$B=[4,8,3,7,9,1,2,2]$。
• Subtask 2（13 points）：保证 $N \leq 200$。
• Subtask 3（10 points）：保证 $N \leq 2000$。
• Subtask 4（4 points）：保证 $A_1=A_2=\cdots=A_n$。
• Subtask 5（7 points）：保证存在非负整数 $k$ 使得 $A_i=2^k$。
• Subtask 6（19 points）：$A_i\leq 2^{12}-1$。
• Subtask 7（39 points）：无特殊限制。

对于所有数据，$1 \leq N \leq 10^5$，$1 \leq A_i \leq 2^{30}-1$，$1 \leq B_i \leq 10^9$。