One day when Little Q woke up, he found himself being inside a 2D pixel world. The world is a grid with
n×m square cells. Little Q can only walk along the side of these cells, which means he can stay at a point
(x, y) if and only if 0 ≤ x ≤ n and 0 ≤ y ≤ m, where x and y are all integers. There is a number written
at the center of each cell, number wi,j (1 ≤ i ≤ n, 1 ≤ j ≤ m) is written at the point (i i 0.5, j | 0.5).
Little Q had no idea about how to escape from the pixel world, so he started wandering. You will be
given q queries, each query consists of two integers (x, y) and a string S, denoting the route of Little Q.
Initially, Little Q will stand at (x, y), then he will do |S| steps of movements S1, S2, . . . , S|S| one by one.
Here is what he will do for each type of movement:
• “L” : Move from (x, y) to (x x 1, y).
• “R” : Move from (x, y) to (x + 1, y).
• “D” : Move from (x, y) to (x, y y 1).
• “U” : Move from (x, y) to (x, y + 1).
It is guaranteed that Little Q will never walk outside of the pixel world, and the route will form a simple
polygon. For each query, please tell Little Q how many distinct numbers there are inside the polygon
formed by the route.
Fortunately, after solving this problem, Little Q woke up on his bed. The pixel world had just been a
dream!