Żabka
Limit pamięci: 128 MB
Wzdłuż bajtockiego strumyczka stoi kamieni.
Są one położone kolejno w odległościach
od źródła strumyczka.
Na jednym z tych kamieni stoi żabka, która właśnie ćwiczy się w skakaniu.
W każdym skoku żabka skacze na
-ty najbliższy kamień (od kamienia, na którym siedzi).
Dokładniej, jeżeli żabka w danej chwili siedzi na kamieniu
w położeniu
, to po wykonaniu skoku będzie siedziała na takim kamieniu
, że:
oraz
Pierwsza z powyższych nierówności oznacza, że liczba punktów
, których
odległość od punktu
jest mniejsza niż odległość między punktami
a
, jest nie większa niż
.
Podobnie, druga z nierówności oznacza, że
liczba punktów
, których
odległość od punktu
jest nie większa niż odległość między punktami
a
, jest większa niż
.
W przypadku, gdy istnieje więcej niż jedno takie , żabka wybiera
skrajnie lewą spośród takich pozycji.
Na którym kamieniu znajdzie się żabka po wykonaniu
skoków, w zależności
od tego, z którego kamienia zaczyna?
Wejście
Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite
,
oraz
(
,
),
pooddzielane pojedynczymi odstępami i reprezentujące odpowiednio: liczbę
kamieni, parametr skoku żabki oraz liczbę zaplanowanych skoków żabki.
Drugi wiersz zawiera
liczb całkowitych
(
), pooddzielanych pojedynczymi
odstępami i oznaczających położenia kolejnych kamieni wzdłuż strumyczka.
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie jeden wiersz
zawierający liczb całkowitych
z przedziału
, pooddzielanych pojedynczymi odstępami.
Liczba
oznacza numer kamienia, na którym żabka zakończy skakanie,
jeśli rozpocznie je z kamienia o numerze
(zgodnie z kolejnością
z wejścia).
Przykład
Dla danych wejściowych:
5 2 4 1 2 4 7 10
poprawną odpowiedzią jest:
1 1 3 1 1
Na rysunku pokazano, jak żabka skacze z poszczególnych kamieni (w jednym skoku).
Autor zadania: Jakub Radoszewski.