„Er ist ein Gesetzloser und er ist berühmt, Andrii Popa, der Mutige.

Tag und Nacht reitet er, Er fordert seinen Tribut an der Hauptstraße Und überall im Land Rennen die Diebesfänger davon, so schnell sie können“

— „Andrii Popa“, Phoenix

Ghiță besitzt eine $0$-indizierte Folge $S$ aus $N$ positiven ganzzahligen Gewichten. Da er der König der Karpaten ist, möchte er einen Binärbaum konstruieren, dessen Knoten die Indizes $0, 1, \ldots, N - 1$ tragen, sodass Folgendes gilt:

• Die Inorder-Traversierung des Baums liefert die Knoten in aufsteigender Reihenfolge ihrer Indizes. Die Inorder-Traversierung eines Binärbaums setzt sich zusammen aus der Inorder-Traversierung des Teilbaums mit Wurzel im linken Kind der Wurzel (falls dieses Kind existiert), gefolgt vom Index der Wurzel, gefolgt von der Inorder-Traversierung des Teilbaums mit Wurzel im rechten Kind der Wurzel (falls dieses Kind existiert).
• Wenn Knoten $x$ der Elternknoten von Knoten $y$ ist, dann teilt $S_x$ den Wert $S_y$.

Wir erinnern daran, dass ein Binärbaum eine Baumdatenstruktur ist, in der jeder Knoten höchstens zwei Kinder hat, die als linkes Kind und rechtes Kind bezeichnet werden.

Unglücklicherweise hat der berühmte Gesetzlose Andrii Popa die Folge $S$ gestohlen, sodass Ghiță nicht mehr direkt auf sie zugreifen kann. Mithilfe fortschrittlicher Technologie (seines Mobiltelefons) kann er für je zwei zusammenhängende Teilfolgen $[a, b]$ und $[c, d]$ von $S$ herausfinden, ob $\gcd[a, b]$ gleich $\gcd[c, d]$ ist, wobei $\gcd[x, y]$ der größte gemeinsame Teiler von $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$ ist. Leider ist diese Technologie ziemlich teuer — wenn Ghiță sie öfter als $Q$-mal verwendet, muss er eine hohe Geldstrafe zahlen. Hilf ihm, indem du die Technologie höchstens $Q$-mal verwendest, um den gewünschten Baum zu konstruieren. Es wird garantiert, dass dies möglich ist. Jede gültige Lösung wird akzeptiert.

Interaktion

Der Teilnehmer muss den Header popa.h (C / C++) einbinden oder popa.pas (Pascal) implementieren. Der Teilnehmer muss die folgende Funktion implementieren:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

Diese Funktion soll die Wurzel des Baums zurückgeben und $\text{Left}_i$ sowie $\text{Right}_i$ auf das linke bzw. rechte Kind des Knotens $i$ setzen. Falls Knoten $i$ kein linkes Kind hat, muss $\text{Left}_i$ gleich $-1$ sein. Falls Knoten $i$ kein rechtes Kind hat, muss $\text{Right}_i$ gleich $-1$ sein. Left und Right zeigen auf zwei bereits reservierte Arrays der Größe genau $N$.

Die Funktion solve wird im Verlauf eines einzelnen Programmlaufs höchstens $5$-mal aufgerufen. Wir empfehlen, beim Verwenden globaler Variablen vorsichtig zu sein.

Der Teilnehmer darf die folgende Funktion verwenden:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

Diese Funktion gibt genau dann $1$ zurück, wenn $\gcd[a, b]$ gleich $\gcd[c, d]$ ist, wobei $0 \le a \le b < N$ und $0 \le c \le d < N$ gilt, und andernfalls $0$.

Teilaufgaben

Teilaufgabe 1 (37 Punkte)

• $N = 100$
• $Q = 10000$

Teilaufgabe 2 (24 Punkte)

• $N = 1000$
• $Q = 20000$

Teilaufgabe 3 (39 Punkte)

• $N = 1000$
• $Q = 2000$

Beispiele

Ein Beispiel für die Interaktion bei $S = [12, 4, 16, 2, 2, 20]$ lautet:

Hinweis

Ein Beispiel für einen Baum der Art, wie Ghiță ihn für das obige Beispiel sucht, ist: