Problem G
火星人のDNA

ご存知の方も多いと思いますが、ヒトのDNAは4つのアルファベット（A, C, G, T） で構成される長い文字列で表され、 それぞれの文字は異なる核酸塩基（それぞれアデニン、シトシン、グアニン、チミン）を表しています。

NASAが捉えた最新の火星人を調査した結果、火星人のDNAはなんと$K種類$もの異なる核酸塩基で 構成されていることが明らかになったのです！このことから、火星人のDNAは $K$個のアルファベットで構成される文字列として表せるそうです。

さて、火星人のDNAを人工知能の応用に利用しようとしているある研究グループが、 火星人のDNAの文字列の連続した一片を取得するように要求してきました。 $R$個の核酸塩基に対して、サンプル中に存在するその核酸塩基の数の最小値を指定しています。

あなたは、彼らの要求を満たすDNAの最短部分文字列を見つけることに興味があります。

入力

最初の行には、3つの整数$N$, $K$, $R$が含まれており、 それぞれ火星人のDNAの長さ、アルファベットの種類数、研究者が最低限必要とする核酸塩基の数を表しています。 これらは、$1 \le R \le K \le N$を満たします。

2行目には、スペースで区切られた$N$個の整数によって、火星人のDNAの完全な文字列が表されています。 これらの整数のうち、$i$番目の整数である$D_ i$は、DNA文字列の$i$番目の位置にどの核酸塩基があるかを示しています。 核酸塩基は$0$から始まる番号で表されます。すなわち、$0 \leq D_ i < K$です。 各核酸塩基は、DNAの文字列の中に少なくとも1個は含まれます。

以降の$R$行には、それぞれ核酸塩基とその最小必要量を表す整数$B$と$Q$($0 \le B < K, 1 \le Q \le N$)が含まれています。 これらの$R$行には、同じ核酸塩基が2回以上リストアップされることはありません。

出力

研究者の要求を満たすDNAの最も短い連続した部分文字列の長さを1つの整数で出力します。 もしそのような部分文字列が存在しなければ、 “impossible”を出力します。

制約

あなたのソリューションは、テストグループのセットでテストされ、それぞれのグループにポイントが定義されています。 各テストグループにはテストケースのセットが含まれています。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースが成功する必要があります。 あなたの最終的なスコアは、1回の提出での最大スコアとなります。

サンプルの説明

最初の例では、核酸塩基0と1からなる長さ$2$の文字列が3つ(それぞれ、“0 1”、“1 0”、“0 1”)含まれています。 しかし長さ$1$の部分文字列はありません。したがって、最短の長さは$2$となります。

2番目の例では、最短の部分文字列は“1 3 2 0 1 2 0”です。

3番目の例では、核酸塩基0は必要な数を満たしていません。