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