Minimizing Superpower Usage in Soldier Relocation

Xiao Ming has a box of toy soldiers: there are K infantry, K cavalry and one heavenly soldier, for a total of 2K+1 soldiers. He also has an M×N chessboard. Each cell (i,j) has a height \(H_{i,j}\). Initially, all soldiers are placed on some cells of the board. Then, Xiao Ming picks exactly one target cell (from a set of pre‐selected cells, though in this problem the set size is 1) and assigns it a required count \(R\) such that \(R = 2K+1\). The goal is to move every soldier to the target cell using moves along the four cardinal directions (north, east, south, west) obeying the following restrictions:

• Infantry can only move from a cell \(A\) to an adjacent cell \(B\) if \(H_A \le H_B\) (i.e. they only climb up or move on flat ground).
• Cavalry can only move from \(A\) to \(B\) if \(H_A \ge H_B\) (i.e. they only jump down or on flat ground).
• Heavenly soldier can move without any restriction.

Noticing that the game can be extremely difficult, Xiao Ming is allowed to use a "superpower". Each use of the superpower does not move any soldier but allows an arbitrary number of swap operations between any two soldiers (swapping their positions). By using this, he may reassign soldier types among the starting positions. However, he wishes to minimize the number of times he uses this superpower.

Your task is to determine the minimum number of superpower uses needed so that all soldiers can eventually reach the target cell under the movement restrictions. Moves are done individually (one cell step at a time) and a soldier may move along any valid path. Without using any superpower, each soldier must travel from its given starting cell following the rule corresponding to its type. With one superpower usage, you are allowed to reassign soldier types arbitrarily among the starting positions (each position can hold only one soldier) before starting the moves. (Note that even after the swap, the soldier’s move restrictions are determined by the type assigned to that starting cell.)

If it is possible to achieve the goal without any superpower use, output 0. Otherwise, if a single superpower usage suffices (i.e. there exists an assignment of soldier types to starting positions that allows all soldiers to reach the target cell), output 1. If it is impossible altogether, output -1.

Note: For each move the soldier moves one cell in the four cardinal directions and cannot leave the board. All paths are considered with respect to the movement rules for each soldier type.

The conditions for movement can be summarized in LaTeX as follows:

• Infantry: A soldier can move from cell \(A\) to cell \(B\) if and only if \(H(A) \le H(B)\).
• Cavalry: A soldier can move from cell \(A\) to cell \(B\) if and only if \(H(A) \ge H(B)\).
• Heavenly: A soldier can move freely to an adjacent cell.

inputFormat

The input consists of:

1. Two integers M and N — the number of rows and columns of the board.
2. M lines, each containing N integers: the height matrix \(H\), where the \(j\)-th number in the \(i\)-th line is \(H_{i,j}\).
3. An integer K (\(K \ge 1\)). There are \(2K+1\) soldiers in total.
4. Next \(2K+1\) lines: each line contains three items: two integers r and c (the 1-indexed coordinates of the cell where a soldier is placed) and a character representing the soldier type, which can be I (infantry), C (cavalry) or T (heavenly).
5. One line with three integers: r_t, c_t and R, representing the 1-indexed coordinates of the target cell and its required number of soldiers. It is guaranteed that \(R = 2K+1\).

All values are space‐separated.

outputFormat

Output a single integer: the minimum number of superpower usages required to achieve the goal. Output 0 if possible without superpower, 1 if one usage is sufficient, and -1 if it is impossible.

sample

3 3
1 2 3
2 3 4
3 4 5
1
1 1 I
3 3 C
2 2 T
3 1 3

0