Patrik yêu thích nghiên cứu các từ trong tiếng Anh. Anh ấy đặc biệt yêu thích các từ có chính xác ~N~ chữ cái. Khi nhìn thấy một từ như vậy, anh ngay lập tức bắt đầu quan sát ~Q~ đoạn con của nó và đối với mỗi đoạn con đó, anh xác định liệu tất cả các chữ cái trong đó có khác nhau hay không. Nếu điều đó đúng với mỗi ~Q~ đoạn con, thì anh coi từ gốc là hoàn hảo.

Krešimir không thích nghiên cứu các từ tiếng Anh, anh thích ném bóng tuyết vào Patrik hơn. Vào một buổi sáng lạnh giá mùa đông, anh đang đi quanh thị trấn mang theo đúng ~N~ quả bóng tuyết và tình cờ gặp Patrik đang quan sát một từ khổng lồ gồm ~N~ chữ cái được viết trên tường bởi một số kẻ phá hoại. Thật là một sự trùng hợp...

Krešimir hăng hái ném quả bóng tuyết đầu tiên về phía Patrik, nhưng Patrik khéo léo né được quả bóng tuyết đó nên nó đã trúng và hoàn toàn che phủ chữ cái thứ ~p_1~ của từ trên tường. Theo cách tương tự, Krešimir đã không trúng Patrik với ~(N − 1)~ quả bóng tuyết tiếp theo. Chính xác hơn, quả bóng tuyết thứ ~i~ của anh không trúng Patrik và hoàn toàn che phủ chữ cái thứ ~p_i~ của từ trên tường. Thú vị thay, sau khi Krešimir ném tất cả các quả bóng tuyết, toàn bộ từ đã bị phủ kín tuyết.

Patrik nhìn thoáng qua từ đã bị phủ kín tuyết và kết luận rằng nó hoàn hảo. Vì vậy, anh cần phải thay đổi một chút định nghĩa về từ hoàn hảo của mình. Từ được coi là hoàn hảo nếu không có hai chữ cái nào giống nhau trong bất kỳ đoạn con ~Q~ nào mà không bị phủ tuyết. Bây giờ anh muốn biết sau quả bóng tuyết nào (có thể là không quả nào) từ trên tường trở nên hoàn hảo.

Input

• Dòng đầu tiên chứa một từ bao gồm ~N~ ~(1 \leq N \leq 10^5)~ chữ cái thường trong bảng chữ cái tiếng Anh.
• Dòng thứ hai chứa một số nguyên ~Q~ ~(1 \leq Q \leq 10^5)~ từ mô tả của bài toán.
• Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo chứa hai số nguyên ~a_i~ và ~b_i~ ~(1 \leq a_i \leq b_i \leq N)~ biểu thị rằng đoạn con thứ ~i~ trong ~Q~ đoạn con từ mô tả bài toán kéo dài từ chữ cái thứ ~a_i~ đến chữ cái thứ ~b_i~ của từ trên tường.
• Dòng tiếp theo chứa ~N~ số nguyên khác nhau ~p_i~ ~(1 \leq p_i \leq N)~ từ mô tả bài toán.

Output

Trong dòng duy nhất, bạn cần xuất ra số thứ tự của quả bóng tuyết sau khi từ trên tường trở nên hoàn hảo (có thể là không quả nào).

Chú ý

• Trong các trường hợp kiểm tra có tổng cộng 14 điểm, sẽ giữ ~(1 \leq N, Q \leq 500)~.
• Trong các trường hợp kiểm tra có thêm 21 điểm, sẽ giữ ~(1 \leq N, Q \leq 3000)~.
• Trong các trường hợp kiểm tra có thêm 14 điểm, từ sẽ chỉ chứa các chữ cái ~a~.

Sample Input 1

aaaaa
2
1 2
4 5
2 4 1 5 3

Sample Ouput 1

2

Sample Input 2

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

Sample Ouput 2

5

Sample Input 3

abcd
1
1 4
1 2 3 4

Sample Ouput 3

0

Giải thích

Trong test thứ hai: Trạng thái của từ trên tường sau mỗi lần ném bóng tuyết là:

abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********