You are given an array A containing N integers. You have to answer Q queries.

Queries are of form:

L R

Here you have to fInd sum of all numbers $$A_{i}$$, for those $$A_{i}$$ which has odd frequency in subarray L to R

INPUT CONSTRAINTS

• $$1 \le N,Q \le 10^5$$
• $$1 \le A_i \le 10^9$$
• $$1 \le L \le R \le N$$

INPUT FORMAT

First line of input contains a single integer $$N$$, next line contains $$N$$ space separated integers, elements of array $$A$$. Next line of input contains a single integer $$Q$$. $$Q$$ lines follow each containing two space separated integer $$L$$ and $$R$$.

OUTPUT Fvv

For each query, print the answer to the query in new line.

Hint:

Mo's Algorithm