Problem description
Rozważmy płaszczyznę oraz układ współrzędnych. W punkcie (0,0) stoi pionek, którego celem jest przemieścić się do wyznaczonego punktu (X,Y). W każdej sekundzie, pionek należy przesunąć o jedną jednostkę w jedną z czterech stron: do góry, w dół, w lewo lub w prawo. Jednakże, na planszy wieje silny wiatr, który w każdej sekundzie przesuwa pionek o jedną jednostkę w którymś kierunku, zaraz przed wykonaniem wybranego ruchu. Oznacza to, że jeśli wiatr zepchnie nas pole (X,Y), to nie traktujemy tego jako przemieszczenie się do tego punktu: musimy na niego wejść bezpośrednio po wykonaniu naszego ruchu.
Chciałbyś odpowiadać na zapytania, w jakim najszybszym czasie jesteś w stanie przesunąć pionek z pozycji startowej do pewnej pozycji (X,Y)?
Wejście
W pierwszym wierszu wejścia dana jest jedna liczba całkowita Q oznaczająca liczbę zapytań. W
drugim wierszu wejścia dany jest ciąg znaków c0c1…cN − 1,
składający się z liter U, D, L
oraz R, jest to opis wiatru oraz w którą stronę wiatr
przesuwa pionek w kolejnych sekundach (litery odpowiadają odpowiednio
przesunięciu o 1 w górę (up) i w dół
(down) wzdłuż osi OY
oraz o 1 w lewo (left) i prawo (right)
wzdłuż osi OX). W
sekundzie i, wiatr przesunie
pionek w stronę daną przez ci mod N
(gdzie i mod N
oznacza resztę z dzielenia i
przez N). Można myśleć o tym,
że przez pierwsze N sekund
wiatr przesuwa zgodnie ze znakami w ciągu, a kiedy dojdzie do końca,
zapętla się i zaczyna przesuwać od początku ciągu.
W następnych Q wierszach dany jest opis kolejnych zapytań, i-te zapytanie składa się z dwóch liczb xi oraz yi, oznaczających docelowe pole, na którym ma znaleźć się pionek.
Wyjście
Należy wypisać Q wierszy, i-ty wiersz powinien być odpowidzią na zapytanie, w ile minimalnie sekund jesteśmy w stanie przesunąć pionek z pola (0,0) do pola (xi,yi), lub liczbą − 1, jeżeli nie jest to możliwe w żadnym czasie.
Ograniczenia
1 ≤ Q ≤ 200 000, 1 ≤ N ≤ 1 000 000, |xi|, |yi| ≤ 109.
Podzadania
W każdym podzadaniu testy, w których zachodzi warunek Q = 1, warte są 60% punktów za dane podzadanie.
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | N = 1. | 26 |
| 2 | N ≤ 20. | 23 |
| 3 | Jeżeli odpowiedź istnieje, to jest nie większa niż 1 000 000. | 28 |
| 4 | Brak dodatkowych ograniczeń. | 23 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
W pierwszym przypadku, jedną z możliwości jest pójście kolejno w lewo, lewo oraz w dół. W drugim przypadku nie ma żadnej możliwości, aby po którymś ruchu znaleźć się w polu (1,0). W ostatnim przypadku trzeba się trochę bardziej natrudzić, ale chodząc odpowiednio w prawo, dwa razy w górę, w prawo, dwa razy w górę i jeszcze w prawo i w górę, jesteśmy w stanie dotrzeć do docelowego punktu. |