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 hóa 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~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 500\,000)~ 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 \cdot 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.

Output

• 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.

Scoring

Sample Input 1

3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5

Sample Output 1

7 3 5 3 1

Notes

• Cặp ~l, r~ đầu tiên yêu cầu đếm số lượng chuỗi con của toàn bộ chuỗi khớp với các chuỗi trong tập hợp.

  • Các chuỗi con khớp với "aba" là ~[1, 3]~ và ~[5, 7]~.

  • Các chuỗi con khớp với "a" là ~[1, 1], [3, 3], [5, 5], [7, 7]~.

  • Chuỗi con khớp với "ac" là ~[3, 4]~.

Tổng cộng có ~7~ chuỗi con của "abacaba" khớp với các chuỗi từ tập hợp.

• Trong cặp ~l, r~ thứ hai, chuỗi con từ vị trí ~1~ đến ~3~ của chuỗi gốc được lấy, đó là chuỗi "aba". Trong đó, chuỗi "aba" xuất hiện ~1~ lần, chuỗi "a" xuất hiện ~2~ lần và chuỗi "ac" không xuất hiện lần nào. Tổng là ~3~.

• Trong cặp ~l, r~ thứ ba, chuỗi con từ vị trí ~2~ đến ~7~ của chuỗi gốc được lấy, đó là chuỗi "bacaba". Trong đó, chuỗi "aba" xuất hiện ~1~ lần, chuỗi "a" xuất hiện ~3~ lần và chuỗi "ac" xuất hiện ~1~ lần. Tổng là ~5~.

• Tương tự cho các cặp ~l, r~ còn lại.