Однажды в школе на уроке информатики Петя и Вася решили сыграть в морской бой. Заканчивая расставлять свои корабли на листочке, Петя задумался: ему вдруг стало интересно, сколькими различными способами он сможет поставить свой последний K-палубный кораблик? Он попробовал быстро посчитать количество способов, но скоро сбился со счета. Тогда Петя посмотрел по сторонам и, неожиданно для себя, увидел стоящие повсюду компьютеры (в этом нет ничего удивительного, ведь, как мы помним, дело было на уроке информатики; но до этого момента Петя был так увлечен подготовкой к игре, что компьютеров не замечал). Подумав немного, он решил написать программу, которая может решить его задачу. Но у него ничего не получилось, поскольку он был двоечником — он отнюдь не первый раз в своей жизни играл в морской бой на уроке! Помогите Пете в его нелегком деле.

В первой строке содержатся три числа, разделённые пробелами: размер поля по вертикали N (1 ≤ N ≤ 30000), размер поля по горизонтали M (1 ≤ M ≤ 30000) и количество уже поставленных кораблей L (0 ≤ L ≤ 30). Далее следуют L строк с описанием расставленных кораблей. Описание каждого корабля состоит из записанных через пробел трёх чисел и буквы. Числа — это координаты левого верхнего угла корабля (левая верхняя клетка игрового поля имеет координаты (1, 1)) и количество палуб корабля. Буква же задает ориентацию корабля («V» — если корабль стоит вертикально и «H» — если горизонтально). В последней строке содержится число K — количество палуб корабля, который нужно поставить Пете.

Для тех, кто никогда не играл в морской бой, поясним, что i-палубный корабль — это прямоугольник размером i × 1 клеточку. Корабли могут иметь от одной до четырёх палуб. По правилам игры корабли не могут касаться друг друга рёбрами или вершинами.

Выведите количество различных способов, которыми Петя может разместить на поле K-палубный корабль.