Khepel’s Problem

Khepel (also known as James the Cat, see figure 1) is a handsome cat starring in an old but well-known TV cartoon. He lives in an m × n rectangular garden with each cell being a unit-sized square. In order to keep the grass of the garden green and beautiful, sprinklers are placed in some of the cells. Each sprinkler can pour water in only one direction at each time instance. They continue watering for p seconds in each direction and then stop pouring water, rotate clockwise by 90 degrees (which itself takes 1 second of time) and start pouring water in the new direction. Also, each sprinkler has a specific range R which means that it can pour water on up to R cells away from its position in its current direction. Figure 1.Khepel trying to solve the problem A warm sunny day, Khepel decided to take a nap. But as you know, cats do not like to get wet with water. As a result, he asked you to help him. In other words, given the dimensions of his garden and the coordinates, original configuration, and the values of p and R for each sprinkler, you must write a program to calculate the number of cells in which he is able to sleep in his scheduled period of time (note that Khepel can not sleep in a cell containing a sprinkler). You must assume that all sprinklers start watering in their original direction in the beginning of time 0. Input Input consists of several test cases. The first line of each test case contains 3 integers 1 ≤ m, n ≤ 100 (the dimensions of the garden), and 0 ≤ k ≤ 1000 which is the number of sprinklers in it. The next k lines each consist of 4 non negative integers ri,ci,pi,Ri and a character di. 1 ≤ ri ≤ m and 1 ≤ ci ≤ n indicate the coordinates of the ith sprinkler in row-column format (with the upper leftmost cell having having coordinates (1, 1)), 1 ≤ pi ≤ 1, 000, 000 is its watering time in each direction, Ri ≥ 0 is its range, and finally, di is a character which indicates the original direction of the sprinkler in the beginning of time 0. The possible values of di are ‘N’ (for north), ‘S’ (for south), ‘E’ (for east), and ‘W’ (for west). The last line of each test case consists of two integers 0 ≤ a ≤ b ≤ 1, 000, 000, 000 indicating that Khepel would like to sleep from the start of time a until the end of time b. Input is terminated with a test case having n = m = k =O Output The output for each test case is a single integer which is the total number of cells in which Khepel is able to sleep from the start of time a until the end of time b. Sample Input 100 100 1 1 1 100 1 E 02 000 Sample Output 9998