你在一个 $n \times m$ 的网格上放置了胶水，以创建一个矩形跳蚤陷阱。每个胶水都有一个“弱方向”；如果跳蚤在胶水上并向其弱方向跳跃，它就能跳出该胶水。

更准确地说，每个胶水用 U、D、L 或 R 表示，分别代表向上、向下、向左和向右。在单次跳跃中，跳蚤可以沿弱方向移动最多 $k$ 个单元格。如果跳蚤跳出了矩形范围，我们称该跳蚤已逃脱。

你对陷阱的效率感到好奇。如果放置在陷阱某个单元格上的跳蚤可以通过连续跳跃逃脱，我们称该单元格为“可逃脱单元格”。你的任务是计算可逃脱单元格的数量。

输入格式

输入的第一行包含三个整数：陷阱的大小 $n$ 和 $m$ 以及跳跃限制 $k$ ($1 \le n, m, k \le 2000$)。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，由字母 U、D、L 和 R 组成。这些行表示每个胶水的弱方向。

输出格式

输出可逃脱单元格的数量。

样例

输入 1

5 5 2
DDDRD
DDDDD
RDLUL
UURUU
UUUUU

输出 1

14

说明

起始位置为 $(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4)$ 和 $(5, 5)$ 的跳蚤可以逃脱。例如：

• 位于 $(1, 3)$ 的跳蚤可以通过以下路径逃脱： $(1, 3) \to (2, 3) \to (4, 3) \to (4, 4) \to (3, 4) \to (1, 4) \to$ 跳出陷阱
• 位于 $(1, 4)$ 的跳蚤可以通过向右跳跃两个单元格逃脱。