Finally a Problem Without a Legend#11729
You can't rickroll someone who doesn't have YouTube Premium.
Given three arrays , , of length .
We will construct an undirected weighted graph consisting of vertices such that an edge between two distinct vertices and exists if and only if a_u \mid 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 queries, each defined by two numbers and . For each query, you need to output the length of the shortest path from vertex to vertex , or 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 minimal length.
Here, means the bitwise OR operation, and means the bitwise AND operation.
We consider an integer to be a supermask of an integer if and only if all bits which are turned on in are also turned on in , more formally if a \& b = b.
The first line contains one integer (2 \le n \le 10^5) — the size of the graph.
The second line contains integers a_i (0 \le a_i \le 10^{18}).
The third line contains integers b_i (0 \le b_i \le 10^{18}).
The fourth line contains integers c_i (0 \le c_i \le 10^{12}).
The fifth line contains one integer (1 \le q \le 10^6).
The next lines contain a pair of distinct integers , (1 \le u, v \le n) — vertices between which you need to find the shortest path.
For each query, you need to output the length of the shortest path, or if such a path does not exist.
Example
The graph for the first sample.
In the first query, it is asked about the shortest path between vertex and . The optimal way is — — , and the length is 18 + 10 = 28.
( points): a_1 = a_i (1 \le i \le n), b_1 = b_i (1 \le i \le n);
( points): n \le 100, q \le 100;
( points): n \le 1000;
( points): n \le 10000, a_i \le 10^6 (1 \le i \le n), b_i \le 10^6 (1 \le i \le n);
( points): c_i = 0;
( points): a_i \le 10^{12} (1 \le i \le n), b_i \le 10^{12} (1 \le i \le n);
( points): no additional constraints.