Chú ý: Những nhân vật và tình tiết dưới đây phỏng theo một tiểu thuyết không có thật trên mạng internet. Mọi sự tương đồng với những cá nhân có thật, nếu có, đều là trùng hợp ngẫu nhiên. Các bạn có thể tham khảo thêm tại đây.

Admin trẻ tuổi nhất của cộng đồng Vinoy — VLT — sinh ra trong gia tộc V.L. danh gia vọng tộc đứng thứ 2 thế giới chỉ sau gia tộc N.H. Trong truyện, cậu được miêu tả một cách vô cùng hư cấu như sau:

• Ngoại hình : soái ca, vô cùng đẹp trai cao 1 mét 86 đôi mắt hổ phách mái tóc bạch kim
• Tính cách : lạnh lùng thờ ơ chỉ bên người thân mới ấm áp và rất yêu nó, siêu quậy
• IQ : 300 / 300 giỏi tất cả các loại võ chuyên về sử dụng súng và chế tạo vũ khí

Gần đây, VLT vừa khám phá ra một văn tự cổ xưa, nghi rằng có liên quan đến gia tộc V.L.

Đáng ngạc nhiên là văn tự này lại được viết bằng bảng chữ cái Latin in thường. Ngay lập tức, VLT bắt tay vào việc giải mã văn tự này. Với IQ 300/300 của mình, VLT suy luận rằng manh mối chắc chắn nằm ở một đoạn liên tiếp của văn tự và có liên quan đến tên của một trong các tổ tiên của mình. Tất nhiên, VLT đã có sẵn gia phả bao gồm tên của \(𝑛\) tổ tiên thuộc gia tộc V.L. Như một truyền thống, thành viên thứ \(𝑖\) gia tộc V.L. được đặt tên giống với tên của một tổ tiên \(𝑥_𝑖\) trước đó, ghép với "tên riêng" là một xâu \(𝑠_𝑖\) không rỗng gồm các chữ cái Latin viết thường. Ví dụ, nếu tổ tiên thứ nhất có tên là "\(𝑣𝑢𝑜𝑛𝑔\)", \(𝑥_2 = 1, 𝑠_2 =\) "\(𝑙𝑜𝑛𝑔\)" thì tổ tiên thứ hai sẽ có tên là "\(𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔\)". Tương tự, nếu \(𝑥_3 = 2, 𝑠_3 =\) "\(𝑡𝑜𝑎𝑛\)" thì tổ tiên thứ ba sẽ có tên là "\(𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔𝑡𝑜𝑎𝑛\)".

Vấn đề duy nhất còn lại là VLT không chắc là manh mối nằm ở đoạn nào của văn tự, do đó cậu chọn ra \(𝑞\) đoạn văn, đoạn thứ \(𝑖\) gồm các kí tự thứ từ \(𝑙_𝑖\) tới \(𝑟_𝑖\) của văn tự. Với mỗi đoạn văn, VLT muốn biết số thứ tự của tổ tiên có tên có thứ tự từ điển lớn nhất nhưng không lớn hơn đoạn văn đang xét.

Nhắc lại, xâu ký tự \(𝑠 = 𝑠_1𝑠_2 … 𝑠_𝑚\) có thứ tự từ điển nhỏ hơn xâu ký tự \(𝑡 = 𝑡_1𝑡_2 … 𝑡_𝑛\) khi và chỉ khi một trong hai điều kiện sau được thoả mãn:

• \(𝑚 < 𝑛\) và \(𝑠_1 = 𝑡_1, 𝑠_2 = 𝑡_2, … , 𝑠_𝑚 = 𝑡_𝑚\). Nói cách khác, \(𝑠\) là một tiền tố thực sự của \(𝑡\).
• Tồn tại chỉ số \(𝑖\) thoả mãn \(𝑖 < min(𝑚, 𝑛)\), \(𝑠_1 = 𝑡_1, 𝑠_2 = 𝑡_2, … , 𝑠_𝑖 = 𝑡_𝑖\) và \(𝑠_{𝑖+1} < 𝑡_{𝑖+1}\).

