在与危险的海外国家进行了多年漫长而艰苦的战争之后，我们的国家终于成功消灭了几乎所有的敌对势力，并取得了胜利。如此辉煌的胜利将在未来的许多年里被铭记和庆祝。因此，我们的国王决定将胜利之日定为法定假日，届时将举行胜利阅兵。在阅兵期间，国王将在军队的陪同下从他的皇宫出发，随后访问该国的所有城市。

国王及其随从将乘坐一种新型环保电动直升机旅行，该直升机的缺点是运行半径相对较短。国王要求你和你的顾问在一些农田和所有城市中建造直升机停机坪，以便从他的皇宫可以通过一系列在停机坪之间的短途飞行到达每个城市。然而，建造直升机停机坪和配套基础设施是昂贵的。因此，尽量减少建造直升机停机坪的农田数量是很重要的。

此外，由于直升机的特殊设计，国王和他的军队需要以一种特殊的模式移动，这可能会影响停机坪的数量和位置。

给你一张国家的矩形网格地图，它由农田网格、城市网格和国王皇宫网格组成。此外，还给出了直升机的移动模式——它可以像国际象棋中的车（Rook）、皇后（Queen）、主教（Bishop）、骑士（Knight）或国王（King）一样移动（移动方式见图示）。你的任务是确定必须建造直升机停机坪的农田网格和城市网格的最小数量，以满足上述条件。拥有国王皇宫的网格已经有一个停机坪，不需要新建。

图 1：直升机特定移动模式的说明

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 15$），其中 $N$ 是表示我们国家的网格的行数，$M$ 是列数。

输入的第二行包含两个整数 $X$ 和 $Y$（$1 \le X \le N, 1 \le Y \le M$），表示国王皇宫的位置，随后是一个字符，表示移动模式（“R” — 车，“Q” — 皇后，“B” — 主教，“N” — 骑士，“K” — 国王）。

输入的第三行包含一个整数 $T$（$1 \le T \le 10$），表示国家中的城市数量。

接下来的 $T$ 行，每行包含两个整数 $W$ 和 $Z$（$1 \le W \le N, 1 \le Z \le M$）。每行表示一个城市网格的位置。所有城市占用的网格互不相同，且没有城市占用皇宫网格。所有不表示城市或皇宫的网格都被视为农田。

输出格式

输出一个整数 — 建造直升机停机坪所需的农田/城市网格的最小数量。如果国王和他的军队不可能访问所有城市，则输出 $-1$。

样例

输入样例 1

3 3
3 1 K
2
1 1
1 3

输出样例 1

3

输入样例 2

3 3
3 1 Q
2
1 1
1 3

输出样例 2

2

输入样例 3

5 5
4 4 R
4
1 2
2 1
2 5
5 1

输出样例 3

6