You have an array of N integers $S_1, S_2, ... S_N$. Consider a N x N matrix such that $A_{i,j} = S_i \oplus S_j$. Here $\oplus$ indicates bitwise xor operator.
You have been given Q queries. Each query consists of four integers $x_1, y_1, x_2, y_2$ which denotes a submatrix with ($x_1, y_1$) as their top-left corner and ($x_2, y_2$) as their bottom-right corner such that $x_1 \le x_2$ and $y_1 \le y_2$. For each of the query, you have to print summation of all integers lying in queried submatrix.

INPUT:
First line of input consists of integer N. Next line consist of N space separated integers denoting array $S_1, S_2, ... S_N$. Next line consists of integer Q denoting total number of queries. Next Q lines consist of four integers $x_1, y_1, x_2, y_2$ denoting the queried submatrix.

OUTPUT:
For each of the query, print a single number in a separate line which denotes summation of all the numbers lying in queried submatrix.

CONSTRAINTS:
$1 \le N \le 10^6$
$1 \le S_i \le 10^6$
$1 \le Q \le 10^6$
$1 \le x_1 \le x_2 \le N$
$1 \le y_1 \le y_2 \le N$