D. The Boys and Wasting Time Syndrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad, Hamza, Malek, and Bahaa were having a "break" at the beach (garage). They were discussing a problem Bahaa wrote, but it was too easy, so they started throwing ideas, and this is one of them.

In an Amazon Warehouse, there are $$$n$$$ items; the $$$i$$$-th item has a code $$$a_i$$$, and its price is $$$b_i$$$.

They have special pricing when you buy items in pairs. If you buy item $$$i$$$ and item $$$j$$$, the cost is $$$cost(i, j) = (a_i | a_j) \times b_j$$$.

For each item $$$i$$$, they're interested in calculating the following sum $$$$$$\sum_{j=1}^n cost(i, j)$$$$$$.

Input

The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

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

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i \lt 2^{15})$$$ .

The third line of the test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \lt 2^{15})$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, print $$$n$$$ integers; the $$$i$$$-th integer is the cost over all $$$j$$$-s for the $$$i$$$-th item.

Example
Input
3
3
1 2 3
1 2 3
3
3 2 1
1 2 3
4
2 4 8 15
5 3 10 4
Output
16 16 18 
18 16 12 
188 222 226 330