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ứ 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 kimTí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ậyIQ : 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 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à 𝑣𝑢𝑜𝑛𝑔, 𝑙𝑜𝑛𝑔 thì tổ tiên thứ hai sẽ có tên là 𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔. Tương tự, nếu 𝑡𝑜𝑎𝑛 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ự có thứ tự từ điển nhỏ hơn xâu ký tự khi và chỉ khi một trong hai điều kiện sau được thoả mãn:
và . 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 và
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số thứ tự của subtask chứa test này.
Dòng thứ hai chứa xâu ký tự gồm từ tới 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 là 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ừ tới 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 , tên của thành viên thứ chính là . Tổng độ dài của các xâu không quá .
Dòng tiếp theo chứa số nguyên là 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ừ .
Dữ liệu ra:
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 . Các tổ tiên được đánh số từ tới .
Giới hạn:
Subtask . Văn tự cổ và tên của mỗi người trong dòng họ có không quá kí tự
Subtask Tổng độ dài của đoạn văn tự cần xét tổng của các không quá
Subtask
Subtask Không có ràng buộc gì thêm.
Ví dụ:
Dữ liệu vào:
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
Dữ liệu ra:
5
-1
6
-1
3
6
Dữ liệu vào:
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
Dữ liệu ra:
1
2
1
6
2
2
Giải thích:
Trong ví dụ đầu tiên, tổ tiên trong gia tộc lần lượt có tên là 𝑣𝑢𝑜𝑛𝑔, 𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔,
𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔𝑡𝑢, 𝑣𝑢𝑜𝑛𝑔ℎ𝑜𝑎𝑛𝑔, 𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔𝑡𝑜𝑎𝑛, 𝑣𝑢𝑜𝑛𝑔ℎ𝑜𝑎𝑛𝑔𝑙𝑜𝑛𝑔. Các tổ tiên sắp xếp theo thứ tự tăng dần của tên là .
Đoạn văn cần xét thứ nhất là 𝑣𝑢𝑜𝑛𝑔𝑙𝑜𝑛𝑔𝑡𝑜𝑎𝑛. Tổ tiên số trùng với đoạn văn này.
Đoạn văn cần xét thứ hai là 𝑣𝑢𝑜𝑛. Tất cả tổ tiên có tên có thứ tự từ điển lớn hơn.
Trong ví dụ thứ hai, tổ tiên trong gia tộc lần lượt có tên là 𝑎, 𝑎𝑏𝑐, 𝑎𝑏, 𝑎𝑏𝑐, 𝑎𝑏𝑎𝑏, 𝑎𝑎𝑏.
Đoạn văn thứ hai cần xét là 𝑎𝑏𝑐. Tổ tiên số và số đều có tên có thứ tự từ điển lớn nhất không quá đoạn văn. Do đó được in ra vì có chỉ số nhỏ hơn.
