Metro

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 512MB

Mamy linię metra z n stacjami. Jeździ po niej pociąg. Nie znamy algorytmów które nim sterują.
Chcemy go złapać i unieruchomić. Do dyspozycji mamy stare urządzenie lokalizujące.
Możemy nim zeskanować obszar między stacjami l i r, a urządzenie powie nam, czy pociąg tam się znajduje.
Jednak urządzenie długo się ładuje, więc między użyciami pociąg może się przemieszczać. Zatem jeśli pociąg znajdował
się na stacji x, to w trakcie następnego pomiaru może znajdować się na przedziale [max(1, x-k), min(n, x+k)], gdzie k oznacza prędkość pociągu.
Możesz też zeskanować pojedyńczą stację (wtedy l = r) i jeśli pociąg się tam znajduje, grupa uderzeniowe uda się tam i odzyska kontrolę nad maszyną.
Czy jesteś w stanie namierzyć pociąg używając co najwyżej 4500 pomiarów?

Wejście

W pierwszym wieszu znajdują się dwie liczby całkowite n i k (1<=n<=1018, 0<=k<=10) oznaczająca ilość stacji i prędkość pociągu.

Interakcja

By użyć urządzenia, należy wypisać na wyjście parę liczb l, r.
Następnie na wejściu zostanie podana odpowiedź ("Yes", jeśli pociąg został zauważony, "No", jeśli go tam nie ma).
Po otrzymaniu odpowiedzi "Yes" na zapytanie gdzie l=r program powinien się zakończyć.

Przykład

Dla pozycji pociągu 5, 5, 3, 5, 7, 7, ...
Wejście:
10 2

Yes

No

Yes

Yes

Wyjscie:
3 5

3 3

3 4

5 5