Trong buổi học đầu tiên ở lớp, huyhau6a2 được cho một xâu $s$ gồm $n$ ký tự chỉ bao gồm các chữ cái tiếng anh viết thường. Cô đã dạy cho huyhau6a2 một số định nghĩa như sau:

• Một xâu con của xâu $s$ được tạo ra bằng cách bỏ bớt một số ký tự liên tiếp ở đầu và ở cuối của xâu $s$, với $s[l\rightarrow r]$ là xâu con $s_l s_{l+1}\dots s_r$.
• Gọi $p_i$ là hậu tố bắt đầu từ vị trí $i$ của xâu $s$, định nghĩa $p_i=s[i\rightarrow n]$.
• Gọi $lcp(s_1,s_2,\dots,s_x)$ là giá trị $k$ lớn nhất sao cho $s_1[1\rightarrow k]=s_2[1\rightarrow k]=\dots=s_x[1\rightarrow k]$ và $s_1,s_2,\dots,s_x$ là các xâu bất kỳ

Sau buổi học, cô giáo đã cho huyhau6a2 $q$ truy vấn, mỗi truy vấn gồm 2 số $l,r$. Nhiệm vụ của huyhau6a2 là với mỗi truy vấn, hãy tính giá trị của $lcp(p_l,p_{l+1},\dots,p_r)$.

huyhau6a2 đã giải xong rồi, và giờ đây chính là thử thách dành cho các bạn!

4 3
abbb
1 2
2 3
2 4

0
2
1