Problem D
Martian DNA

CC-BY-SA 2.0, Enzymlogic by DNMT1 via Flickr

For martians, however, things are a bit different; top secret research conducted on the martian that was recently captured by NASA, revealed that its DNA consisted of a whopping $K$ distinct nucleobases! The caputured martian’s DNA may thus be represented as a string over an alphabet of size $K$.

A certain research group interested in exploiting martian DNA in artificial intelligence applications has requested to get a single consecutive piece of the martian DNA string. For $R$ of the nucleobases, they have specified a minimum quantity of how many they need of that particular nucleobase to be present in the sample.

For reasons related to computational complexity, they prefer the shortest substring of the DNA which satisfies their requirements. Your job is to find it.

Input

The first line contains three integers $N$, $K$, and $R$, denoting the total length of the martian DNA, the alphabet size, and the number of nucleobases for which the researchers have a minimum quantity requirement, respectively. They obey $1 \le R \le K \le N \le 200\, 000$.

The second line contains $N$ space-separated integers: the complete martian DNA string. The $i$-th of these integers, $D_ i$, indicates what nucleobase is in the $i$-th position of the DNA string. Nucleobases are $0$-indexed, i.e. $0 \leq D_ i < K$. Each nucleobase will occur at least once in the DNA string.

Each of the following $R$ lines contains two integers $B$ and $Q$ representing a nucleobase and its mimimum required quantity, respectively ($0 \le B < K, 1 \le Q \le N$). No nucleobase will be listed more than once in these $R$ lines.

Output

Output a single integer, the length of the shortest consecutive substring of the DNA that satisfies the researchers’ requirements. 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