题目译自 BalticOI 2018 Day1「Martian DNA」

题目描述

给定一个字符集大小 $$|\Sigma| = K$$ 的长度为 N 的字符串和 R 个要求，每个要求为使子串中的字符 B 至少出现 Q 次。求出满足所有要求的最短子串长度。

输入格式

第一行包括三个整数 N, K, R，分别表示字符串的长度、字符集的大小和要求个数，保证 $$1 \leqslant R \leqslant K \leqslant N$$。

第二行包含 N 个用空格隔开的整数，表示这个字符串。字符从 0 开始编号，每个字符集中的字符至少出现一次。

接下来的 R 行，每行两个整数 B 和 Q，表示一组要求，满足 $$0 \leqslant B < K$$，$$1 \leqslant Q \leqslant N$$，同一个字符不会被重复要求两次。

输出格式

输出一个整数，满足所有要求的最短子串长度。特别地，如果不存在这样的子串，输出 "impossible"。

样例 1

输入

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

输出

2

解释

有三个长度为 2 的子串含有字符 0 和 1 各一个，分别为 0 1、1 0 和 0 1，但是不存在长度为 1 的子串满足要求，因此满足要求的最短子串的长度为 2。

样例 2

输入

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

输出

7

解释

最短的满足要求的子串为 1 3 2 0 1 2 0。

样例 3

输入

5 3 1
1 2 0 1 2
0 2

输出

impossible

解释

在这个字符串中，字符 0 的数量不足。

数据范围与提示

子任务	分值	限制
1	16	$$1 \leqslant N \leqslant 100$$，$$R \leqslant 10$$
2	24	$$1 \leqslant N \leqslant 4,000$$，$$R \leqslant 10$$
3	28	$$1 \leqslant N \leqslant 200,000$$，$$R \leqslant 10$$
4	32	$$1 \leqslant N \leqslant 200,000$$

请注意：在 LibreOJ 上共有 5 个子任务，其中第一个子任务为样例。