금고

요즘은 밖에 그냥 놓아둔 것이라면 무엇도 안전하지 않다. 헥토르(Hektor)가 모은 우케몬 카드 컬렉션도 예외가 아니다. 내일 사촌 동생 올렉(Olek)이 놀러 오기 때문이다. 오랫동안 모아 온 컬렉션을 방문 기간 동안 위험에 노출시키지 않으려고, 헥토르는 이번 기회에 맞춰 금고를 하나 사서 카드를 그 안에 넣고 잠갔다.

금고의 자물쇠는 둥근 다이얼이다. 다이얼에는 $1$부터 $N$까지의 수가 시계 방향으로 적혀 있고, 맨 위에는 $1$이 놓여 있다. 다이얼은 미리 정해진 $M$가지 방법으로만 돌릴 수 있으며, 각 방법은 정해진 칸 수만큼 왼쪽 또는 오른쪽으로 돌린다. 정확히 $R$번 돌린 뒤 맨 위에 수 $k$가 오면 금고가 열린다.

현재 맨 위에 있는 수를 $v$라고 하자(돌리기 전에는 $v = 1$이다). L x로 표기하는 왼쪽 돌리기는 맨 위 수를 $((v - 1 + x) \bmod N) + 1$로 바꾸고, P x로 표기하는 오른쪽 돌리기는 $((v - 1 - x) \bmod N) + 1$로 바꾼다. 돌리기는 차례대로 하나씩 적용된다.

헥토르는 금고가 얼마나 안전한지 알고 싶다. 여러 목표에 대해, $M$가지 방법 중에서 매번 하나씩 고른 $R$번의 돌리기로 이루어진 순서열 가운데, 맨 위에 수 $k$가 남는 서로 다른 순서열이 몇 개인지 구하면 된다.

첫 번째 줄에는 테스트 세트의 개수를 나타내는 자연수 $Z$ ($Z = 1$)가 주어진다. 이어서 각 세트가 차례로 주어진다.

각 세트의 첫 번째 줄에는 공백으로 구분된 두 자연수 $N$, $M$ ($1 \le N, M \le 2000$)이 주어진다. 다음 $M$개의 줄은 각각 허용되는 돌리기 하나를 설명한다. 각 줄에는 방향을 나타내는 문자 L(왼쪽) 또는 P(오른쪽)가 오고, 공백 뒤에 돌리는 칸 수를 나타내는 자연수 $x$ ($0 < x < N$)가 온다. $M$개의 돌리기는 모두 서로 다르다.

그다음 줄에는 확인할 $(R, k)$ 쌍의 개수를 나타내는 자연수 $T$ ($1 \le T \le 10$)가 주어진다. 이어지는 $T$개의 줄에는 각각 두 양의 정수 $R$ ($1 \le R \le 10^9$)과 $k$ ($1 \le k \le N$)가 주어진다.

각 쌍 $(R, k)$에 대해, 금고를 여는(즉, 맨 위에 $k$가 남는) 서로 다른 $R$번 돌리기 순서열의 개수를 $1000033$으로 나눈 나머지를 한 줄에 하나씩 음이 아닌 정수로 출력한다.