9441: 2D Travel

There is a robot in the 2D rectangular region $W = \{(x,y) \; | \; 0\le x \le n, 0\le y \le m\}$. Assume that the robot is at $(x,y)$ currently, it can move in the following four directions: - U : go from $(x,y)$ to $(x,y+1)$ if $(x,y+1) \in W$; - D : go from $(x,y)$ to $(x,y-1)$ if $(x,y-1) \in W$; - L : go from $(x,y)$ to $(x-1,y)$ if $(x-1,y) \in W$; - R : go from $(x,y)$ to $(x+1,y)$ if $(x+1,y) \in W$. An instruction contains a character $c$ of \`\`U'', \`\`D'', \`\`L'', \`\`R'' and an integer $t\,(1 \le t \le 10^9)$, indicating that the robot moves in the direction $c$ for $t$ times consecutively under the instruction. Given a list of instructions of length $k$, there are $q$ queries, you should report the final position and the length of the moving route if the robot starts moving from the given position $(x,y)$ and does the $l$\-th, $(l+1)$\-th, $(l+2)$\-th, ..., $r$\-th instructions one by one for each query.

The first line contains four integers $n, m\,(1 \le n, m \le 10^9)$, $k, q\,(1 \le k, q \le 10^5)$, denoting the size of the rectangular region, the number of instructions, and the number of queries respectively. Each of the following $k$ lines contains a character $c$ of \`\`U'', \`\`D'', \`\`L'', \`\`R'' and an integer $t\,(1 \le t \le 10^9)$, denoting an instruction. Each of the following $q$ lines contains four integers $x\,(0 \le x \le n)$, $y\,(0 \le y \le m)$, $l,r\,(1 \le l \le r \le k)$, denoting a query.

For each query, output a line containing three integers $u,v$ and $w$, denoting the coordinates of the final position and the length of the moving route.

· For the first query, the moving route is $(1,1) \xrightarrow{L} (0,1) \xrightarrow{L} (0,1) \xrightarrow{D} (0,0) \xrightarrow{D} (0,0) \xrightarrow{R} (1,0)$, where the final position is $(1,0)$ and the length of the moving route is $3$. · For the second query, the moving route is $(2,1) \xrightarrow{D} (2,0) \xrightarrow{D} (2,0) \xrightarrow{R} (3,0) \xrightarrow{R} (3,0) \xrightarrow{U} (3,1) \xrightarrow{U} (3,2)$, where the final position is $(3,2)$ and the length of the moving route is $4$.