太空海盗 Krys 船长最近获得了一张人工建造且戒备森严的 Alpha-Zet 行星地图，他计划去那里掠夺一番。事实证明，整个行星建立在一个二维平面上，由若干个模块组成，每个模块作为一个房间。在每一对整数坐标处都有且仅有一个模块，每个模块的大小恰好为 $1 \times 1$。每个模块都与至少一个相邻模块双向连通。此外，对于任意两个模块，它们之间存在且仅存在一条路径。总而言之，这些模块构成了一个没有环的矩形迷宫。

在地图上，Krys 船长标记了他想要访问的若干模块，并要求按标记的顺序进行访问。他去那里打算做什么与你无关，但他承诺，如果你能算出他沿途必须经过的模块总数（由于没有环，他总是会沿着从一个标记模块到下一个标记模块的直接路径行进），他就会给你一笔财富。第一个标记的模块表示他旅程的起点，最后一个表示他想要到达的终点。

输入格式

输入包含：

• 一行包含两个整数 $h$ 和 $w$ ($2 \le h, w \le 1000$)，描述迷宫的高度和宽度。
• 接下来 $h + 1$ 行，用 ASCII 字符描述迷宫，每行包含 $2 \cdot w + 1$ 个字符。描述始终遵循以下规则：
  • 在每一行中，奇数索引（从 1 开始）的列包含垂直墙或空格，偶数索引的列包含水平墙或空格。
  • 第一行描述迷宫的北墙（始终仅由水平墙组成）。随后的每一行描述一行模块。
  • 每个偶数列索引处都有一个模块。它的西墙和东墙分别位于相邻的奇数列索引处，它的北墙位于同一列索引但上一行的位置，它的南墙位于其自身位置。如果墙缺失，则相应位置包含一个空格。
• 迷宫描述之后，给出一个整数 $m$ ($2 \le m \le 10^4$)。
• 接下来的 $m$ 行，每行描述一个标记的模块，包含两个整数坐标 $x$ 和 $y$ ($1 \le x \le h; 1 \le y \le w$)。第一对坐标是旅程的起点，最后一对是终点。模块可能会多次出现，但不会连续两次或多次出现。$(1, 1)$ 是左上角的模块，$(h, w)$ 是右下角的模块。

保证迷宫本身是封闭的。此外，保证任意两个模块之间存在且仅存在一条路径。

输出格式

输出一个整数，表示 Krys 船长按照输入给定的顺序行进时，必须经过的模块总数。

图 A.1：样例 2 的示意图

样例

样例输入 1

2 6
 _ _ _ _ _ _
| _ _ _ _ _|
|_ _ _ _ _ _|
5
1 5
1 1
1 6
1 1
1 5

样例输出 1

18

样例输入 2

5 5
 _ _ _ _ _
|_ _ |_ |
| _| | _|
| |_ _| |
| _ _ |
|_|_ _ _|_|
7
4 4
1 4
3 1
4 5
1 2
2 2
5 4

样例输出 2

43