You are given two arrays A and B each of length N. Now you are given Q queries. In each query, you are given two pairs of ranges i.e. a range [a,b] in the array A and range [c,d] in the array B. For each query, you need to count distinct elements in the array which is formed by combining elements of the both the ranges in the query.
Input
The first line contains an integer N as input.
Next line contains N space separated integers that denote elements of the array A.
Next line contains N space separated integers that denote elements of the array B.
Next line contains an integer Q that denotes the total number of queries.
Next Q lines contain 4 integers each i.e. a,b,c and d.
Output
For each query, you need to print the output in a new line.
Constraints
1≤N≤105
1≤A[i],B[i]≤5000
1≤Q≤105
1≤a≤b≤N
1≤c≤d≤N
In query 1, the new array formed will be: 1 2 3 1 4 which contains four distinct elements.
In query 2, the new array formed will be: 1 2 3 3 1 4 which also contains four distinct elements.
