Như bạn có thể đã biết, DNA của con người có thể được biểu diễn bằng một xâu dài trên bảng chữ cái gồm bốn ký hiệu A, C, G, T. Mỗi ký hiệu biểu thị một loại bazơ nitơ khác nhau, lần lượt là adenine, cytosine, guanine và thymine.

Tuy nhiên, với người sao Hỏa thì mọi thứ hơi khác. Nghiên cứu trên người sao Hỏa mới nhất mà NASA bắt được cho thấy DNA của họ có tới \(K\) loại bazơ nitơ khác nhau! Vì vậy, DNA của người sao Hỏa có thể được biểu diễn bằng một xâu trên bảng chữ cái gồm \(K\) ký hiệu.

Một nhóm nghiên cứu muốn khai thác DNA của người sao Hỏa trong các ứng dụng trí tuệ nhân tạo đã yêu cầu lấy một đoạn liên tiếp duy nhất của một xâu DNA. Với \(R\) loại bazơ nitơ, họ chỉ định số lượng tối thiểu của từng loại cần có trong mẫu.

Bạn cần tìm đoạn con ngắn nhất của xâu DNA thỏa mãn các yêu cầu đó.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(K\) và \(R\), lần lượt là tổng độ dài của xâu DNA, số loại bazơ nitơ và số loại mà các nhà nghiên cứu yêu cầu một số lượng tối thiểu.

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn toàn bộ xâu DNA. Số nguyên thứ \(i\), ký hiệu là \(D_i\), cho biết loại bazơ nitơ ở vị trí thứ \(i\). Các loại bazơ được đánh số từ \(0\) đến \(K-1\). Mỗi loại xuất hiện ít nhất một lần trong xâu DNA.

Mỗi dòng trong \(R\) dòng tiếp theo chứa hai số nguyên \(B\) và \(Q\), lần lượt là một loại bazơ và số lượng tối thiểu cần có của loại đó. Không có loại bazơ nào được liệt kê nhiều hơn một lần trong \(R\) dòng này.

Dữ liệu ra

In ra một số nguyên là độ dài của đoạn con liên tiếp ngắn nhất thỏa mãn yêu cầu của các nhà nghiên cứu. Nếu không tồn tại đoạn con như vậy, in ra impossible.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le R \le K \le N\).
• \(0 \le D_i < K\) với mọi \(1 \le i \le N\).
• Mỗi loại bazơ từ \(0\) đến \(K-1\) xuất hiện ít nhất một lần trong xâu DNA.
• Với mỗi yêu cầu, \(0 \le B < K\) và \(1 \le Q \le N\).
• Các giá trị \(B\) trong \(R\) yêu cầu đôi một khác nhau.

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (16 điểm): \(1 \le N \le 100\), \(R \le 10\).

• Nhóm 2 (24 điểm): \(1 \le N \le 4\,000\), \(R \le 10\).
• Nhóm 3 (28 điểm): \(1 \le N \le 200\,000\), \(R \le 10\).
• Nhóm 4 (32 điểm): \(1 \le N \le 200\,000\); không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.