Tèo và Tép là hai anh em thân thiết, mỗi người có một sở thích riêng. Trong khi Tèo luôn bị cuốn hút bởi việc khám phá những điều thú vị trong ngôn ngữ tiếng Anh, Tép lại thích những trò vui nhộn ngoài trời. Mùa đông này, cả hai quyết định cùng nhau đi du lịch đến một đất nước phủ đầy tuyết trắng.

Họ lang thang khắp các con phố cổ kính, tận hưởng không khí mùa đông tuyệt đẹp. Khi đi ngang qua một bức tường lớn, Tèo bất ngờ nhìn thấy một từ khổng lồ dài ~N~ chữ cái, được viết lên bởi những kẻ nghịch ngợm. Là người đam mê ngôn ngữ, Tèo lập tức bị thu hút và bắt đầu nghiên cứu từ này. Cậu đặc biệt yêu thích những từ có đúng ~N~ chữ cái và luôn kiểm tra ~Q~ từ con của chúng. Đối với mỗi từ con, Tèo kiểm tra xem liệu tất cả các chữ cái trong đó có hoàn toàn khác nhau hay không. Nếu điều kiện này đúng với mọi từ con, Tèo sẽ gọi từ đó là hoàn hảo.

Trong khi Tèo mải mê phân tích, Tép cảm thấy hơi chán. Cậu quyết định sử dụng những quả bóng tuyết đang cầm để trêu đùa anh trai. Với đúng ~N~ quả bóng tuyết trong tay, Tép bắt đầu ném. Cú ném đầu tiên, dù Tèo nhanh nhẹn né được, đã đập trúng chữ cái thứ ~p_i~ của từ trên tường, che phủ hoàn toàn chữ cái đó. Không dừng lại ở đó, Tép tiếp tục ném những quả bóng tiếp theo, mỗi lần lại che phủ một chữ cái khác của từ. Sau khi Tép ném hết ~N~ quả bóng, toàn bộ từ đã bị tuyết bao phủ hoàn toàn.

Nhìn vào từ đã bị che phủ, Tèo nhận thấy rằng nó trở nên hoàn hảo. Điều này buộc cậu phải thay đổi định nghĩa của mình: một từ được gọi là hoàn hảo nếu không có từ con nào trong số ~Q~ từ con chứa hai chữ cái giống nhau mà không bị tuyết che phủ.

Tèo giờ đây muốn biết rằng, sau cú ném thứ bao nhiêu của Tép (bao gồm cả trường hợp chưa ném cú nào), từ trên tường sẽ trở thành hoàn hảo.

Yêu cầu: Hãy giúp Tèo lập trình giải quyết yêu cầu trên.

Input

• Dòng đầu tiên ghi một từ gồm ~N~ ~(1 \le N \le 10^5)~ chữ cái thường trong bảng chữ cái tiếng Anh;

• Dòng thứ hai ghi một số nguyên dương ~Q~ ~(Q \le 10^5)~ đại diện cho số lượng từ con cần kiểm tra;

• ~Q~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên dương ~a_i~ và ~b_i~ ~(a_i \le b_i \le N)~, chỉ ra rằng từ con thứ ~i~ bắt đầu từ chữ cái thứ ~a_i~ và kết thúc tại chữ cái thứ ~b_i~ của từ trên tường;

• Dòng cuối cùng ghi ~N~ số nguyên dương ~p_i~ ~(p_i \le N)~, biểu thị thứ tự các chữ cái bị che phủ bởi từng quả bóng tuyết.

Hai số ghi trên cùng một dòng được phân cách với nhau bởi một dấu cách.

Output

Ghi một số nguyên biểu thị sau quả bóng tuyết thứ bao nhiêu (có thể là ~0~) thì từ trên tường trở thành hoàn hảo.

Scoring

Subtask	Điểm	Ràng buộc
1	~30\%~	~1 \le N, Q \le 500~
2	~30\%~	~1 \le N, Q \le 3000~
3	~20\%~	Từ chỉ chứa các chữ cái 'a'
4	~20\%~	Không có ràng buộc gì thêm

Sample Input 1

aaaaa
2
1 2
4 5
2 4 1 5 3

Sample Output 1

2

Sample Input 2

abbabaab
3
1 3
4 7
3 5
6 3 5 1 4 2 7 8

Sample Output 2

5

Sample Input 3

abcd
1
1 4
1 2 3 4

Sample Output 3

0

Notes

Ví dụ 2, tình trạng của từ trên tường sau mỗi lần ném bóng tuyết:

abbab*ab

ababab

aba*ab

ba**ab

b*ab

**ab

*b

**

Sau quả bóng tuyết thứ ~5~, từ trở thành hoàn hảo.