Input

• Dòng đầu tiên chứa số nguyên \(𝑇\) – số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa xâu ký tự gồm từ 1 tới \(5 \times 10^5\) chữ cái in thường thể hiện văn tự cổ xưa mà VLT khám phá được.
• Dòng thứ ba chứa số nguyên \(𝑛\) – số tổ tiên thuộc gia tộc V.L.
• Trong \(𝑛\) dòng tiếp theo, dòng thứ \(𝑖\) chứa số nguyên \(𝑥_𝑖\) và xâu ký tự \(𝑠_𝑖\) (gồm từ 1 tới \(5 \times 10^5\) chữ cái in thường), cho biết tên của thành viên thứ \(𝑖\) trong gia tộc được tạo ra bằng cách ghép tên của thành viên thứ \(𝑥_𝑖\) với tên riêng \(𝑠_𝑖\). Nếu \(𝑥_𝑖 = 0\), tên của thành viên thứ \(𝑖\) chính là \(𝑠_𝑖\). Tổng độ dài của các xâu \(𝑠_1, 𝑠_2, … , 𝑠_𝑛\) không quá \(5 \times 10^5\).
• Dòng tiếp theo chứa số nguyên \(𝑞\) – số đoạn văn mà VLT quan tâm.
• Trong \(𝑞\) dòng cuối cùng, dòng thứ \(𝑖\) chứa hai số nguyên \(𝑙_𝑖\) và \(𝑟_𝑖\) với \(𝑝\) là độ dài văn tự cổ, cho biết đoạn văn thứ \(𝑖\) được tạo ra bởi cách lấy các ký tự từ vị trí \(𝑙_𝑖\) tới vị trí \(𝑟_𝑖\) của văn tự cổ. Các ký tự được đánh số từ 1.

Output

• Gồm \(𝑞\) dòng, dòng thứ \(𝑖\) chứa một số nguyên duy nhất là số thứ tự của tổ tiên có tên có thứ tự từ điển lớn nhất nhưng không lớn hơn đoạn văn thứ \(𝑖\). Nếu nhiều tổ tiên cùng thoả mãn điều kiện này, in ra số thứ tự của tổ tiên có số thứ tự nhỏ nhất. Nếu không có tổ tiên nào thoả mãn, in ra −1. Các tổ tiên được đánh số từ 1 tới \(𝑛\).

Constraints

• \(1 ≤ 𝑇 ≤ 4\)
• \(1 ≤ 𝑛 ≤ 3 \times 10^5\)
• \(0 ≤ 𝑥_𝑖 < 𝑖\)
• \(1 ≤ 𝑞 ≤ 3 \times 10^5\)
• \(1 ≤ 𝑙_𝑖 ≤ 𝑟_𝑖 ≤ 𝑝\)

Scoring

• Subtask \(1\) (\(8.3\%\) số điểm): \(𝑛, 𝑞 ≤ 2000\). Văn tự cổ và tên của mỗi người trong dòng họ có không quá 2000 kí tự.
• Subtask \(2\) (\(26.6\%\) số điểm): Tổng độ dài của \(𝑞\) đoạn văn tự cần xét (tổng của các \(𝑟_𝑖 − 𝑙_𝑖 + 1\)) không quá \(10^7\).
• Subtask \(3\) (\(28.3\%\) số điểm): \(𝑥_1 = 𝑥_2 = ⋯ = 𝑥_𝑛 = 0\).
• Subtask \(4\) (\(36.6\%\) số điểm): Không có ràng buộc gì thêm.

Example

2 
vuonglongtoanatgmaildotcomorz 
6 
0 vuong 
1 long 
2 tu 
1 hoang 
2 toan 
4 long 
6 
1 13 
1 4 
1 6 
14 26 
29 29 
1 8  

5 
-1 
6 
-1 
3
6

1 
aaabcbdaac 
6 
0   a 
1   bc 
0 ab 
3 c 
3 ab 
1 ab 
6 
1 3 
3 5 
2 2 
8 10 
10 10 
9 10  

1 
2 
1 
6 
2 
2