703_D. Mishka and Interesting sum_33187
Little Mishka enjoys programming. Since her birthday has just passed, her friends decided to present her with array of non-negative integers a1, a2, ..., an of n elements!

Mishka loved the array and she instantly decided to determine its beauty value, but she is too little and can't process large arrays. Right because of that she invited you to visit her and asked you to process m queries.

Each query is processed in the following way:

  1. Two integers l and r (1 ≤ l ≤ r ≤ n) are specified — bounds of query segment. 
  2. Integers, presented in array segment [l, r] (in sequence of integers al, al + 1, ..., ar) even number of times, are written down. 
  3. XOR-sum of written down integers is calculated, and this value is the answer for a query. Formally, if integers written down in point 2 are x1, x2, ..., xk, then Mishka wants to know the value <image>, where <image> — operator of exclusive bitwise OR. 



Since only the little bears know the definition of array beauty, all you are to do is to answer each of queries presented.

Input

The first line of the input contains single integer n (1 ≤ n ≤ 1 000 000) — the number of elements in the array.

The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — array elements.

The third line of the input contains single integer m (1 ≤ m ≤ 1 000 000) — the number of queries.

Each of the next m lines describes corresponding query by a pair of integers l and r (1 ≤ l ≤ r ≤ n) — the bounds of query segment.

Output

Print m non-negative integers — the answers for the queries in the order they appear in the input.

Examples

Input

3
3 7 8
1
1 3


Output

0


Input

7
1 2 1 3 3 2 3
5
4 7
4 5
1 3
1 7
1 5


Output

0
3
1
3
2

Note

In the second sample:

There is no integers in the segment of the first query, presented even number of times in the segment — the answer is 0.

In the second query there is only integer 3 is presented even number of times — the answer is 3.

In the third query only integer 1 is written down — the answer is 1.

In the fourth query all array elements are considered. Only 1 and 2 are presented there even number of times. The answer is <image>.

