双串区间对照

题目描述

给定两个字符串 $A$ 与 $B$（仅包含小写字母）。你将收到若干次查询，每次给出 $A$ 的一个区间 $[l_1,r_1]$ 与 $B$ 的一个区间 $[l_2,r_2]$。

请你对每次查询输出：$A[l_1..r_1]$ 与 $B[l_2..r_2]$ 的最长公共子序列长度。

下标从 $1$ 开始。

输入格式

输入共三部分。

• 第一行是字符串 $A$。
• 第二行是字符串 $B$。
• 第三行包含一个整数 $q$，表示查询次数。
• 接下来 $q$ 行，每行四个整数 $l_1,r_1,l_2,r_2$。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的答案。

输入输出样例 #1

输入 #1

abac
cab
3
1 4 1 3
2 3 1 3
1 2 2 3

输出 #1

2
1
2

数据范围

对于所有测试数据，保证：

• $1 \le |A|,|B| \le 200$；
• $1 \le q \le 200$；
• $1 \le l_1 \le r_1 \le |A|$；
• $1 \le l_2 \le r_2 \le |B|$。