该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

「$\red{Tea Chess}$」是 $\red{TeaLand }$上非常流行的一种棋类游戏，两个玩家各有一张 $\red{n \times n }$的 棋盘，每个格子上有一枚勇士棋，也就是说，总共有 $\red{n^2 }$枚勇士棋。

每一枚勇士棋都有一个战斗力，而勇士棋的位置与战斗力决定了玩家在这场对弈中 的优势与否。由于规则非常复杂，我们可以简单地认为一个矩形区域内战斗力不低于某 个值的勇士棋是比较关键的。

所以，小 $\red{T }$给你展示了他现在的棋盘，然后会对你进行 $\red{Q }$次询问，每次询问从 $\red{(a, b)}$ 到 $\red{(c, d) }$的矩形区域的 $\red{(c - a + 1)(d - b + 1) }$枚棋子中，有多少枚棋子的战斗力是不低于 $\red{x }$的。

输入格式

第一行一个正整数 $\red{n}$。

之后 $\red{n }$行，每行 $\red{n }$个整数，第 $\red{i }$行第 $\red{j }$个数表示位于 $\red{(i, j) }$的勇士棋的战斗力 $\red{a_{ij}}$。

之后一行一个正整数 $\red{Q}$。

之后 $\red{Q }$行，每行五个正整数 $\red{a, b, c, d, x}$。

输出格式

对于每个询问，输出答案。

样例

输入样例

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

输出样例

9
3
16
1
2

提示

对于 $\red{30\% }$的数据保证 $\red{Q ≤}$ $\red{10}$。

对于另外 $\red{20\% }$的数据保证 $\red{a_{ij} ≤}$ $\red{1}$。

对于所有测试点保证 $\red{1 ≤}$ $\red{n ≤}$ $\red{10^3，}$$\red{1 ≤}$ $\red{Q ≤}$ $\red{10^5，}$$\red{0 ≤}$ $\red{a_{ij} , x ≤}$ $\red{9，}$$\red{1 ≤}$ $\red{a ≤}$ $\red{c ≤}$ $\red{n，}$ $\red{1 ≤}$ $\red{b ≤}$ $\red{d ≤}$ $\red{n}$。

注意，本题读入量较大，建议使用较快的读入方式。