Restore Array from Partial XOR Prefix and Suffix

Given an integer array \(a_1,a_2,\dots,a_n\) with \(0 \le a_i < 2^{60}\) for \(1\le i\le n\), its prefix XOR array is defined as \(p_i=a_1\oplus a_2\oplus\dots\oplus a_i\) and its suffix XOR array as \(s_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n\). Unfortunately, someone replaced exactly \(n\) entries (out of the total \(2n\) entries) in the two arrays with \(-1\) (i.e. some of the entries in p and s are missing).

You are given the two arrays p and s (each of length \(n\)); for every index \(i\) the value is either the originally computed one or \(-1\) (representing a missing value). It is guaranteed that there exists at least one array \(a\) which could have produced the given arrays p and s (i.e. if an entry is not \(-1\) then it equals the corresponding XOR computed from \(a\)).

Your task is to output any valid array \(a_1,a_2,\dots,a_n\) (with \(0 \le a_i < 2^{60}\)) such that if you compute its prefix and suffix XOR arrays, all the entries provided in the input are matched.

Note: The XOR operator is denoted by \(\oplus\). All formulas must be interpreted in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) (\(1\le n\le 10^5\)).

The next line contains \(n\) space‐separated integers representing the array \(p\). Each integer is either a nonnegative integer less than \(2^{60}\) or \(-1\) (indicating a missing value).

The next line contains \(n\) space‐separated integers representing the array \(s\). Each integer is either a nonnegative integer less than \(2^{60}\) or \(-1\).

outputFormat

Output \(n\) space‐separated integers \(a_1,a_2,\dots,a_n\) (with \(0\le a_i<2^{60}\)) which is a possible original array that produces the given (partial) XOR prefix and suffix arrays.

sample

3
1 -1 -1
-1 1 3

1 2 3