Anton and School
Contest: Codeforces Round 379 (Div. 2)
Difficulty rating: 2500
Tags: bitmasks, constructive algorithms, implementation, math

Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays b and c of length n, find array a, such that:

$$\begin{cases}
b_i = (a_i \text{ and } a_1) + (a_i \text{ and } a_2) + \cdots + (a_i \text{ and } a_n), \\
c_i = (a_i \text{ or } a_1) + (a_i \text{ or } a_2) + \cdots + (a_i \text{ or } a_n).
\end{cases}$$

where a and b means bitwise AND, while a or b means bitwise OR.

Usually Anton is good in arraystudying, but this problem is too hard, so Anton asks you to help.

Input format:
The first line of the input contains a single integers n (1 ≤ n ≤ 200 000) — the size of arrays b and c.

The second line contains n integers bi (0 ≤ bi ≤ 109) — elements of the array b.

Third line contains n integers ci (0 ≤ ci ≤ 109) — elements of the array c.

Output format:
If there is no solution, print  - 1.

Otherwise, the only line of the output should contain n non-negative integers ai — elements of the array a. If there are multiple possible solutions, you may print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
6 8 4 4
16 22 10 10

Example output:
3 5 1 1

Example input:
5
8 25 14 7 16
19 6 9 4 25

Example output:
-1

Editorial:
We'll prove that $$(a\ \mathrm{and}\ b)+(a\ \mathrm{or}\ b)=(a+b)$$. At first, let's prove that it's true when $$a \in \{0, 1\}$$ и $$b \in \{0, 1\}$$. To do it, let's consider all the possible values of a and b:
$$\begin{array}{|c|c|c|c|c|}
\hline
a & b & \text{a and b} & \text{a or b} \\
\hline
0 & 0 & 0 & 0 \\
\hline
0 & 1 & 0 & 1 \\
\hline
1 & 0 & 0 & 1 \\
\hline
1 & 1 & 1 & 1 \\
\hline
\end{array}$$
Here we can see that the equality is true. Now, we'll prove it for any positive integers. To do it, let's divide a and b into bits:
$$a = b a _ { 0 } \cdot 2 ^ { 0 } + b a _ { 1 } \cdot 2 ^ { 1 } +...$$
$$b = bb_0 \cdot 2^0 + bb_1 \cdot 2^1 +...$$
Here ba0, ba1, ... mean the bits of a and bb0, bb1, ... mean the bits of b.
Now, let's divide (a and b) and (a or b) into bits:
$$(a\;and\;b)=(ba_{0}\;and\;bb_{0})\cdot2^{0}+(ba_{1}\;and\;bb_{1})\cdot2^{1}+\ldots$$
$$(a\ or\ b)=(ba_{0}\ or\ bb_{0})\cdot2^{0}+(ba_{1}\ or\ bb_{1})\cdot2^{1}+\ldots$$
Rewrite the initial equality:
$$(ba_0 \text{ and } bb_0) \cdot 2^0 + (ba_1 \text{ and } bb_1) \cdot 2^1 + \ldots + (ba_0 \text{ or } bb_0) \cdot 2^0 + (ba_1 \text{ or } bb_1) \cdot 2^1 + \ldots = ba_0 \cdot 2^0 + ba_1 \cdot 2^1 + \ldots + bb_0 \cdot 2^0 + bb_1 \cdot 2^1 + \ldots$$
Now it's not hard to observe that $$( ba_{0} \; and \; bb_{0} ) \cdot 2^{0} + ( ba_{0} \; or \; bb_{0} ) \cdot 2^{0} = ba_{0} \cdot 2^{0} + bb_{0} \cdot 2^{0}$$ is true because the equality $$(a\ \mathrm{and}\ b)+(a\ \mathrm{or}\ b)=(a+b)$$ is true for bits. Similarly, we see that $$( ba_{1} \; and \; bb_{1} ) \cdot 2^{1} + ( ba_{1} \; or \; bb_{1} ) \cdot 2^{1} = ba_{1} \cdot 2^{1} + bb_{1} \cdot 2^{1}$$ is true and so on.
From all this it follows that the equality $$(a\ \mathrm{and}\ b)+(a\ \mathrm{or}\ b)=(a+b)$$ is true.
Let's create an array di where $$d_i = b_i + c_i$$. It's obvious that
$$$$
See that
$$$$
from where $$a_{1}+a_{2}+\cdots+a_{n}=\frac{d_{1}+d_{2}+\cdots+d_{n}}{2\cdot n}.$$
Now it's not hard to find ai: $$a_i = \frac{d_i - (a_1 + a_2 + \cdots + a_n)}{n}.$$
Now, we only must check the answer for correctness. It's obvious then, if answer exists, it's alway unique, because it's explicitly derived from the formula above. To check if the answer exists, let's build arrays b and c from the found array a and compare it with the arrays given in the input. We'll do this separately for every bit. Let's calculate kj — amount of numbers in array a that has a one in the j-th bit. Let's denote the j-th bit of ai as Ai, j. Now, let's count Bi, j and Ci, j such as
$$B_{i,j} = (A_{1,j} \text{ and } A_{i,j}) + (A_{2,j} \text{ and } A_{i,j}) + \cdots + (A_{n,j} \text{ and } A_{i,j})$$ $$C_{i,j} = (A_{1,j} \ or \ A_{i,j}) + (A_{2,j} \ or \ A_{i,j}) + \cdots + (A_{n,j} \ or \ A_{i,j})$$
It's not hard to do since we know kj:
$$\begin{aligned}
B_{i,j} &= 0, \text{ if } A_{i,j} = 0, \\
B_{i,j} &= k_j, \text{ if } A_{i,j} = 1.
\end{aligned}$$
See that if we calculate Bi, j и Ci, j, it will be easy to find bi и ci:
$$b_{i}=B_{i,0}\cdot2^{0}+B_{i,1}\cdot2^{1}+\ldots$$ $$c_{i}=C_{i,0}\cdot2^{0}+C_{i,1}\cdot2^{1}+\ldots$$
Time complexity is $${\mathcal {O}}(n\cdot \log val)$$, where $$val = \max(a_1, a_2, \ldots, a_n)$$.