{"code":"beads","name":"Chuỗi hạt nhiều màu","description":"Bạn vừa được tặng một chuỗi hạt nhiều màu rất đẹp!\r\n\r\n
\r\n\r\nĐể thuận tiện, ta kí hiệu những hạt cùng màu sắc bằng những kí tự giống nhau. Chúng ta sẽ dùng $26$ kí tự Latin in thường (`a`-`z`) để biểu diễn các hạt khác màu nhau. Như vậy, chuỗi hạt được tặng có thể biểu diễn dưới dạng một xâu $S$ có $n$ kí tự. Chuỗi hạt được gọi là *phong thủy* nếu nó chứa các hạt màu may mắn theo đúng thứ tự. Gọi $P$ là chuỗi may mắn (gồm $m$ kí tự).\r\n\r\nĐể kiểm tra một chuỗi hạt có phong thủy hay không, ta làm như sau:\r\n- **B0:** Chọn một hạt làm hạt bắt đầu trong xâu $s$ và đánh dấu nó.\r\n- **B1:** Đặt $i = 1$.\r\n- **B2:** Nếu $i > m$ thì kết thúc quá trình tìm kiếm.\r\n- **B3:** Nếu hạt hiện tại trùng với hạt thứ $i$ trong chuỗi may mắn, gán $i = i+1$.\r\n- **B4:** Lần chuỗi hạt tới vị trí tiếp theo.\r\n- **B5:** Nếu lần tới hạt được đánh dấu (hạt bắt đầu), ta kết thúc quá trình tìm kiếm vì đã đi được một vòng.\r\n- **B6:** Quay lại bước 2.\r\n\r\nSau khi thực hiện xong các bước trên, nếu $i > m$ thì ghi nhận $S$ là chuỗi phong thủy.\r\n\r\nVí dụ, với $S =$ `dab`, $P =$ `bd` thì $S$ là chuỗi phong thủy vì:\r\n- Ta bắt đầu tại hạt thứ $2$ là `a`.\r\n- `a` không trùng với hạt thứ $i = 1$ trong $P$, lần chuỗi hạt tới vị trí tiếp theo.\r\n- `b` trùng với hạt thứ $i = 1$ trong $P$, ta gán $i = 2$, sau đó lần chuỗi hạt tới vị trí tiếp theo.\r\n- `d` trùng với hạt thứ $i = 2$ trong $P$, ta gán $i = 3$, lần chuỗi hạt tới vị trí tiếp theo. Do hạt tiếp theo là hạt bắt đầu nên ta kết thúc.\r\n- Do $i = 3 > m$ nên chuỗi $S$ có **chứa** chuỗi may mắn $P$.\r\n\r\nBạn cần xác định chuỗi hạt cho trước có hợp phong thủy hay không?\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa số nguyên $n$ ($1 \\leq n \\leq 10 ^ 4$).\r\n- Dòng tiếp theo chứa xâu $S$ độ dài $n$.\r\n- Dòng tiếp theo chứa số nguyên $m$ ($1 \\leq m \\leq \\min(n, 10 ^ 2)$).\r\n- Dòng tiếp theo chứa xâu $P$ độ dài $m$.\r\n\r\n

Output

\r\n\r\n- Nếu chuỗi hạt hợp phong thủy, in ra vị trí bắt đầu mà bạn chọn: $j$ với $(1 \\le j \\le n)$ nghĩa là bạn bắt đầu từ vị trí $j$ của chuỗi $S$.\r\n- Ngược lại, in ra số $0$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($50\\%$ số điểm): $n \\leq 10 ^ 2$.\r\n- Subtask $2$ ($30\\%$ số điểm): $m \\leq 3$.\r\n- Subtask $3$ ($20\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3\r\n dab\r\n 2\r\n bd\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```","points":1500.0,"partial":true,"time_limit":0.1,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}