Problem Description

This problem is a translation from BalticOI 2018 Day1 "Martian DNA"

Given a string of length \( N \) with a character set size \( |\Sigma| = K \), and \( R \) requirements, each requiring that character \( B \) appears at least \( Q \) times in a substring. Find the shortest substring length that satisfies all requirements.

Input Format

The first line includes three integers \( N \), \( K \), and \( R \), representing the length of the string, the size of the character set, and the number of requirements, respectively. It is guaranteed that \( 1 \leqslant R \leqslant K \leqslant N \).

The second line contains \( N \) integers separated by spaces, representing the string. Characters are numbered from \( 0 \), and each character in the set appears at least once.

The next \( R \) lines each contain two integers \( B \) and \( Q \), representing a requirement, where \( 0 \leqslant B < K \) and \( 1 \leqslant Q \leqslant N \). The same character will not be required twice.

Output Format

Output a single integer, the shortest substring length that satisfies all requirements. If no such substring exists, output "impossible".

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

7

Sample Input #3

5 3 1
1 2 0 1 2
0 2

Sample Output #3

impossible

Notes

Sample 1 Explanation

There are three substrings of length \( 2 \) that each contain one character \( 0 \) and one character \( 1 \), namely 0 1, 1 0, and 0 1. However, no substring of length \( 1 \) satisfies the requirements, so the shortest substring length that meets the requirements is \( 2 \).

Sample 2 Explanation

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

Sample 3 Explanation

In this string, the character 0 is insufficient.

见题面 Input 部分

见题面 Output 部分