Woburn Challenge 2016-17 Round 2 - Senior Division

Lieutenant commander Scetty has been assigned quite the tedious task - testing a turbolift. Hardly a job worthy of the Enterprise's chief engineer! This particular turbolift has just $2$ buttons - one to take the turbolift up $1$ floor, and another to take it down $1$ floor.

One "button press" is an action consisting of, well, pressing one of the buttons. It can be represented as a single character, either U if the up button is pressed, or D if the down button is pressed.

One "button sequence" is an ordered sequence of one or more button presses. The turbolift has the ability to perform $N$ $(1\le N\le 200000)$ different types of button sequences, numbered from $1$ to $N$, with the $i^{th}$ one represented by the string $B_i$. The $j^{th}$ character in this string represents the $j^{th}$ button press in the sequence. The strings $B_{1\dots N}$ are not necessarily distinct, and the sum of their lengths is at most $200000$.

The turbolift will start on floor $0$ of the Enterprise. Due to recent technological advances, the ship has infinitely many floors above floor $0$ (numbered upwards from $1$), and infinitely many basement floors below it (numbered downwards from $-1$). As part of the testing process, it will then be programmed to execute $M$ $(1\le M\le 200000)$ button sequences, one after another. The $i^{th}$ button sequence in this sequence of sequences will be button sequence is $S_i$ $(1\le S_i\le N)$. Note that some button sequences could be executed multiple times during the testing, while others could not be executed at all.

Throughout the process, Scetty will make notes about how low and high the turbolift ends up getting. In particular, he has $Q$ $(1\le Q\le 200000)$ questions to answer. The $i^{th}$ one asks: "After the first $P_i$ button presses, what are the minimum and maximum floor numbers that the turbolift will have reached up to that point?". $P_i$ is a positive integer no greater than the total number of button presses which will be executed throughout the sequence of $M$ button sequences. Note that both $P_i$ and the answers may not fit within a $32$-bit integer.

In test cases worth $12/27$ of the points, $N\le 3000$, $M\le 3000$, and no single button sequence consists of more than $3000$ button presses.

Input Specification

The first line of input consists of three space-separated integers $N$, $M$, and $Q$.
$N$ lines follow, the $i^{th}$ of which consists of a single string $B_i$ (for $i=1\dots N$).
$M$ lines follow, the $i^{th}$ of which consists of a single integer $S_i$ (for $i=1\dots M$).
$Q$ lines follow, the $i^{th}$ of which consists of a single integer $P_i$ (for $i=1\dots Q$).

Output Specification

Output $Q$ lines, the $i^{th}$ of which should consist of two space-separated integers - the lowest and highest floors that the turbolift will reach after no more than $P_i$ button presses (for $i=1\dots Q$).

Sample Input

2 3 3
DDUU
U
2
1
2
1
6
4

Sample Output

0 1
-1 2
-1 1

Sample Explanation

The turbolift will receive $6$ button presses in total, with the following results:

Button | Floor
-------+------
   U   |   1
   D   |   0
   D   |  -1
   U   |   0
   U   |   1
   U   |   2