Problem Description

This problem is translated from BalticOI 2018 Day 1 “Martian DNA”.

You are given a string of length $N$ over an alphabet of size $|\Sigma| = K$, and $R$ requirements. Each requirement is: in the substring, character $B$ must appear at least $Q$ times. Find the length of the shortest substring that satisfies all requirements.

Input Format

The first line contains three integers $N,\, K,\, R$, representing the length of the string, the size of the alphabet, and the number of requirements. It is guaranteed that $1\leqslant R\leqslant K\leqslant N$.
The second line contains $N$ space-separated integers describing the string. Characters are numbered starting from $0$, and every character in the alphabet appears at least once.
The next $R$ lines each contain two integers $B$ and $Q$, describing one requirement. It is guaranteed that $0\leqslant B < K,\, 1\leqslant Q\leqslant N$, and no character will be required more than once.

Output Format

Output one integer: the length of the shortest substring that satisfies all requirements. In particular, if no such substring exists, output "impossible".

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

Hint

Explanation for Sample 1

There are three substrings of length $2$ that contain one occurrence each of characters $0$ and $1$: 0 1, 1 0, and 0 1. However, there is no substring of length $1$ that satisfies the requirements, so the shortest valid substring has length $2$.

Explanation for Sample 2

The shortest substring that satisfies the requirements is 1 3 2 0 1 2 0.

Explanation for Sample 3

In this string, the number of 0 is not enough.

Thanks to Hatsune_Miku for providing the translation.

Translated by ChatGPT 5