Sejf

05.08.2011

Sejf

Limit czasowy: 4000 milisekund
Limit pamięciowy: 32000 kilobajtów


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ć.

Wejście

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 N, M ( 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 - L (lewo) lub P (prawo) - oznaczającej kierunek obrotu, oraz po spacji jednej liczby naturalnej x ( 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 (R, k) do przetestowania. Każda z ostatnich T linii zawiera po dwie dodatnie liczby całkowite R ( 1 <= R <= 109 ) oraz k ( 1 <= k <= N ).

Wyjście

Dla każdej pary danych (R, k) 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.

Przykład

Wejście Wyjście
1
3 3
L 1
P 1
P 2
3
1 3
1 2
2 1

1

2

4

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com