题目描述

给定一个 $n$ 行 $n$ 列且值域为 $[1,n]$ 的正整数方阵 $a$ 和 $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$。

对于每个询问，你需要回答集合 $A=\{a_{i,j}\mid l_1\le i\le r_1,\ l_2\le j\le r_2\}$ 的大小。

输入格式

第一行输入一个正整数 $n$，表示方阵大小与值域上界。

接下来 $n$ 行每行输入 $n$ 个正整数，表示方阵 $a$。

接下来一行输入一个正整数 $q$，表示询问个数。

接下来 $q$ 行每行输入四个正整数 $l_1,r_1,l_2,r_2$，表示询问参数。

输出格式

输出 $q$ 行每行一个整数表示答案。

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

1
2
2
3
3

提示

样例一解释

对于这五个询问，集合 $A$ 分别为 $\{1\},\{1,2\},\{2,3\},\{1,2,3\},\{1,2,3\}$。

样例二

见下发文件下的 genshin2.in 与 genshin2.ans。

该样例约束与测试点 $1,3$ 一致。

样例三

见下发文件下的 genshin3.in 与 genshin3.ans。

该样例约束与测试点 $13$ 一致。

样例四

见下发文件下的 genshin4.in 与 genshin4.ans。

该样例约束与测试点 $17,19$ 一致。

数据范围

测试点编号	$n=$	$q=$	$r_1-l_1<$
$1\sim 4$	$30$	$5\times 10^5$	$n$
$5\sim 7$	$200$
$8$	$500$
$9\sim 12$	$1500$
$13\sim 14$	$2000$	$10^4$
$15\sim 16$		$5\times 10^4$
$17\sim 19$	$1998$	$5\times 10^5$	$1$
$20\sim 21$	$1999$		$20$
$22\sim 25$	$2000$		$n$

对于编号为奇数的测试点，由所有满足限制的输入数据中等概率随机抽取得到。

对于所有数据，保证 $30\le n\le 2000$，$10^4\le q\le 5\times 10^5$，$1\le a_{i,j}\le n$，$1\le l_i\le r_i\le n$。

提示

本题输入输出规模较大，请使用较为快速的输入输出方式。