Không phải bài toán xâu kinh điển

Có một bài toán xâu kinh điển: cho hai xâu $A$ và $B$, hãy đếm số lần xâu $A$ xuất hiện trong xâu $B$.

Tiến sĩ Hùng không muốn bài toán dễ như vậy, nên ông cho bạn hai xâu $S$, $T$ và $q$ truy vấn. Mỗi truy vấn gồm hai cặp chỉ số $(i,j)$ và $(u,v)$. Với mỗi truy vấn, Tiến sĩ Hùng hỏi số lần xâu $X=S_i{S}_{i+1}\dots S_j$ xuất hiện trong xâu $Y=T_u{T}_{u+1}\dots T_v$.

Một lần xuất hiện của $X$ trong $Y$ là một vị trí bắt đầu trong $Y$ mà từ đó $|X|$ ký tự liên tiếp của $Y$ trùng với $X$; các lần xuất hiện được phép chồng lên nhau.

Dữ liệu vào

• Dòng đầu tiên chứa xâu $S$.
• Dòng thứ hai chứa xâu $T$.
• Dòng thứ ba chứa số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $i$, $j$, $u$, $v$.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng chứa một số nguyên là số lần xuất hiện tương ứng với truy vấn.

Ràng buộc

• $1\le |S|\le 2\times {10}^5$, $1\le |T|\le 2\times {10}^5$.
• $S$ và $T$ chỉ gồm chữ cái Latin thường.
• $1\le q\le 5\times {10}^5$.
• $1\le i\le j\le |S|$, $1\le u\le v\le |T|$ (các chỉ số đánh số từ $1$).

Ví dụ