Một hệ thống lưu ~n~ mật khẩu dạng vòng tròn. Với một mật khẩu vòng tròn, việc chọn vị trí bắt đầu đọc không quan trọng. Vì vậy hai xâu được xem là tương đương nếu xâu này có thể thu được từ xâu kia bằng một phép xoay vòng.

Ví dụ, ~\text{abca}~, ~\text{bcaa}~, ~\text{caab}~ và ~\text{aabc}~ là các mật khẩu tương đương.

Có ~q~ truy vấn. Mỗi truy vấn cho đoạn chỉ số ~[l, r]~ và một xâu ~t~. Cần đếm số mật khẩu trong các vị trí từ ~l~ đến ~r~ tương đương với ~t~.

Yêu cầu

Với mỗi truy vấn, in ra số lượng mật khẩu ~s_i~ với ~l \le i \le r~ sao cho ~s_i~ tương đương với ~t~ theo phép xoay vòng.

Dữ liệu

Dữ liệu vào từ chuẩn gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa mật khẩu ~s_i~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~, ~r~ và một xâu ~t~.

Kết quả

Ghi ra ~q~ dòng, mỗi dòng chứa đáp án của truy vấn tương ứng.

Ví dụ

Ví dụ 1

Input

5 5
abca
bcaa
abcd
aaaa
dabc
1 5 aabc
2 4 caab
1 3 bcda
3 5 cdab
1 5 aa

Output

2
1
0
2
0

Giải thích

Ví dụ 1

Trong toàn bộ danh sách, hai mật khẩu đầu tiên tương đương với ~\text{aabc}~.

Mật khẩu ~\text{abcd}~ và ~\text{dabc}~ tương đương với ~\text{cdab}~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, q \le 2 \cdot 10^5~.
• Tổng độ dài của ~n~ mật khẩu ban đầu không vượt quá ~4 \cdot 10^5~.
• Tổng độ dài của các xâu ~t~ trong truy vấn không vượt quá ~4 \cdot 10^5~.
• Mọi xâu chỉ gồm chữ cái tiếng Anh thường.

Chấm điểm

• Subtask~1~ ~(20\%)~: ~n, q \le 2000~, tổng độ dài các xâu không vượt quá ~5000~.
• Subtask~2~ ~(25\%)~: mọi xâu có cùng độ dài.
• Subtask~3~ ~(25\%)~: không có hai mật khẩu ban đầu tương đương nhau.
• Subtask~4~ ~(30\%)~: không có ràng buộc bổ sung.