Folding Game

Time limit1sMemory limit128 MB

Summary
For each fold sequence on a rectangle, count how many paper layers sit under a given point.
Level

Medium5 of 10

Topics
Simulation, Implementation, Geometry, Recursion
Solved
No attempts yet

Problem

Alice places a rectangular sheet of paper in front of Bob. The paper has width WW and height HH and lies flat. Alice then folds the paper NN times. Each fold is either horizontal or vertical: a horizontal fold leaves a rectangle of the same width WW but smaller height, and a vertical fold leaves a rectangle of the same height HH but smaller width.

When the folding is done, Alice presses a finger onto some point of the resulting rectangle and asks: how many layers of paper lie directly beneath her finger?

Input

The input contains several test cases. Each test case begins with a line of three integers

W H N

where WW and HH (0<W,H≤1060 < W, H \le 10^6) are the width and height of the paper and NN (0≤N≤200 \le N \le 20) is the number of folds. Both WW and HH are even. Each of the next NN lines contains a letter and a number separated by one space

D K

The capital letter DD is one of T, B, L, R, telling whether the fold comes from the Top, Bottom, Left, or Right. The number KK gives the position of the fold, measured from that edge; for instance, if DD is T, Alice lifts the top edge and folds it downward. KK always lies on the paper and is even. The final line of each test case contains two integers

X Y

the point where Alice puts her finger, measured from the bottom-left corner: XX is the distance to the right and YY is the distance upward. The point (X,Y)(X, Y) is guaranteed to lie on the fully folded paper, and both XX and YY are odd. Because WW, HH, and every KK are even, this guarantees that (X,Y)(X, Y) never lies exactly over an edge or a fold. The input ends with a line containing three zeros.

Output

For each test case, output a single integer on its own line: the number of layers of paper at the point (X,Y)(X, Y). Do not print extra spaces, and do not separate the answers with blank lines.

Examples1

  1. Example 1

    Input
    10 10 1
    B 4
    5 1
    10 10 1
    B 4
    7 5
    10 10 1
    T 6
    3 1
    10 10 1
    T 6
    9 3
    14 10 2
    L 4
    R 4
    3 3
    0 0 0
    
    Expected output
    2
    1
    1
    2
    3