Problem G
Mars-DNA

Wie du sicherlich weißt, kann menschliche DNA durch einen langen String über einem Alphabet mit vier Elementen (A, C, G, T) dargestellt werden, wobei jedes Symbol eine bestimmte Nukleinbase darstellt (Adenin, Cytosin, Guanin und Thymin).

Für Marsianer ist das allerdings anders; Studien an dem letzten von der NASA gefangenen Marsianer zeigten, dass Mars-DNA aus $K$ verschiedenen Nukleinbasen besteht! Mars-DNA kann also als String über einem Alphabet mit $K$ Elementen dargestellt werden.

Eine gewisse Forschungsgruppe, die sich für die Anwendungsmöglichkeiten der Mars-DNA im Bereich der Künstlichen Intelligenz interessiert, hat ein zusammenhängendes Stück eines Mars-DNA-Strings zur Untersuchung beantragt. Für $R$ der Nukleinbasen haben sie spezifiziert, wie oft diese mindestens in dem DNA-String vorkommen sollen.

Du möchtest den kürzesten Teilstring finden, der diese Bedingungen erfüllt.

Eingabe

Die erste Zeile enthält drei ganze Zahlen $N$, $K$ und $R$, die die Gesamtlänge der Mars-DNA, die Alphabet-Größe und die Anzahl der Nukleinbasen, für die die Forscher eine Mindesthäufigkeit angegeben haben, spezifizieren. Es gilt $1 \le R \le K \le N$.

Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen: Den vollständigen Mars-DNA-String. Die $i$-te dieser ganzen Zahlen, $D_ i$, gibt an, welche Nukleinbase sich an der $i$-ten Position des DNA-Strings befindet. Die Nukleinbasen sind $0$-indiziert, also gilt $0 \leq D_ i < K$. Jede Nukleinbase wird mindestens einmal im DNA-String vorkommen.

Jede der folgenden $R$ Zeilen enthält zwei ganze Zahlen $B$ und $Q$, die jeweils eine Nukleinbase und ihre minimal benötigte Häufigkeit angeben ($0 \le B < K, 1 \le Q \le N$). Keine Nukleinbase wird mehr als einmal in diesen $R$ Zeilen aufgeführt.

Ausgabe

Gib eine einzelne ganze Zahl aus: die Länge des kürzesten zusammenhängenden Teilstrings der DNA, der die Anforderungen der Forscher erfüllt. Falls ein solcher Teilstring nicht existiert, gib “impossible” aus.

Beschränkungen

Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.

Beschreibung der Beispiele

Im ersten Beispiel gibt es drei Teilstrings der Länge $2$, die die Nukleinbasen 0 und 1 jeweils einmal enthalten (nämlich “0 1”, “1 0” und “0 1”), aber es gibt keinen solchen Teilstring der Länge $1$. Die kürzeste Länge ist also $2$.

Im zweiten Beispiel ist der (einzige) optimale Teilstring “1 3 2 0 1 2 0”.

Im dritten Beispiel gibt es nicht genug Nukleinbasen des Typs 0.

5 2 2
0 1 1 0 1
0 1
1 1

2

13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

7

5 3 1
1 2 0 1 2
0 2

impossible