COCI 2019/2020 - Contest 3 - Grudanje

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 3
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Patrik thích học những từ tiếng Anh, đặc biệt là những từ có chính xác ~N~ chữ cái. Khi mà anh ấy thấy một từ như thế, anh ấy ngay lập tức bắt đầu quan sát ~Q~ từ con trong số những từ con của từ đó, và với mỗi từ con đó, anh ấy xác định xem liệu những chữ cái trong từ con đó có phân biệt hay không. Nếu cả ~Q~ từ con đó đều có các chữ cái phân biệt, anh ấy sẽ cho rằng từ ban đầu là hoàn hảo.

Krešimir không thích học tiếng anh, thay vì thế, anh ấy thích mém những quả bóng tuyết vào Patrik. Vào một buổi sáng mùa đông lạnh lẽo, anh ấy đang đi xung quanh thị trấn và mang theo đúng ~N~ quả bóng tuyết và va phải Patrik, người đang quan sát một chữ khổng lồ có ~N~ kí tự được viết lên tường bởi những tên côn đồ. Thật là trùng hợp ...

Krešimir mém quả bóng tuyết đầu tiên về hướng của Patrik, nhưng Patrik đã né nó một cách điêu luyện và nó đã trúng và che phủ hoàn toàn kí tự thứ ~p_1~ của từ được viết ở trên tường. Chính xác hơn, Krešimir cũng thất bại trong việc ném trúng người Patrik với ~N-1~ quả bóng tuyết tiếp theo. Quả bóng tuyết thứ ~i~ không đi trúng Patrik mà trúng vào tường và đã che phủ chữ cái thứ ~p_i~ của từ đó ở trên tường. Thú vị hơn nữa, sau khi Krešimir ném tất cả các quả bóng tuyết thì toàn bộ từ được viết trên tường đã bị che phủ bởi tuyết.

Patrik nhìn thoáng qua từ đã bị che phủ hoàn toàn và kết luận, nó là một từ hoàn hảo. Do đó, anh ấy phải sửa lại một chút định nghĩa của anh ấy về một từ hoàn hảo. Một từ sẽ là từ hoàn hảo nếu không có bất kì từ con nào trong ~Q~ từ con của từ đó có cặp chữ cái mà chưa bị che phủ bởi tuyết và cặp chữ cái đó giống nhau. Giờ anh ấy muốn biết chính xác sau bao nhiêu quả bóng tuyết được ném (có thể là ~0~ quả) thì từ ở trên tường trở nên hoàn hảo.

Input

Dòng đầu tiên chứa ~1~ từ có ~N~ chữ cái viết thường ở bảng chữ cái tiếng Anh. ~(1 \le N \le 10^5)~.

Dòng thứ ~2~ chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~ như trong đề bài đã mô tả.

Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo chứa ~2~ số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i \le b_i \le N)~ cho biết rằng từ con thứ ~i~ trong số ~Q~ từ con như trong đề bài đề cập bắt đầu từ chữ cái thứ ~a_i~ và kết thúc ở chữ cái thứ ~b_i~ của từ ban đầu ở trên tường.

~N~ dòng tiếp theo chứa ~N~ số nguyên ~p_i~ khác nhau ~(1 ≤ p_i ≤ N)~ như trong đề bài mô tả.

Output

In ra số nguyên duy nhất là số thứ tự của quả bóng tuyết (có thể bằng ~0~) mà sau khi được ném làm cho từ ở trên tường trở nên hoàn hảo.

Sample 1

Input
aaaaa 
2 
1 2 
4 5 
2 4 1 5 3
Output
2

Sample 2

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

Sample 3

Input

abcd
1
1 4
1 2 3 4
Output
0

Subtask

  • ~2~ test có ~1 \le N,Q \le 500~.
  • ~6~ test tiếp theo có ~1 \le N,Q \le 3000~.
  • ~2~ test còn lại, từ ban đầu ở trên tường chỉ có chữ cái ~a~.

Giải thích test ví dụ thứ 2:

Trạng thái của từ ở trên tường sau mỗi quả bóng tuyết là:

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.