Contest problemset 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 c₀c₁…c_N − 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 c_{i 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 x_i oraz y_i, 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 (x_i,y_i), lub liczbą  − 1, jeżeli nie jest to możliwe w żadnym czasie.

Ograniczenia

1 ≤ Q ≤ 200 000, 1 ≤ N ≤ 1 000 000, |x_i|, |y_i| ≤ 10⁹.

Podzadania

W każdym podzadaniu testy, w których zachodzi warunek Q = 1, warte są 60% punktów za dane podzadanie.

Przykład

3
LRD
-2 -2
1 0
3 3

3
-1
8

Dana jest tablica o N wierszach i N kolumnach. Komórka w i-tym wierszu i j-tej kolumnie ma początkowo pewien kolor k_i, j. Twoim zadaniem jest przemalować tablicę tak, żeby dla danego K, oraz dla dowolnych i, j, x, y zachodziły następujące warunki:

• Jeżeli reszta z dzielenia przez K liczb (i+j) oraz (x+y) jest taka sama, to komórki (i,j) oraz (x,y) powinny mieć ten sam kolor.
• Jeżeli reszta z dzielenia przez K liczb (i+j) oraz (x+y) jest różna, to komórki (i,j) oraz (x,y) muszą mieć różne kolory.

Jednakże, zmiana koloru pojedynczej komórki o kolorze i w kolor j kosztuje c_i, j. Kolor każdej komórki można zmienić co najwyżej raz. Jaki jest najmniejszy sumaryczny koszt przemalowania tablicy tak, żeby spełniała oba warunki?

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite N, K oraz C, oznaczające odpowiednio rozmiar tablicy, parametr K oraz liczbę kolorów. W następnych N wierszach znajduje się opis początkowego stanu tablicy. i-ty wiersz składa się z N liczb, k_i, 1, …, k_i, N, oznaczająca początkowe kolory w i-tym wierszu tablicy.

Potem następuje C wierszy opisujące koszta zmiany kolorów. W i-tym wierszu znajduje się C liczb c_i, 1, …, c_i, C, wartość c_i, j określająca cenę zmiany koloru i w kolor j (odwrotna zmiana koloru może mieć inną cenę).

Wyjście

W jednym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą minimalny koszt przemalowania tablicy tak, by spełniała założenia zadania.

Ograniczenia

1 ≤ N ≤ 1 000, 1 ≤ C ≤ 10, 1 ≤ K ≤ C, 1 ≤ k_i, j ≤ C, 1 ≤ c_i, j ≤ 10⁹.

Podzadania

Przykład

2 3 3
2 1
2 1
0 3 3
2 0 5
2 1 0

5

Rozważmy następującą wariację gry w bilarda (gry, w której kijem uderza się kule ustawione na stole, które mają wpaść do specjalnie wyznaczonych dziur w odpowiednich miejscach stołu). Na stole leży N kul bilardowych, ponumerowanych od 1 do N. Mamy w zasobach X energii. Wbicie kuli o numerze i kosztuje a_i energii. Nie można wbić danej kuli, jeżeli posiadana energia w danym momencie jest mniejsza od jej kosztu. Ponadto, dany jest ciąg p_i, dla i = 1, …, N. Jeżeli p_i =  − 1, to kula o numerze i może zostać wbita w dowolnym momencie. Jeżeli natomiast 1 ≤ p_i ≤ N, to kula o numerze i może zostać wbita dopiero po wbiciu kuli o numerze p_i.

Jaki jest największy numer kuli, jaką jesteśmy w stanie wbić, przy założeniu, że zawsze trafiamy?

Wejście

W pierwszym wierszu wejścia dane są dwie liczby naturalne N oraz X oznaczające liczbę kul oraz początkową energię. W następnym wierszu dany jest ciąg a₁, …, a_N, oznaczający energię potrzebną do wbicia kolejnych kul. W następnym wierszu dany jest ciąg p₁, …, p_N.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą najwyższy numer kuli, jaki jesteśmy w stanie wbić, lub  − 1 jeżeli nie jest to możliwe.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ X ≤ 10¹⁵, 1 ≤ a_i ≤ 10⁹, 1 ≤ p_i ≤ N lub p_i =  − 1, ale p_i ≠ i, dla i = 1, …, N.

Podzadania

Przykład

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

4

5 12
1 2 3 5 8
-1 1 2 3 4

4

8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7

7

2 1000000000000000
1 1
2 1

-1