접두사와 부분 문자열의 LCS

길이가 각각 $N$, $M$인 문자열 $S$, $T$와 $Q$개의 질의가 주어진다. $S$의 인덱스는 $0$부터 $N-1$까지이고, $T$의 인덱스는 $0$부터 $M-1$까지이다. $S[l,r)$와 $T[l,r)$는 각 문자열에서 인덱스가 $l$ 이상 $r$ 미만인 부분 문자열을 뜻한다.

두 문자열의 LCS는 공통으로 나타나는 부분 수열 중 가장 긴 부분 수열이다. 먼저 $S$와 $T$의 LCS 길이를 구하고, 각 질의 $(I,L,R)$에 대해 $S[0,I)$와 $T[L,R)$의 LCS 길이를 구해 보자.

첫 번째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. $(0 \le N, M \le 4\,000; 1 \le Q \le 2\,000)$

두 번째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다.

세 번째 줄에 알파벳 소문자로 이루어진 문자열 $T$가 주어진다. 빈 문자열도 한 줄을 차지한다.

네 번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $I$, $L$, $R$이 공백으로 구분되어 주어진다. $(0 \le I \le N; 0 \le L \le R \le M)$

첫 번째 줄에 두 문자열 $S$, $T$의 LCS 길이를 출력한다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 $S[0,I)$와 $T[L,R)$의 LCS 길이를 질의가 주어진 순서대로 출력한다.