Battleship P19727

0.67 Ann and Bob like to play a variant of Battleship. First, they agree on the number of rows $r$ and the number of columns $c$ of a rectangular grid, and also on a length $m$. Afterwards, Ann decides a place to hide exactly one ship of size $1 \times m$ completely inside the grid, either horizontally or vertically. Then, Bob tries to sink Ann’s ship by shoting at $n$ cells of the grid. For every shot, Ann must say if the ship has been hit, or if the shot has been a miss.

0.33

You are looking at one game between Ann and Bob, and you suspect that Ann is cheating. To confirm or refute your suspicions, please count the number of positions where the ship could be placed according to Ann’s answers.

Input

Every case begins with $r$, $c$, $m$ and $n$. Follow $n$ triples $i, j, x$, where $1 \le i \le r$ is the row of the shot, $1 \le j \le c$ is the column of the shot, and $x$ is a character that is ‘h’ or ‘m’ depending on whether the shot is a hit or a miss according to Ann. Assume $1 \le r \le 10^8$, $1 \le c \le 10^8$, $2 \le m \le 100$, and $0 \le n \le 10^5$. The coordinates of all the shots are different.

Output

For every case, print the number of possible locations of the ship hidden by Ann. If this number is 0 or if Ann’s answers are clearly wrong, print “Ann is cheating.”.