SOLVE

LATER

Distinct Integers in Range

/

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 \le N \le 10^5$$

$$1 \le A[i], B[i] \le 5000$$

$$1 \le Q \le 10^5$$

$$1 \le a \le b \le N$$

$$1 \le c \le d \le N$$

Explanation

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.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
1024 MB

Source Limit:
1024 KB

Initializing Code Editor...