Problem E
Mineral deposits

Erodująca ściana błota odsłaniająca nowe minerały. Zdjęcie: Michael D. Turnbull, licencja: CC BY-SA.

Zajmujesz się przetwarzaniem sygnałów dla pozaziemskiej firmy wydobywczej, a Twój statek właśnie zbliża się do asteroidy. Wstępne skany wskazują na obecność $k$ złóż minerałów na asteroidzie, ale ich dokładne lokalizacje nie są znane.

Powierzchnia asteroidy może być postrzegana jako siatka współrzędnych całkowitych. Każde ze złóż minerałów znajduje się w nieznanych współrzędnych całkowitych, tak że $i$-te złoże ma współrzędne $(x_ i, y_ i)$ spełniające $-b \le x_ i \le b$ oraz $-b\le y_ i \le b$ dla pewnej liczby całkowitej $b$ odpowiadającej rozmiarowi Twojego początkowego skanu.

Aby określić dokładne położenie złóż minerałów, możesz wysłać na powierzchnię asteroidy sondy. Sondy są wysyłane w falach po kilka sond jednocześnie.

Powiedzmy, że wysłałeś jedną falę $d$ sond na powierzchnię na współrzędne $(s_ j,t_ j)$ dla $1\leq j\leq d$. Kiedy sonda dociera do swoich współrzędnych, określa odległości w metryce Manhattan do każdego z $k$ złóż minerałów i wysyła odległości z powrotem na statek. Wszystkie pakiety danych docierają w tym samym czasie i nie jest możliwe określenie, które sondy zwróciły jakie odległości. Tak więc fala zwraca $k\cdot d$ odległości całkowitych

Musisz zminimalizować liczbę fal sond, które są wysyłane na powierzchnię.

Interakcja

Jest to problem interaktywny. Interakcja rozpoczyna się od wczytania ze standardowego wejścia pojedynczego wiersza zawierającego trzy liczby całkowite $b$, $k$ oraz $w$: granica siatki $b$, liczbę złóż minerałów $k$, i maksymalna liczba $w$ fal, które możesz wysłać.

Następnie zadajesz co najwyżej $w$ zapytań, każde odpowiadające jakiejś fali. Zapytanie składa się z ?, po którym następuje $2d$ liczb całkowitych oddzielonych spacją, na przykład “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, gdzie liczba $d$ sond w tej fali musi spełniać wymagania $1\leq d\leq 2000$. Wartości $(s_ i,t_ i)$ są interpretowane jako współrzędne $i$-tej sondy i muszą spełniać $-10^8 \leq s_ i \leq 10^8$ oraz $-10^8 \leq t_ i \leq 10^8$. Odpowiedzią jest jeden wiersz zawierający $k \cdot d$ liczb całkowitych w kolejności niemalejącej: wszystkie pary odległości w metryce Manhattan pomiędzy złożami mineralnymi oraz współrzędnymi sondy. Całkowita liczba sond we wszystkich falach nie może przekroczyć $2\cdot 10^4.$

Interakcja kończy się wypisaniem pojedynczego wiersza składającego się ze znaku !, po którym następuje $k$ punktów $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, oddzielone spacją. To musi być ostatni wiersz wypisany przez Ciebie na standardowe wyjście.

Twoje zgłoszenie zostanie uznane za poprawne, jeśli wypiszesz wszystkie lokalizacje złóż minerałów. Możesz je wypisać w dowolnej kolejności.

Ograniczenia i punktacja

Zawsze jest spełnione $1\leq b \leq 10^8$, $1 \leq k \leq 20$, oraz $2 \le w \le 10^4$.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za daną grupę testową należy rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

Przykład

W tym przykładzie, na pozycjach $(1,2)$ oraz $(-3,-2)$ znajdują się $k=2$ złoża mineralne, zareprezentowane jako czerwone gwiazdy. W pierwszym rzucie możesz wysłać $d=3$ sondy na pozycje $(-4,-3)$, $(-1, 0)$ oraz $(2,-1)$, zareprezentowane jako czarne kropki. Ta fala zwróciłaby $6$ odległości

W następnej fali można wysłać sondy $d=2$ do $(1,2)$ oraz $(0,-2)$. Ta fala zwróciłaby $4$ odległości

 4 2 10

 ? -4 -3 -1 0 2 -1

 2 4 4 4 6 10

 ? 1 2 0 -2

 0 3 5 8

 ! 1 2 -3 -2