Problem Description

Translated from [CERC2018] The Lord of the Kings

After years of war with foreign countries, our nation has finally succeeded in eliminating most of the reactionary forces and enemies. Such a glorious victory should be remembered and celebrated for a long time. Therefore, our king has declared that the day of victory will be designated as a public holiday and a victory parade will be held. In the parade, the army will follow the king from his palace to visit every city in the country.

The king and his entourage will use an environmentally friendly electric helicopter as their mode of transportation. This helicopter has a drawback, which is its short range. The king asks you and your advisors to build helipads in some farms and all cities, so that from his palace, after passing through some helipads, he can reach any city. However, building helipads and infrastructure is very costly. Therefore, the goal is to minimize the number of helipads built.

Additionally, due to the special design of the helicopter, the king and his soldiers need to move in a special way, which will affect the number and location of the helipads.

You are given a rectangular grid map of the country, which includes grids representing villages, cities, and the palace. You are also given the movement pattern of the helicopter, which is the same as one of the pieces in chess: "Rook," "Queen," "Bishop," "Knight," or "King" (the detailed movement patterns of each piece can be found in the "Data Range and Hints"). Your task is to determine the minimum number of helipads that need to be built in farms or cities to meet the king's requirements. A helipad has already been built in the king's palace, so no new one needs to be built there.

Input Format

The first line contains two integers $N, M$, representing the country's grid size of $N$ rows and $M$ columns.

The second line contains two integers $X, Y$, representing the location of the king's palace, followed by a character indicating the movement pattern (R - Rook, Q - Queen, B - Bishop, N - Knight, K - King).

The third line contains an integer $T$, representing the number of cities in the country.

The next $T$ lines contain two integers $W, Z$, representing the location of a city. All cities are on different grids, and no city is on the same grid as the palace. All grids that do not represent a city or the palace are farms.

Output Format

Output a single integer representing the minimum number of helipads that need to be built. If it is impossible for the king and his soldiers to reach every city, output $-1$.

Sample Input and Output

Sample Input #1

3 3
3 1 K
2
1 1
1 3

Sample Output #1

3

Sample Input #2

3 3
3 1 Q
2
1 1
1 3

Sample Output #2

2

Sample Input #3

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

Sample Output #3

6

Notes

$1 ≤ N, M ≤ 15, 1 ≤ T ≤ 10, 1 ≤ X, W ≤ N, 1 ≤ Y, Z ≤ M$

The following diagram shows the movement patterns of the helicopter (similar to the corresponding chess piece's movement rules):

见题面 Input 部分

见题面 Output 部分