Đếm chuỗi con

Công ty khởi nghiệp DroneX được đầu tư sản xuất hàng loạt các máy bay không người lái (drone) phục vụ nông nghiệp. Sản phẩm của họ trợ giúp cho người nông dân có thể bón phân qua lá cho các cây có độ cao lớn như sầu riêng, hồ tiêu, điều, ... Drone của họ cũng được sử dụng trong việc vận chuyển hàng hoá tới các vùng khó khăn, những nơi mà các phương tiện bình thường khác không thể tiếp cận. Mô hình kinh doanh của họ cũng đặc biệt: sản phẩm của họ không bán, chỉ cho thuê trực tiếp tại các cửa hàng tiện ích. Để kích hoạt drone khởi động, khách hàng phải nhập dãy số gồm $m$ số bí mật, nếu chúng trùng khớp trong hệ thống của công ty, drone sẽ được kích hoạt tự động và sẵn sàng bay.

Mỗi khi có khách đến thuê drone, cửa hàng sẽ cung cấp cho khách hàng một chuỗi kí tự $t$ và một tập hợp $n$ chuỗi $s_1,s_2,s_3,\dots ,s_n$. Để lấy được $m$ số bí mật, công ty sẽ gửi cho mỗi khách hàng $m$ cặp chỉ số $l,r$. Nhiệm vụ của khách hàng là với mỗi cặp chỉ số $l,r$ đó, lấy chuỗi con của $t$ từ kí tự thứ $l$ đến ký tự thứ $r$ và đếm số lượng chuỗi con này nếu trùng khớp với chuỗi nào đó từ tập đã cho. Thứ tự các số bí mật tìm được phải trùng với thứ tự của các cặp $l,r$ mà khách hàng nhận được.

Sau khi có kết quả, khách hàng sẽ gửi về cho công ty, nếu trùng khớp, drone đã sẵn sàng khởi động.

Một cách tiếp cận khác: Đếm số cặp vị trí $(a,b)$ sao cho $l_i\le a\le b\le r_i$ và chuỗi con của chuỗi $t$ từ vị trí $a$ đến $b$ khớp với một chuỗi $s_j$ nào đó từ tập hợp đã cho.

Chuỗi con của chuỗi $t$ từ vị trí $a$ đến $b$ là chuỗi được tạo ra bằng cách xóa $a-1$ ký tự đầu và $|t|-b$ ký tự cuối của $t$, trong đó $|t|$ là độ dài của chuỗi $t$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $m$ $(1\le n,m\le 500000)$ lần lượt là số lượng chuỗi trong tập hợp mà cửa hàng gửi cho khách hàng và số lượng cặp $l,r$ mà công ty gửi cho khách hàng.
• Dòng thứ hai chứa duy nhất chuỗi $t$, chỉ bao gồm các chữ cái tiếng Anh viết thường $(1\le |t|\le 5\times {10}^6)$.
• $n$ dòng tiếp theo mô tả các chuỗi trong tập hợp. Dòng thứ $i$ chứa duy nhất một chuỗi $s_i$, bao gồm các chữ cái tiếng Anh viết thường. Gọi $S$ là tổng độ dài của tất cả các chuỗi trong tập hợp. Dữ liệu luôn đảm bảo $S\le {10}^6$, và tất cả các chuỗi $s_i$ là khác nhau.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $l_i$ và $r_i$ $(1\le l_i\le r_i\le |t|)$ lần lượt là biên trái và biên phải của chuỗi con lấy ra từ chuỗi $t$ từ cặp $l,r$ thứ $i$.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Dữ liệu ra

Một dòng duy nhất ghi dãy số bí mật tìm được để gửi kích hoạt drone, trong đó số thứ $i$ là kết quả của cặp $l,r$ thứ $i$. Các số cách nhau bởi một dấu cách.

Ràng buộc

• $1\le n,m\le 500000$.
• $1\le |t|\le 5\times {10}^6$; $t$ và các $s_i$ chỉ gồm chữ cái tiếng Anh viết thường.
• $S\le {10}^6$, các chuỗi $s_i$ đôi một khác nhau.
• $1\le l_i\le r_i\le |t|$.

Subtasks

Điểm được tính theo từng test; số test của mỗi subtask tương ứng với tỉ lệ điểm.

• Subtask 1 ($12\%$ số điểm): $n\le 100$, $m\le 100$, $|t|\le 100$, $S\le 10000$.
• Subtask 2 ($14\%$ số điểm): $n\le 100$, $m\le 500$, $|t|\le 5000$.
• Subtask 3 ($11\%$ số điểm): $n\le 5000$, $|t|\le 5000$.
• Subtask 4 ($10\%$ số điểm): $n\le 100$, $|t|\le 50000$.
• Subtask 5 ($12\%$ số điểm): $|t|\le 100000$, $S\le 100000$.
• Subtask 6 ($10\%$ số điểm): $|t|\le 250000$, $S\le 100000$.
• Subtask 7 ($10\%$ số điểm): $|t|\le 500000$, $S\le 100000$.
• Subtask 8 ($10\%$ số điểm): $|t|\le 750000$, $S\le 100000$.
• Subtask 9 ($11\%$ số điểm): Không có ràng buộc bổ sung.

Ví dụ