Treasure Hunt in the Alpaca Palace

Deep in the vast African desert, the brave Alpaca family lives in peace under the leadership of the revered AlpacaL.Sotomon (also known as the "King of Alpacas"). Over his lifetime, he defended his family against the brutal invasions of the "Crab Empire" and safeguarded a fortune of treasures. Being modest, he hid his treasure in an underground palace which is organized as a grid of $R \times C$ rectangular rooms. Among these rooms, exactly $N$ are treasure rooms equipped with a special teleportation portal. Rooms without treasures have no portal.

There are three types of portals installed in the treasure rooms:

1. Horizontal Gate (H): From this room, you can teleport to any other treasure room in the same row.
2. Vertical Gate (V): From this room, you can teleport to any other treasure room in the same column.
3. Any-direction Gate (A): From this room, you can teleport to any other treasure room in one of the 8 surrounding cells, i.e. in the 8 adjacent positions (if such a room exists).

Henry Curtis, an extremely clever (but greedy) treasure hunter, has obtained the palace blueprints which detail the position and type of each portal. Equipped with his portable teleportation device, he may choose any room of the palace to enter (and will use the device to exit after his journey), but once inside he can only travel through the in-room portals. There is no limit on the number of times the in-room portals may be used and rooms may be visited multiple times, though each treasure room is only counted once toward his haul.

Your task is to help Henry plan a route so that he can visit as many distinct treasure rooms as possible. If we model the treasure rooms as nodes in a directed graph (where an edge exists from room i to room j if room i's portal allows teleportation to room j), then your goal is to compute the maximum number of distinct nodes that can be visited in a path. Note that Henry may start at any treasure room.

Mathematically, if we number the treasure rooms from 1 to $N$ and let a directed edge exist from room i to room j if:

• Room i has a Horizontal Gate and the two rooms are in the same row, or
• Room i has a Vertical Gate and the two rooms are in the same column, or
• Room i has an Any-direction Gate and room j is one of the 8 adjacent cells surrounding room i (i.e. \( |r_i - r_j| \le 1 \) and \( |c_i - c_j| \le 1 \), with \( (r_i, c_i) \ne (r_j, c_j) \)).

Determine the maximum number of distinct treasure rooms that Henry can visit in such a route.

inputFormat

The first line contains three integers R, C and N (R, C are the number of rows and columns of the palace, and N is the number of treasure rooms) separated by spaces.

Then follow N lines, each containing two integers and a character: r c type. Here r and c (1-indexed) denote the row and column coordinates of a treasure room, and type is one of H, V or A representing the portal type in that room.

outputFormat

Output a single integer --- the maximum number of distinct treasure rooms that can be visited.

sample

3 3 1
2 2 H

1