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\)