접두사-부분 문자열 LCS

길이가 $M$인 문자열 $S$와 길이가 $N$인 문자열 $T$가 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리한다.

• $a$ $b$ $c$: $(S_0, S_1, \dots, S_{a-1})$와 $(T_b, T_{b+1}, \dots, T_{c-1})$의 최장 공통 부분 수열의 길이를 출력한다.

제한 조건

• $1 \leq M \leq 1000$
• $1 \leq N \leq 1000$
• $1 \leq Q \leq 500000$
• $0 \leq a_i \leq M$
• $0 \leq b_i \leq c_i \leq N$
• $S$와 $T$의 각 문자는 영문 소문자이다.

$Q$
$S$
$T$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{Q-1}$ $b_{Q-1}$ $c_{Q-1}$

$a$ $b$ $c$: $(S_0, S_1, \dots, S_{a-1})$와 $(T_b, T_{b+1}, \dots, T_{c-1})$의 최장 공통 부분 수열의 길이를 출력한다.