c29837877f697e2bb6bce5011d64ab04 ~(2^7)~

sau khi chật vật chất xám, vật lộn với việc giải câu đố của Peace, Matcha Latte không thích mình bị động nên đã dẫn cậu bạn thân của mình đến một vườn hoa gần nhà mình và thách đố với nhưng câu hỏi tương tự, nhưng với một phiên bản khó hơn.

Vì số lượng hoa ở đây quá lớn nên Peace không thể giải các câu đố trong một khoảng thời gian ngắn và nhiệm vụ của bạn là thay thế anh chàng này giải quyết các câu hỏi mà Matcha Latte đã đưa ra nhằm gây ấn tượng với cô bạn này nhé!

Vì đây là vườn hoa gần nhà Matcha Latte, rất nhiều hoa nên theo lí thuyết, nhiều hoa thì số lượng câu hỏi sẽ phong phú hơn vườn hoa gần nhà Peace nên giới hạn bài này thuộc loại khó: ~1 \leq n \leq 69420, 1 \leq q \leq 69420~.

Input

• Dòng thứ nhất gồm một xẫu kí tự ~s~.
• Dòng thứ hai là một số nguyên dương ~q~.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương ~l, r, u, v~.

Output

• Gồm ~q~ dòng, mỗi dòng in ra một số nguyên tương ứng với đáp án của mỗi câu đố.

Example input 1

abacaba
3
1 3 5 7
2 4 4 6
1 1 7 7

Example output 1

3
1
1

Note 1

• Câu đố ~1~: ~l = 1, r = 3, u = 5, v = 7~.

  • Khu vực A: ~s[0..2]~ ~=~ aba
  • Khu vực B: ~s[4..6]~ ~=~ aba
  • So sánh: a bằng a, b bằng b, a bằng a ~\rightarrow~ có ~3~ vị trí giống nhau.

• Câu đố ~2~: ~l = 2, r = 4, u = 4, v = 6~.

  • Khu vực A: ~s[1..3]~ ~=~ bac
  • Khu vực B: ~s[3..5]~ ~=~ cab
  • So sánh: b khác c, a bằng a, c khác b ~\rightarrow~ có ~1~ vị trí giống nhau.

• Câu đố ~3~: ~l = 1, r = 1, u = 7, v = 7~.

  • Khu vực A: ~s[0..0]~ ~=~ a
  • Khu vực B: ~s[6..6]~ ~=~ a
  • So sánh: a bằng a ~\rightarrow~ có ~1~ vị trí giống nhau.