题目描述

雅娜（Yana）是一位生活在童话国度里的海盗。她的国家可以表示成一个 n x m 的网格，行编号为 0 到 n-1，列编号为 0 到 m-1。

这个国家遵循一个古怪的规则：

• 当且仅当 i & j = 0 时，单元格 (i, j) 是陆地；
• 否则，该单元格是海洋。

这里的 & 表示按位与运算，即对两个数对应二进制位逐位进行逻辑与后得到的新数。

一个岛屿是一个由陆地格子组成的集合，满足：

• 集合内任意两个格子之间都可以通过若干次“上下左右”相邻移动到达；
• 移动过程中只能经过集合中的格子；
• 并且这个集合在包含关系意义下是极大的，也就是说，不能再加入任何一个与其相邻的陆地格子。

现在，雅娜有 q 个问题。每个问题形如：

如果她的国家只保留行区间 [a_i, c_i] 和列区间 [b_i, d_i] 所构成的子矩形，那么该子矩形中会有多少个岛屿？

请你编写程序 islands，回答所有问题。

输入格式

第一行输入三个整数 n, m, q，表示国家的大小以及问题个数。
接下来 q 行，每行输入四个整数 a_i, b_i, c_i, d_i，定义第 i 个询问对应的子矩形。

输出格式

输出 q 行，按输入顺序依次给出每个询问的答案。

数据范围

• 1 <= n, m <= 10^9
• 1 <= q <= 10^5
• 0 <= a_i <= c_i < n
• 0 <= b_i <= d_i < m

子任务

只有当某个子任务及其所依赖的全部子任务全部通过时，才能获得该子任务的分数。

样例

输入

6 5 4
0 0 3 2
0 2 1 3
0 1 2 4
5 4 5 4

输出

1
1
2
0

说明

下列图示分别标出了雅娜四个询问所对应的区域：

• 询问 (0, 0, 3, 2)
• 询问 (0, 2, 1, 3)
• 询问 (0, 1, 2, 4)
• 询问 (5, 4, 5, 4)

以上四个询问对应的子矩形区域。