To jest zadanie interaktywne.

Na ladzie cukierni Pchła stoją dwa rzędy kolorowych, dwuwarstwowych galaretek (górna warstwa to $a$, a dolna to $b$). Zgodnie z obowiązującą w sklepie zasadą „uzupełniającego się tężenia” suma wysokości górnej i dolnej warstwy każdej galaretki wynosi dokładnie $n+1$. Pracownicy ustawili wcześniej oba rzędy według wysokości w idealne permutacje liczb $1 \sim n$, ale wczoraj wieczorem energiczny pracownik, pchła, przypadkowo zamienił miejscami górne i dolne warstwy na niektórych pozycjach!

Teraz zbliża się rozpoczęcie corocznego festiwalu deserów, a pracownicy muszą odtworzyć początkowe ustawienie galaretek sprzed zamian (czyli ciąg wysokości górnych warstw $a$ sprzed zamian).

Nie możesz bezpośrednio obserwować wysokości galaretek, ale możesz wydawać polecenia automatycznemu urządzeniu pomiarowemu cukierni: wskaż kilka pozycji $i$, a urządzenie zamieni na nich górne i dolne warstwy galaretek i zwróci różnicę między największą a najmniejszą wysokością obecnych górnych warstw (rozstęp), a także różnicę między największą a najmniejszą wysokością dolnych warstw (rozstęp). Uwaga: skutki każdej zamiany pozostają w mocy.

Czy potrafisz odtworzyć początkowy ciąg ustawienia górnych warstw galaretek, wykonując ograniczoną liczbę pomiarów z zamianami?

Biblioteka interaktywna najpierw wybiera permutację $p$ liczb $1\sim n$ i tworzy permutację $b_i=n+1-p_i$. Następnie dla każdego indeksu $i$ niezależnie decyduje, czy zamienić dwie liczby na pozycji $i$. Tablice otrzymane po wykonaniu zamian oznaczamy przez $a,b$. Zawsze zachodzi wtedy $a_i+b_i=n+1$, ale $a,b$ nie muszą już być permutacjami.

Znasz $n$, ale nie znasz tych dwóch tablic. Możesz wybrać kilka pozycji i zamienić na nich $a_i,b_i$; biblioteka interaktywna poda rozstępy obu tablic po zamianach. Skutki każdej zamiany pozostają w mocy.

Twoim zadaniem jest odtworzenie tablicy $a$ sprzed pierwszego zapytania. Odpowiedź zostanie uznana za poprawną również wtedy, gdy dopiero jednoczesne zastąpienie każdej wartości $x$ w zwróconej tablicy przez $n+1-x$ da tablicę docelową.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

W pliku źródłowym recover.cpp należy dołączyć plik nagłówkowy range.h i zaimplementować następującą funkcję:

std::vector<int> recover(int c, int n);

• $c$ jest numerem bieżącego podzadania: w oficjalnych testach przyjmuje wartości $1,2,3,4$, a w przykładzie $0$. $n$ jest długością tablicy. Biblioteka interaktywna wywołuje recover dokładnie raz dla każdego testu.
• Zwrócona wartość musi być tablicą liczb całkowitych o długości $n$, przedstawiającą $a$ sprzed pierwszego zapytania lub jej dopełnienie na wszystkich pozycjach.

Możesz wywoływać następującą funkcję:

std::pair<int, int> query(const std::vector<int>& positions);

• Indeksy w positions muszą być parami różne i należeć do $[0,n-1]$. Można przekazać pustą tablicę.
• Biblioteka interaktywna zamienia bieżące $a_i,b_i$ dokładnie raz dla każdego indeksu w positions, po czym zwraca rozstęp bieżącej tablicy $a$ oraz rozstęp bieżącej tablicy $b$. Zamiany między zapytaniami kumulują się, ale zwracając odpowiedź, należy odtworzyć początkową tablicę sprzed zamian.
• Rozstęp jest zdefiniowany jako największa wartość w tablicy minus najmniejsza. Ponieważ zawsze zachodzi $b_i=n+1-a_i$, oba rozstępy są zawsze równe.
• Liczba wywołań query nie może przekroczyć limitu $Q_{\max}$ dla danego testu.

Biblioteka interaktywna nie jest adaptacyjna: początkowe tablice są ustalone przed rozpoczęciem recover i nie zmieniają się w zależności od twoich zapytań. Biblioteka używana podczas ostatecznej oceny może różnić się od udostępnionej biblioteki przykładowej. Twój program nie może odczytywać wewnętrznych danych biblioteki ani bezpośrednio korzystać ze strumieni standardowego wejścia i wyjścia.

Testowanie programu

Umieść recover.cpp, range.h i załączony plik grader.cpp w tym samym katalogu i skompiluj je w C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

Pierwszy wiersz odczytywany przez lokalną bibliotekę interaktywną zawiera $c,n,Q_{\max}$; drugi zawiera permutację $p_0,\ldots,p_{n-1}$; trzeci zawiera $n$ liczb $0/1$, przy czym $1$ oznacza zamianę na danej pozycji przed rozpoczęciem interakcji. Jedynie $c,n$ są udostępniane zawodnikowi jako argumenty funkcji; permutacja, znaczniki zamian i limit zapytań nie są bezpośrednio przekazywane programowi zawodnika.

Jeśli odpowiedź jest poprawna, lokalna biblioteka interaktywna wypisuje w pierwszym wierszu Correct!, a w drugim Queries used: Q, gdzie $Q$ oznacza liczbę zapytań użytych podczas tego wywołania. Jeśli odpowiedź jest błędna, wypisuje Wrong answer.; jeśli wywołanie interfejsu jest nieprawidłowe, dodatkowo podaje przyczynę błędu na standardowym strumieniu błędów.

Przykład

Wejście 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Wyjście 1

Correct!
Queries used: 16

Uwagi

W przykładzie przed rozpoczęciem interakcji $a=(3,6,1,4,5,5)$, a jej dopełnienie na wszystkich pozycjach to $(4,1,6,3,2,2)$. Zwrócenie dowolnej z tych tablic jest poprawne. Pierwsze wywołanie query({}) zwraca $(5,5)$. Powyższe wyjście odpowiada wynikowi uruchomienia załączonego programu wzorcowego; różne poprawne programy mogą używać różnej liczby zapytań.

Ograniczenia

Dla wszystkich danych testowych $1\le n\le 500$.

Wynik każdego podzadania jest wyznaczany na podstawie testu o najniższym mnożniku punktów w tym podzadaniu; szczegóły podano poniżej.

Podzadania

Jeśli odpowiedź zwrócona przez recover jest niepoprawna, argumenty query są nieprawidłowe lub liczba zapytań przekracza $Q_{\max}$, wynik dla tego testu wynosi $0$.

W przeciwnym razie w podzadaniach $1,2$ test otrzymuje pełną liczbę punktów. W podzadaniach $3,4$ niech $Q$ oznacza faktyczną liczbę zapytań użytych w danym teście. Mnożnik punktów $f(Q)$ jest obliczany według poniższej tabeli:

Wynik podzadania $3$ wynosi $40f(Q)$, a wynik podzadania $4$ wynosi $40f(Q)$. Ostateczny wynik jest zaokrąglany do $3$ miejsc po przecinku.

Limit czasu: $2\ \mathrm{s}$.

Limit pamięci: $512\ \mathrm{MiB}$.