ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest October'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Battleship

Time limit: 1.0 second
Memory limit: 64 MB
Once two friends Petya and Vasya decided to play “Battleship” at the lesson of computer science at school. Finishing place his ships on the field Petya fell to thinking how many ways of placing his last K-deck ship exist. He tried to calculate it quickly but soon lost a count. Then Petya looked around and suddenly saw computers (there's no surprise: the children played at the lesson of computer science, but by the moment Patya was carried away by the game so much that he didn't notice the computers). He thaught a bit and decided to write a program that would solve his problem. But so far as he was backward (it wasn't the first time that he played “Battleship” during the lesson) he didn't succeed. Please, help Petya with his problem.

Input

Problem illustration
The first line contains three numbers separated with a space — the vertical size of the playing field N (1 ≤ N ≤ 30000), the horizontal size of the field M (1 ≤ M ≤ 30000) and a number of already placed ships on the field L (0 ≤ L ≤ 30). Then follow L lines describing the ships location. Each description consists of three numbers and a letter separated with a space. The numbers are the coordinates of upper-left cell of a ship (the coordinates of upper-left cell of the playing field are (1,1)) and a number of ship decks. The letter defines the ship orientation (“V” — if it stands vertically, “H” — if horizontally). The last line contains the only positive integer K — the number of decks of the last ship that Petya wants to place.
We'll explain to those who has never played the “Battleship” that a i-deck ship is the rectangular of i × 1 cells. Ships may have from one to four decks. According to the standard rules of the game, no two ships may contact each other neither by their edges nor by the vertices.

Output

You should output the only number — an amount of different ways of placing the Petya's last K-deck ship.

Sample

inputoutput
4 4 2
1 2 2 V
3 1 2 H
2
4
Problem Author: Anton Botov and Anatoly Uglov
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session
To submit the solution for this problem go to the Problem set: 1212. Battleship