Số Nguyên Khác Nhau Trong Đoạn

Trong một dự án thủy lợi, FullHouse Dev được giao nhiệm vụ phân tích dữ liệu từ các cảm biến đo lường. Họ nhận được hai mảng số liệu và cần xác định số lượng giá trị khác nhau trong các đoạn được chỉ định.

Bài toán

Cho hai mảng \(A\) và \(B\), mỗi mảng có độ dài \(N\). Tiếp theo là \(Q\) truy vấn, mỗi truy vấn gồm hai cặp chỉ số xác định một đoạn trong mảng \(A\) (từ \(L_1\) đến \(R_1\)) và một đoạn trong mảng \(B\) (từ \(L_2\) đến \(R_2\)). Với mỗi truy vấn, hãy đếm số phần tử khác nhau trong mảng được tạo thành bằng cách kết hợp các phần tử từ cả hai đoạn đã cho.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa \(N\) số nguyên là các phần tử của mảng \(A\)
• Dòng thứ ba chứa \(N\) số nguyên là các phần tử của mảng \(B\)
• Dòng thứ tư chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L_1\), \(R_1\), \(L_2\), \(R_2\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra một số nguyên trên một dòng - số lượng phần tử khác nhau trong mảng kết hợp.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq L_1 \leq R_1 \leq N\)
• \(1 \leq L_2 \leq R_2 \leq N\)

Ví dụ

INPUT

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

OUTPUT

4
4

Giải thích

• Ở truy vấn 1: mảng mới được tạo thành là: 1 2 3 1 4, có bốn phần tử khác nhau.
• Ở truy vấn 2: mảng mới được tạo thành là: 1 2 3 3 1 4, cũng có bốn phần tử khác nhau.