题目背景

窗外的雪地里我见到一只很小很小的青蛙，眨巴一只眼睛，另一只眼圆睁睁，一动 不动，直望着我。我知道这就是上帝。 他就这样显示在我面前，只看我是不是领悟。 他用一只眼睛在同我说话，一张一合，上帝同人说话的时候不愿人听到他的声音。 我也毫不奇怪，似乎就应该这样，仿佛上帝原来就是只青蛙，那一只聪明的圆眼睛 一眨不眨。他肯审视我这个可怜的人，就够仁慈的了。 他另一只眼，眼皮一张一合在讲人类无法懂得的语言，我应该明白，至于我是否明 白，这并不是上帝的事情。 我尽可以以为这眨动的眼皮中也许并没有什么意义，可它的意义也许就正在这没有 意义之中。 没有奇迹。上帝就是这么说的，对我这个不知餍足的人说。 那么，还有什么可追求的？我问他。 ——高行健《灵山》

题目描述

给定 n 行 m 列的棋盘上的 q 个矩形。记第 r 行第 c 列的格子为 (r, c)。 考虑一个 nm 个结点的有向无环图，图中每个结点对应棋盘上的一个格子。从格子 (r1, c1) 的结点到格子 (r2, c2) 的结点有边，当且仅当 r1 < r2, c1 < c2，且存在一个给出 的矩形同时包含 (r1, c1) 和 (r2, c2)。

定义路径长度为路径包含的结点个数。求出图中的最长路径，以及长度最长的路径 共有多少条。路径条数对 10^9 + 7 取模。

输入格式

第一行一个整数 T，表示数据组数。

接下来 T 组数据，每组数据格式如下：

• 第一行三个整数 n, m, q。

• 接下来 q 行，每行四个整数 r1, c1, r2, c2，表示包含满足 x ∈ [r1, r2], y ∈ [c1, c2] 的 所有格子 (x, y) 的矩形。

输出格式

T 行，每行两个整数，表示最长路径的长度，以及路径条数对 10^9 + 7 取模的值。

样例输入1

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

样例输出1

3 2
3 1
2 4

样例1解释

对于第一组数据，图中有 4 条边： • 由第 1 个矩形产生的：(1, 1) → (2, 2)。 • 由第 2 个矩形产生的：(2, 2) → (3, 3),(2, 2) → (3, 4),(2, 3) → (3, 4)。 图中没有长度超过 3 的路径，而长度等于 3 的路径有 (1, 1) → (2, 2) → (3, 3) 和 (1, 1) → (2, 2) → (3, 4)。

样例2/3

见下发文件.

数据范围

保证 1 ≤ T ≤ 10^5, 1 ≤∑nm ≤ 1.2 × 10^7, 1 ≤∑q ≤ 5 × 10^5。

对于每组数据，保证 1 ≤ n, m ≤ 2 × 10^3, 1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m。

• 子任务 1（10 分）：T ≤ 100, n, m, q ≤ 10。

• 子任务 2（20 分）：T ≤ 100, n, m, q ≤ 100。

• 子任务 3（10 分）：T = 1, n = m = 2 × 10^3, q = 10^5 且 r1, r2, c1, c2 随机生成。

• 子任务 4（30 分）：∑nm ≤ 7 × 10^5,∑q ≤ 2.5 × 10^5。

• 子任务 5（30 分）：无特殊限制。