시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 128 MB 0 0 0 0.000%

문제

W dzisiejszych czasach nic, co leży na wierzchu, nie jest bezpieczne. Nie inaczej jest z kartami z Ukemonami Hektora, do którego jutro przyjeżdża młodszy kuzyn Olek. Hektor, nie chcąc narażać długo zbieranej kolekcji na potencjalne ryzyko spotkania z kuzynem, postanowił zamknąć ją na czas wizyty Olka w specjalnie na tę okazję kupionym sejfie.

Zamek sejfu jest pokrętłem o kształcie koła z zaznaczonymi na nim prawoskrętnie liczbami kolejno od 1 do N, z liczbą 1 na samym szczycie. Pokrętło można obracać tylko na M z góry ustalonych sposobów: o kilka pozycji w prawo lub kilka w lewo. Sejf otwiera się, gdy po dokładnie R obrotach na szczycie znajduje się liczba k. Hektor bada bezpieczeństwo posiadanego przez siebie sejfu, dlatego tak istotna jest dla niego informacja, ile różnych kombinacji kolejnych R obrotów pozwala go otworzyć.

입력

W pierwszej linii wejścia znajduje się liczba naturalna Z ( Z = 1 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pierwsza linia opisu zestawu testowego zawiera parę oddzielonych spacjami, opisanych w treści liczb naturalnych NM ( 1 <= N, M <= 2000 ). Następne M linii opisuje dopuszczalne obroty zamka sejfu. Każda linia opisująca obrót składa się z jednej litery - (lewo) lub P (prawo) - oznaczającej kierunek obrotu, oraz po spacji jednej liczby naturalnej ( 0 < x < n ), oznaczającej jego zasięg. Każde dwa obroty są różne.

W następnej linii znajduje się liczba naturalna  T  ( 1 <= T <= 10 ) oznaczająca liczbę różnych par liczb (Rk) do przetestowania. Każda z ostatnich T linii zawiera po dwie dodatnie liczby całkowite R ( 1 <= R <= 109 ) oraz k ( 1 <= <= N ).

출력

Dla każdej pary danych (Rk) należy wypisać w osobnej linii jedną nieujemną liczbę całkowitą, będącą resztą z dzielenia liczby różnych kombinacji obrotów otwierających sejf przez 1000033.

예제 입력 1

1
3 3
L 1
P 1
P 2
3
1 3
1 2
2 1

예제 출력 1

1
2
4

출처

Contest > Spot > HotSpot 2011 3-3번