Problem description

Jest to problem interaktywny. Powinieneś wykonać operację flush po wypisaniu każdego wiersza. W C++ możesz użyć funkcji fflush(stdout) lub cout.flush(), w Javie System.out.flush(), w Pythonie sys.stdout.flush().

Bajter Bitl znowu wdał się w kłopoty w kosmosie. Żeby wykaraskać się z tarapatów, musi w idealny sposób rozdysponować pozostałe K litrów paliwa na N silników.

Każdy silnik w jego statku pozwala na przebycie pewnej odległości, zależnej od tego, ile litrów paliwa się do niego wleje. Dokładniej, dla i-tego silnika istnieje pewna funkcja f_i, określona na liczbach całkowitych od 0 do K, która jest nieujemna i ściśle malejąca. Po wlaniu T_i litrów paliwa do i-tego silnika, można przelecieć $\sum_{t = 0}^{T_i} f_i(t)$ jednostek astronomicznych. Przez specyficzną konstrukcję silników, zachodzi f_i(x) ≠ f_j(y), jeśli i ≠ j lub x ≠ y.

Niestety, tabelka z dokładnymi wartościami tych funkcji uległa zniszczeniu. Na szczęście, ostała się niezwykle stara maszyna z technologią z XX wieku, która pozwala porównywać wartości funkcji. Bajter może z jej pomocą odpowiedzieć na zapytanie: “Czy wartość funkcji f_i(x) jest większa od wartości funkcji f_j(y)?”.

Bajter chce, mimo tak ograniczonej technologii, wykorzystać każdy litr paliwa do perfekcji i dotrzeć najdalej jak jest to możliwe.

Niestety, przez wolne działanie maszyny porównującej, Bajter może zadać tylko 5 000 zapytań do maszyny, zanim dopadną go bandyci. Czy jesteś w stanie mu pomóc i uratować jego statek?

Interakcja

Na początku sprawdzaczka podaje (na standardowe wejście programu) dwie liczby całkowite N i K, oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę silników i liczbę litrów paliwa, którymi dysponuje Bajter Bitl.
Twój program może zadać co najwyżej 5 000 zapytań. Każde zapytanie powinno składać się ze znaku zapytania i czterech liczb całkowitych i, x, j, y (1 ≤ i, j ≤ N, 0 ≤ x, y ≤ K), oddzielonych pojedynczymi odstępami. Po wypisaniu wiersza, należy wczytać jedną liczbę całkowitą 0 bądź 1, oznaczającą odpowiednio, że f_i(x) < f_j(y) lub f_i(x) > f_j(y). W zadanym zapytaniu powinien zajść co najmniej jeden z następujących warunków: i ≠ j lub x ≠ y.
Jeżeli znajdziesz optymalne rozwiązanie T₁, T₂, …, T_N, wypisz wiersz składający się z wykrzyknika i kolejnych wartości ciągu T_i, pooddzielanych pojedynczymi odstępami. Wypisanie rozwiązania nie wlicza się do limitu zapytań.
Interaktor może być adaptywny i zależeć od wyników Twoich poprzednich zapytań. Możesz założyć, że odpowiedzi na zadane przez Ciebie zapytania są poprawne tj. istnieją pewne funkcje f_i, które spełniają wszystkie podane założenia.
Uwaga: błędne zapytanie albo przekroczenie limitu zapytań może zakończyć się werdyktem błędu wykonania.

Ograniczenia

1 ≤ N ≤ 32, 1 ≤ K ≤ 2³⁰.

Przykładowa interakcja