In the fifth query 1 and 3 are written down. The answer is <image>.


        import java.io.*;
         
            import java.math.BigInteger;
        import java.text.DecimalFormat;
        import java.util.*;
   
             public class Main {
            	public static InputReader in;
                public static PrintWriter pw;
             
             
             
            	public static void main(String args[]) 
            	{
            		new Thread(null, new Runnable() {
                        public void run() {
                            try{
                                solve();
                            }
                            catch(Exception e){
                                e.printStackTrace();
                            }
                        }
                    }, "1", 1 << 26).start();
                }
            	static ArrayList<Integer> g[];
            	static ArrayList<Integer> h[];
            	static boolean visited[];
            	static int[] parent;
            	static int par[];
            	static int degree[];
            	static int edjes=0;
            	static int start=-1;
            	static int end=-1;
            	static int Total=0;
            	static int time1[];
            	static int time2[];
            	static int glob=0;
            	static int[] ans;
            	static boolean vis2[][];
            	//static long sum1=0;
            	//static long val[];
                static ArrayList<Integer> levels[];
                static int max=0;
                static int lev=1;
                static ArrayList<Integer> nodes[];
                static ArrayList<Integer> values[];
                static int depth[];
                static boolean found=false;
               // static long sm[];
                static int sum1=0;
                static int pre[][];
                static int subtree[];
               static  int cnt=0;
               static  HashMap<String,Integer> hm;
               static int sm[];
               static int size[];
               static long mul[];
               static long d[]=new long[1000000];
               static int tot=0;
               static long highest=(long)1e9;
               static boolean bit=false;
                static Stack<Integer> tt=new Stack();
               static HashSet<Character> set;
         	   static long fact[],num[];
         	   static long MOD=1000000007;
         	   static int value[];static int premen[];
         	   static int count=0,index=0;
         	   static double ans11[];
         	   static int price[];
         	   static ArrayList<String> hp[][];
         	   static boolean visit[][];
         	   static int cnu[]=new int[1000001];
         	   static int label=1;
         	   static int his[][];
         	   static int size1=0;
         	   static int up[],down[];
         	   static int TotalUp=0;
         	   static long dist[];
         	//   static HashMap<String,Integer> hm1=new HashMap();
         	  // static HashMap<Integer,Integer> hm2=new HashMap();
         	   static TreeSet<Long> set1=new TreeSet();
         	  static  long DP[][][]=new long[20][200][1500];
         	 	static int t=-1,n=-1;
         	 	static int two[],min[],r[];
         	 	static int total[];static int black[];
         	 	static int Parent[];
         	 	static int max2[];
         	// 	static int tin[],tout[],a[];
         	 public static void solve() throws FileNotFoundException{
            		
            	
            		 in = new InputReader(System.in);
            		 pw = new PrintWriter(System.out);  
            	/*	 String p=in.readString();
            	     char c[]=p.toCharArray();
            	     int z[]=new int[p.length()];
            	     z[0]=0;
            	     int left=0;
            	     int right=0;
            	     for(int i=1;i<p.length();i++)
            	     {
            	    	 if(i>right)
            	    	 {
            	    		 
            	    		 left=right=i;
            	    		 while(right<p.length()&&c[right]==c[right-left])
            	    			 right++;
            	    		 z[i]=right-left;
            	    		 right--;
            	    	 }
            	    	 else
            	    	 {
            	    		 int k=i-left;
            	    		 if(z[k]<right-i+1)
            	    		 {
            	    			 z[i]=z[k];
            	    		 }
            	    		 else
            	    		 {
            	    			 left=i;
            	    			 while(right<p.length()&&c[right]==c[right-left])
                	    			 right++;
                	    		 z[i]=right-left;
                	    		 right--;
            	    		 }
            	    	 }
            	    	  
            	     }*/
            		 int n=in.nextInt();
            		 int b[]=new int[n+1];int a[]=new int[n+1];
            		 int xor[]=new int[n+1];
            		 for(int i=1;i<=n;i++)
            		 {
            			 a[i]=in.nextInt();b[i]=a[i];
            			 xor[i]=(a[i]^xor[i-1]);
            			 
            		 }
            		 Arrays.sort(b);
            		 HashMap<Integer,Integer> hm=new HashMap();int c=1;
            		 for(int i=1;i<=n;i++)
            		 {
            			 if(!hm.containsKey(b[i]))
            				 hm.put(b[i],c++);
            			 else
            				 hm.put(b[i],hm.get(b[i]));
            		 }
            		 int q=in.nextInt();
            		 Pair query[]=new Pair[q];
            		 for(int i=0;i<q;i++)
            		 {
            			 query[i]=new Pair(in.nextInt(),in.nextInt(),i);
            		 }
            		 Arrays.sort(query);
            		 int ans[]=new int[q];
            		 int curr=0;
            		 int has[]=new int[1000005];
            		 
            		 for(int i=0;i<q;i++)
            		 {
            			 int l=query[i].l;
            			 int r=query[i].r;
            			 int ind=query[i].ind;
            			 while(curr<r)
            			 {
            				 curr++;
            				 int hmp=hm.get(a[curr]);
            				 if(has[hmp]>0)
            				 {
            					 update(1,1,n,has[hmp],0);
            				 }
            				 has[hmp]=curr;
            			      update(1, 1, n,curr,a[curr]);

            			 }
            			 ans[ind]=xor[r]^xor[l-1]^(find(1,1,n,l,r));
            		 }
            		 StringBuilder ans1=new StringBuilder();
            		 for(int i=0;i<q;i++)
            		 {
            			 ans1.append(ans[i]+"\n");
            		 }
            		 System.out.println(ans1);
                      
         	 }
         	 static int tre[]=new int[4000005];
         	 public static void update(int v,int tl,int tr,int index,int val)
         	 {
         		 if(tl==tr)
         		 {
         			 tre[v]=val;
         		 }
         		 else
         		 {
         			 int mid=(tl+tr)/2;
         			if(tl <= index &&index <= mid)
        	        {
        	            update(2*v,tl, mid, index, val);
        	        }
        	        else
        	        {
        	        	update(2*v+1,mid+1,tr, index, val);
        	        }
         			tre[v]=tre[2*v]^tre[2*v+1];
         		 }
         	 }
         	 public static int find(int v,int tl,int tr,int l,int r)
         	 {
         		if(r < tl || tr < l)
        	    {
        	        
        	        // range represented by a node is completely outside the given range
        	    	return 0;
        	    }
        	    if(l <= tl && tr<= r)
        	    {
        	        // range represented by a node is completely inside the given range
        	        return (tre[v]);
        	    }
        	    // range represented by a node is partially inside and partially outside the given range
        	    int mid = (tl + tr) / 2;
        	    int p1 = find(2*v, tl, mid, l, r);
        	    int p2 = find(2*v+1, mid+1, tr, l, r);
        	    return p1^p2;     
        
         	 }
         		public static void bfs(int x)
         	 {
         		 visited[x]=true;
         		 Queue<Integer> Q=new LinkedList<Integer>();
         		 Q.add(x);
         		 while(!Q.isEmpty())
         		 {
         			 int count=Q.size();
         			 while(count>0)
         			 {
         				 int p=Q.poll();
         				 visited[p]=true;
         				 for(int y:g[p])
         				 {
         					 if(!visited[y])
         					 {
         						 Q.add(y);
         					 }
         				 }
         				 count--;
         			 }
         		 }
         	 }
         	 public static void depth(int curr,int parent)
         	 {
         		 visited[curr]=true;
         		 for(int x:g[curr])
         		 {
         			 if(!visited[x])
         			 {
         				 depth[x]=depth[curr]+1;
         				 depth(x,curr);
         			 }
         		 }
         	 }
         	
         	 static int Par[]=new int[202];
         	 public static void Height(int cur,int par){
         		 Par[cur]=par;
         		 visited[cur]=true;
         		 int t=0;
         		 for(int x:g[cur])
         		 {
         			 if(!visited[x])
         			 { 
         				 t++;
         				 Height(x,cur);
         				 high[cur]=Math.max(high[cur], high[x]+1);
         			 }
         		 }
         		 if(t==0)
         		 {
         			 high[cur]=0;
         		 }
         	
         	 }
         	 static int dia[]=new int[202];
         	 static int high[]=new int[292];
         	 public static void Diameter(int curr,int parent)
         	 {
         		visited[curr]=true;
         		int trees=0;
         		ArrayList<Integer> set=new ArrayList();
         	
         		for(int x:g[curr])
         		{
         			if(!visited[x])
         			{
         				trees++;
         				Diameter(x,curr);
         				dia[curr]=Math.max(dia[curr],high[x]);
         				set.add(high[x]);
         			}
         		}
         		if(set.size()>=2)
         		{
         			Collections.sort(set,Collections.reverseOrder());
         			dia[curr]=Math.max(dia[curr],set.get(0)+set.get(1)+2);
         		}
         		else if(set.size()>0)
         		{
         			dia[curr]=Math.max(dia[curr],set.get(0)+1);
         		}
         		if(trees==0)
         		{
         			dia[curr]=0;
         		}
         
         	 }
         	 
              	 
         	 public static boolean IsPal(String s)
         	 {
         		 char c[]=s.toCharArray();
         		 for(int i=0;i<c.length/2;i++)
         		 {
         			 if(c[i]!=c[s.length()-1-i])
         				 return false;
         		 }
         		 return true;
         	 }
         	public static void Merge(long[] a,int p,int r){
                if(p<r){
                    int q = (p+r)/2;
                    Merge(a,p,q);
                    Merge(a,q+1,r);
                    Merge_Array(a,p,q,r);
                }
            }
            public static void Merge_Array(long a[],int p,int q,int r){
               long b[] = new long[q-p+1];
                long c[] = new long[r-q];
                for(int i=0;i<b.length;i++)
                    b[i] = a[p+i];
                for(int i=0;i<c.length;i++)
                    c[i] = a[q+i+1];
                int i = 0,j = 0;
                for(int k=p;k<=r;k++){
                    if(i==b.length){
                        a[k] = c[j];
                        j++;
                    }
                    else if(j==c.length){
                        a[k] = b[i];
                        i++;
                    }
                    else if(b[i]<c[j]){
                        a[k] = b[i];
                        i++;
                    }
                    else{
                        a[k] = c[j];
                        j++;
                    }
                }
            }
         	 
         	 
         	 
         	
         	
               
         	  public static void dfs1(int curr,int parent)
         	  {
         		  visited[curr]=true;
         		  
         		  for(int x:g[curr])
         		  {
         			  
         			  if(x==parent)continue;
         			  depth[x]=depth[curr]+1;
         			  up[x]=up[curr];
         			  if(h[x].contains(curr)){
         				  up[x]++;
         				  TotalUp++;
         			  }
         			  dfs1(x,curr);
         		  }
         	  }
         	 
                
                
                public static void dfs(int curr,int Parent)
                {
                	visited[curr]=true;
                	size[curr]=1;
                	parent[curr]=Parent;
                	count++;
                	if(value[curr]>0)
                	{
                		index=value[curr];
                	}
                	for(int x:g[curr])
                	{
                		if(!visited[x])
                		{
                			dfs(x,curr);
                			size[curr]+=size[x];
                		}
                	}
                }
                static long ncr(long a, long b){
        			if(b>a || b<0) return 0;
        			long f = (fact[(int) a]*modInverse(((fact[(int) b]*fact[(int) (a-b)])%MOD), MOD))%MOD;
        			return f;
        		}
        		static long modInverse(long a, long mOD2){
                    return  power(a, mOD2-2, mOD2);
        }
        static long power(long x, long y, long m)
        {
            if (y == 0)
                return 1;
            long p = power(x, y/2, m) % m;
            p = (p * p) % m;
         
            return (y%2 == 0)? p : (x * p) % m;
        }
         
                public static long gcd(long x, long y) {
            		if (x == 0)
            			return y;
            		else
            			return gcd( y % x,x);
            	}	
                public static long power(long a,long b)
        		{
        			long result=1;
        			while(b>0)
        			{
        				if(b%2==1)
        					result*=a;
        				a=a*a;
        				b/=2;
        			}
        			return result;
        		}
                static class Pair implements Comparable<Pair>{
                	    int l;int r;int ind;
                		Pair(int val,int index,int p){
                	     	this.l=val;
                			this.r=index;
                			this.ind=p;
                		}
                		@Override
                		public int compareTo(Pair o) {
                                 return (r-o.r);
                		}
                				
                	}
            	static class InputReader {
             
            		private InputStream stream;
            		private byte[] buf = new byte[8192];
            		private int curChar, snumChars;
            		private SpaceCharFilter filter;
             
            		public InputReader(InputStream stream) {
            			this.stream = stream;
            		}
             
            		public int snext() {
            			if (snumChars == -1)
            				throw new InputMismatchException();
            			if (curChar >= snumChars) {
            				curChar = 0;
            				try {
            					snumChars = stream.read(buf);
            				} catch (IOException e) {
            					throw new InputMismatchException();
            				}
            				if (snumChars <= 0)
            					return -1;
            			}
            			return buf[curChar++];
            		}
             
            		public   int nextInt() {
            			int c = snext();
            			while (isSpaceChar(c))
            				c = snext();
            			int sgn = 1;
            			if (c == '-') {
            				sgn = -1;
            				c = snext();
            			}
            			int res = 0;
            			do {
            				if (c < '0' || c > '9')
            					throw new InputMismatchException();
            				res *= 10;
            				res += c - '0';
            				c = snext();
            			} while (!isSpaceChar(c));
            			return res * sgn;
            		}
             
            		public long nextLong() {
            			int c = snext();
            			while (isSpaceChar(c))
            				c = snext();
            			int sgn = 1;
            			if (c == '-') {
            				sgn = -1;
            				c = snext();
            			}
            			long res = 0;
            			do {
            				if (c < '0' || c > '9')
            					throw new InputMismatchException();
            				res *= 10;
            				res += c - '0';
            				c = snext();
            			} while (!isSpaceChar(c));
            			return res * sgn;
            		}
             
            		public int[] nextIntArray(int n) {
            			int a[] = new int[n];
            			for (int i = 0; i < n; i++)
            				a[i] = nextInt();
            			return a;
            		}
             
            		public String readString() {
            			int c = snext();
            			while (isSpaceChar(c))
            				c = snext();
            			StringBuilder res = new StringBuilder();
            			do {
            				res.appendCodePoint(c);
            				c = snext();
            			} while (!isSpaceChar(c));
            			return res.toString();
            		}
             
            		public boolean isSpaceChar(int c) {
            			if (filter != null)
            				return filter.isSpaceChar(c);
            			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            		}
             
            		public interface SpaceCharFilter {
            			public boolean isSpaceChar(int ch);
            		}
            	}
            }
          
     

