题目描述

有 $n$ 位同学，编号从 $1$ 到 $n$。

他们参加了两轮考试。

已知：第 $i$ 位同学在第一轮考试的排名为 $a_i$，在第二轮考试的排名为 $b_i$。

接下来有 $q$ 次询问，每次询问包含四个整数 $l_1, r_1, l_2, r_2$（$1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$），对于每次询问，你需要回答出有多少位同学第一轮考试的排名在 $[l_1, r_1]$ 之间，同时第二轮考试的排名在 $[l_2, r_2]$ 之间 —— 即统计有多少下标 $i$ 同时满足 $l_1 \le a_i \le r_1$ 且 $l_2 \le b_i \le r_2$。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$，表示同学人数。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$（是一个 $1 \sim n$ 的排列），其中 $a_i$ 表示第 $i$ 位同学在第一轮考试中的排名。

第三行，$n$ 个整数 $b_1, b_2, \ldots, b_n$（是一个 $1 \sim n$ 的排列），其中 $b_i$ 表示第 $i$ 位同学在第二轮考试中的排名。

第四行，一个整数 $q(1 \le q \le 2 \times 10^5)$，表示询问次数。

接下来 $q$ 行，每行包含四个整数 $l_1, r_1, l_2, r_2$，表示一次询问（$1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$）。

输出格式

对于每次询问，输出一行，包含一个整数，表示第一轮测试的排名在 $[l_1, r_1]$ 之间，同时第二次测试的排名在 $[l_2, r_2]$ 之间的学生人数。

样例

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

1
3
3

10
4 2 5 3 8 7 10 1 9 6
7 1 3 2 8 6 9 5 4 10
8
1 8 3 9
2 5 4 9
8 8 8 8
1 3 9 10
1 5 6 10
1 5 1 5
1 4 5 10
1 10 1 10

5
1
1
0
1
4
2
10

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n, q \le 1000$
• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$a, b$ 均为 $1 \sim n$ 的排列，$1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$