seuOJ395 - 变石 Alexandrite

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2022

题目描述

咲弥在 Arcaea 世界中偶然寻得一些变石。出于好奇，她开始仔细端详这些神奇的石头，最终发现石头“变色”的秘密在于『折射』。

我们可以将变石看做由 $n\times m$ 个小晶格构成，规定左上角为 $(1,1)$、右下角为 $(n,m)$。对于一般的晶格，出射光与入射光保持方向不变；但其中一些特殊的晶格会对于从上、下、左、右这四个方向中某些方向入射的光产生折射，使得入射光改变方向、从该特殊晶格的另一方向射出（请参照输入格式中的折射规则，以及样例与图片解释进行理解）。这些晶格拼合在一起，最终使得变石产生奇异的色彩。

变石的结构实在太复杂了，所以咲弥请求你帮助她进行更加细致的研究。具体来说，对于所有从变石外表面不同位置垂直射入的 $2(n+m)$ 束光，最终会产生多少束不同位置与方向的出射光？

输入格式

第一行包含三个整数 $n$、$m$、$k$$(1\leq n,m\leq 10^5$，$0\leq k\leq min(10^5,4nm))$，分别表示晶格的行数、列数、特殊晶格的数量。

接下来 $k$ 行，每行包含 $4$ 个整数 $x_i$、$y_i$、$from_i$、$to_i$（$1\leq x_i\leq n$，$1\leq y_i\leq m$，$from_i, to_i\in \{0,1,2,3\}$）来描述一条折射规则，表示位置在第 $x_i$ 行第 $y_i$ 列的特殊晶格会将 $from_i$ 方向入射的光线折射至 $to_i$ 方向。对于 $from_i$ 与 $to_i$，$0$ 表示上方，$1$ 表示下方，$2$ 表示左方，$3$ 表示右方。一个特殊晶格可能存在多条折射规则，但保证这些折射规则的入射光线方向互不相同。

输出格式

输出一个整数，表示 $2(n+m)$ 种入射光会产生多少种不同位置与方向的出射光。

样例

样例输入1

2 2 3
1 1 1 2
2 2 3 0
1 2 0 3

样例输出1

5

样例输入2

1 2 6
1 1 1 3
1 1 0 3
1 1 2 3
1 2 1 2
1 2 0 2
1 2 3 2

样例输出2

0

数据范围与提示

样例解释见下图。