# 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, $∣$ 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≤n≤10_{5})$ — the size of the graph.

The second line contains $n$ integers $a_{i}(0≤a_{i}≤10_{18})$.

The third line contains $n$ integers $b_{i}(0≤b_{i}≤10_{18})$.

The fourth line contains $n$ integers $c_{i}(0≤c_{i}≤10_{12})$.

The fifth line contains one integer $q(1≤q≤10_{6})$.

The next $q$ lines contain a pair of distinct integers $u,v(1≤u,v≤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

($6$ points): $a_{1}=a_{i}(1≤i≤n)$, $b_{1}=b_{i}(1≤i≤n)$;

($12$ points): $n≤100$, $q≤100$;

($12$ points): $n≤1000$;

($12$ points): $n≤10000$, $a_{i}≤10_{6}(1≤i≤n)$, $b_{i}≤10_{6}(1≤i≤n)$;

($12$ points): $c_{i}=0$;

($25$ points): $a_{i}≤10_{12}(1≤i≤n)$, $b_{i}≤10_{12}(1≤i≤n)$;

($71$ points): no additional constraints.