如你所知，人类 DNA 可以表示为一个长度为 4 的字母表（A, C, G, T）上的长字符串，其中每个符号代表一种不同的核碱基（分别为腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶）。

然而，对于火星人来说，情况有所不同；NASA 捕获的最新火星人研究表明，火星 DNA 由多达 $K$ 种不同的核碱基组成！因此，火星 DNA 可以表示为长度为 $K$ 的字母表上的字符串。

现在，一个对利用火星 DNA 进行人工智能应用感兴趣的研究小组请求获得一段火星 DNA 字符串的连续片段。对于其中的 $R$ 种核碱基，他们指定了在样本中必须包含的每种核碱基的最低数量。

你需要找到满足他们要求的最短 DNA 子串。

输入格式

第一行包含三个整数 $N$、$K$ 和 $R$，分别表示火星 DNA 的总长度、字母表大小以及研究人员有最低数量要求的核碱基种类数。它们满足 $1 \le R \le K \le N$。

第二行包含 $N$ 个空格分隔的整数：完整的火星 DNA 字符串。其中第 $i$ 个整数 $D_i$ 表示 DNA 字符串第 $i$ 个位置上的核碱基。核碱基从 0 开始编号，即 $0 \le D_i < K$。每种核碱基在 DNA 字符串中至少会出现一次。

接下来的 $R$ 行，每行包含两个整数 $B$ 和 $Q$，分别表示一种核碱基及其最低需求数量（$0 \le B < K, 1 \le Q \le N$）。在这 $R$ 行中，每种核碱基最多只会出现一次。

输出格式

输出一个整数，表示满足研究人员要求的最短连续 DNA 子串的长度。如果不存在这样的子串，则输出 “impossible”。

数据范围

你的解决方案将在多组测试数据上进行测试，每组测试数据包含若干测试点。为了获得某一组测试点的分数，你需要通过该组内的所有测试点。最终得分为单次提交的最高得分。

说明

在第一个样例中，有三个长度为 2 的子串各包含一个核碱基 0 和 1（即 “0 1”、“1 0” 和 “0 1”），但没有长度为 1 的子串满足要求。因此最短长度为 2。

在第二个样例中，（唯一的）最优子串是 “1 3 2 0 1 2 0”。

在第三个样例中，核碱基 0 的数量不足。

样例

样例输入 1

5 2 2
0 1 1 0 1
0 1
1 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

样例输出 2

7

样例输入 3

5 3 1
1 2 0 1 2
0 2

样例输出 3

impossible