Cesarstwo Bajtockie rozpoczęło wojnę z sąsiadami. Potrzeba jak najwięcej rąk do walki! Trzeba o tym powiadomić bajtockich wojowników. Jako, że cesarstwo Bajtockie jest bardzo rozległe, poinformowanie odpowiedniej liczby wojowników jest zadaniem dla kogoś bardzo wytrzymałego, kto potrafi nie jeść, nie pić, biec dniem i nocą, aby jak najprędzej rozgłosić informację o wojnie. Z rozkazu Cesarza wybrany został Bajtokles. Cesarstwo ma w przybliżeniu kształt długiego odcinka, na którym w różnych miejscach stoją domy wojowników. Możemy je utożsamić z odcinkiem, na którym są kolejne punkty o numerach 1, 2, …, n, przy czym każdy punkt jest albo wolny, albo stoi na nim dom wojownika. Bajtokles rozpoczyna swoją wędrówkę w jakimś punkcie i kieruje się w prawo, kończąc w jakimś innym punkcie (początek i koniec są w punktach o współrzędnych całkowitych), informując wojownika w każdym napotkanym domu, który minie (zakładamy, że jeżeli domy stoją w miejscach startu lub końca wędrówki Bajtoklesa, to wojownicy w nich są informowani).
Jeszcze nie do końca wiadomo, jak silny jest przeciwnik, dlatego Bajtokles musi rozważyć przypadki, w których musi odwiedzić różne liczby domów (dla każdej takiej liczby Bajtokles musi odwiedzić dokładnie tyle domów - nie należy zawracać głowy większej liczbie wojowników niż jest to potrzebne, nie może ich być też za mało). Dla każdego takiego przypadku Bajtokles zastanawia się, na ile sposobów może wybrać początek i koniec swojej trasy tak, aby odwiedzić zadaną liczbę wojowników.
W pierwszym wierszu masz podane liczby n i q (1 <= n <= 10^6, 1 <= q <= 2000), które oznaczają kolejno, liczbę punktów, w których Bajtokles może rozpocząć lub skończyć swoją wędrówkę oraz liczbę zapytań, na które musisz odpowiedzieć. W drugiej linii będzie miał podany ciąg n liter „W” i „D”. „W” oznacza, że dany punkt jest wolny, a „D”, że w danym punkcie stoi dom wojownika. Możesz założyć, że litera „D” nie pojawi się w tym ciągu więcej niż 2000 razy. W i+2-giej linii masz podane i-te zapytanie, czyli liczbę d (0 <= d <= 2000), która oznacza, ile domów musi odwiedzić Bajtokles.
W 50% przypadków testowych zachodzi 1<= n <= 3000.
W 30% testów dodatkowo zachodzi 1 <= q <= 500
Na każde zapytanie musisz odpowiedzieć liczbą możliwych wyborów różnych wędrówek, w których Bajtokles odwiedza dokładnie d domów. Dwie wędrówki są różne, gdy nie jest tak, że i początki i końce tych tras są takie same. Koniec musi być nie wcześniej niż początek.
Dla danych wejściowych 4 2 WDWD 1 2 poprawną odpowiedzią jest: 6 2
[Zgłoś rozwiązanie] [Moje zgłoszenia]