Problem G
Марсианская ДНК

Как вам наверное известно, человеческую ДНК можно записать в виде длинной строки над алфавитом из четырех символов (A, C, G, T), где каждый символ обозначает определённое нуклеотидное основание (аденин, цитозин, гуанин и тимин, соответственно).

У марсиан, однако, всё не так. Недавние исследования над захваченным недавно NASA марсианином выявили, что марсианская ДНК содержит $K$ различных нуклеотидных оснований! Поэтому её можно записать в виде строки над алфавитом из $K$ символов.

Некая группа исследователей, желающая начать использовать марсианскую ДНК для разработки искусственного интеллекта, запросила отрезок последовательности марсианской ДНК. Для $R$ нуклеотидных оснований исследователи указали минимальное их количество, которое должно присутствовать в отрезке.

Вам необходимо найти самый короткий возможный отрезок ДНК, удовлетворяющий требованиям исследователей.

Ввод

На первой строке даны три целых числа $N$, $K$, и $R$ ($1 \le R \le K \le N$), обозначающих суммарную длину марсианской ДНК, размер алфавита, и число нуклеотидных оснований, для которых исследователи указали минимальное требуемое их количество.

На второй строке даны $N$ разделенных пробелами целых чисел – вся марсианская последовательность ДНК. $i$-тый элемент $D_ i$ этой последовательности указывает нуклеотидное основание в соответствующей позиции марсианской ДНК. Нуклеотидные основания нумеруются с $0$, т.е. $0 \leq D_ i < K$. Каждое основание встречается в последовательности как минимум один раз.

На каждой из следующих $R$ строк даны два целых числа $B$ и $Q$ – нуклеотидное основание и минимальное требуемое количество этого основания в искомом отрезке ($0 \le B < K, 1 \le Q \le N$). Ни одно основание не будет упомянуто этом списке более одного раза.

Вывод

Вывести одно целое число – длину кратчайшего отрезка (подстроки) ДНК, удовлетворяющего требованиям исследователей. Если такого отрезка не существует, вывести текст “impossible”.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Объяснение примеров

В первом примере существует три отрезка длиной $2$, которые содержат по одному вхождению нуклеотидных оснований 0 и 1 (а именно: “0 1”, “1 0” и “0 1”), а отрезков длиной $1$, удовлетворяющих этому условию, не существует. Поэтому ответ – $2$.

Во втором примере, единственная оптимальная подстрока – “1 3 2 0 1 2 0”.

В третьем примере недостаточно нуклеотидных оснований типа 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