The Safe

These days nothing left out in the open is safe, and Hektor's Ukemon card collection is no exception: tomorrow his younger cousin Olek comes to visit. To keep the collection he spent so long building out of harm's way during the visit, Hektor bought a safe just for the occasion and locked the cards inside.

The safe's lock is a round dial. The numbers $1$ through $N$ are printed around it clockwise, with $1$ at the very top. The dial can be turned only in one of $M$ preset ways; each way turns it a fixed number of steps to the left or to the right. The safe opens when, after exactly $R$ turns, the number $k$ is at the top.

Let $v$ be the number currently at the top (so $v = 1$ before any turn). A left turn written L x changes the top number to $((v - 1 + x) \bmod N) + 1$, and a right turn written P x changes it to $((v - 1 - x) \bmod N) + 1$. The turns are applied one after another.

Hektor wants to gauge how secure the safe is, so for several targets he needs to know how many different ordered sequences of $R$ turns (each turn chosen from the $M$ available ways) leave the number $k$ at the top.

The first line contains a natural number $Z$ ($Z = 1$), the number of test sets. The sets follow one after another.

For each set, the first line contains two space-separated natural numbers $N$ and $M$ ($1 \le N, M \le 2000$). Each of the next $M$ lines describes one allowed turn: a letter, L (left) or P (right), giving the direction, then a space, then a natural number $x$ ($0 < x < N$) giving how many steps it turns. All $M$ turns are pairwise different.

The next line contains a natural number $T$ ($1 \le T \le 10$), the number of pairs $(R, k)$ to check. Each of the following $T$ lines contains two positive integers $R$ ($1 \le R \le 10^9$) and $k$ ($1 \le k \le N$).

For each pair $(R, k)$, print on its own line a single non-negative integer: the number of different ordered sequences of $R$ turns that open the safe (that is, leave $k$ at the top), taken modulo $1000033$.