Finally a Problem Without a Legend

Given three arrays $a,b,c$ of length $n$.

We will construct an undirected weighted graph consisting of $n$ vertices such that an edge between two distinct vertices $u$ and $v$ exists if and only if $a_u|a_v$ is not a supermask of $b_u\&b_v$, and the weight of this edge will be $c_u+c_v$.

You need to answer $q$ queries, each defined by two numbers $u$ and $v$. For each query, you need to output the length of the shortest path from vertex $u$ to vertex $v$, or $-1$ if such a path does not exist. The length of a path is the sum of the weights of its edges, and the shortest path is the one with the minimal length.

Here, $\mid$ means bitwise OR operation, and $\&$ means bitwise AND operation.

We consider an integer $a$ to be a supermask of an integer $b$ if and only if all bits which are turned on in $b$ are also turned on in $a$, more formally if $a\&b=b$.

Input

The first line contains one integer $n(2\le n\le 10^5)$ — the size of the graph.

The second line contains $n$ integers $a_i(0\le a_i\le 10^{18})$.

The third line contains $n$ integers $b_i(0\le b_i\le 10^{18})$.

The fourth line contains $n$ integers $c_i(0\le c_i\le 10^{12})$.

The fifth line contains one integer $q(1\le q\le 10^6)$.

The next $q$ lines contain a pair of distinct integers $u,v(1\le u,v\le n)$ — vertices between which you need to find the shortest path.

Output

For each query, you need to output the length of the shortest path, or $-1$ if such a path does not exist.

Examples

Note

The Graph for the first sample.

In the first query it is asked about the shortest path between vertex $2$ and $5$, the optimal way is $2$ — $4$ — $5$, the length is $18+10=28$.

Scoring

1. ($6$ points): $a_1=a_i(1\le i\le n)$, $b_1=b_i(1\le i\le n)$;

2. ($12$ points): $n\le 100$, $q\le 100$;

3. ($12$ points): $n\le 1000$;

4. ($12$ points): $n\le 10000$, $a_i\le 10^6(1\le i\le n)$, $b_i\le 10^6(1\le i\le n)$;

5. ($12$ points): $c_i=0$;

6. ($25$ points): $a_i\le 10^{12}(1\le i\le n)$, $b_i\le 10^{12}(1\le i\le n)$;

7. ($71$ points): no additional constraints.