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.

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.

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