多次询问的最优长度

题目描述

给定两个字符串 $A$ 与 $B$（仅包含小写字母）。你将收到若干次询问，每次给出一个整数 $k$。

在一次询问中，你可以修改 $A$ 中最多 $k$ 个字符（每个字符可改为任意小写字母），然后计算修改后的 $A'$ 与 $B$ 的最长公共子序列长度。

请输出每次询问的最大可能长度。

输入格式

输入共三部分。

• 第一行是字符串 $A$。
• 第二行是字符串 $B$。
• 第三行包含一个整数 $q$，表示询问次数。
• 接下来 $q$ 行，每行一个整数 $k$。

输出格式

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

输入输出样例 #1

输入 #1

abc
aaa
3
0
1
2

输出 #1

1
2
3

样例解释 #1

• $k=0$ 时不能修改，最长公共子序列为 a，长度为 $1$；
• $k=1$ 时可以把 b 改成 a，得到 aac，最长公共子序列长度为 $2$；
• $k=2$ 时可以把 b,c 都改成 a，得到 aaa，最长公共子序列长度为 $3$。

数据范围

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

• $1 \le |A|,|B| \le 200$；
• $1 \le q \le 200$；
• $0 \le k \le |A|$。