Distinct Integers in Range
/

## Advanced Data Structures, Bit Manipulation, Data Structures, Segment Trees

Problem
Editorial
Analytics

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$

SAMPLE INPUT
5
1 2 3 4 5
2 1 3 1 4
2
1 3 4 5
1 3 3 5
SAMPLE OUTPUT
4
4

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

## This Problem was Asked in

Initializing Code Editor...
Notifications

?