Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

E. 天师桩阵
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

北部禁区曾长期被危险的侵蚀能量笼罩，如今已被成功收复。为了让区内的设施重新投入使用，庄方宜需要在禁区内铺设「天师桩阵列」，稳定裂隙周围残留的侵蚀能量。

重建队伍已经沿一条施工线路从左到右设置了 $$$m$$$ 个辅桩，编号为 $$$1$$$ 到 $$$m$$$。每个辅桩携带一种能量信号，分为「阴爻」和「阳爻」两类，分别用字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 表示，因此这 $$$m$$$ 个辅桩可以表示为一个长度为 $$$m$$$ 的 01 串 $$$S$$$。

队伍拥有数量不限的主桩。为了激活一个主桩，需要按照一个长度为 $$$n$$$ 的 01 串 $$$T$$$ 所规定的顺序连接并激活辅桩：从 $$$S$$$ 中选择 $$$n$$$ 个位置 $$$p_1 \lt p_2 \lt \cdots \lt p_n$$$，使得按从左到右的顺序读出这些位置上的字符恰好得到 $$$T$$$，即：

$$$$$$ S_{p_i} = T_i \quad (1 \le i \le n). $$$$$$

若同时激活多个主桩，它们之间的共振将相互干扰，因此必须完整激活一个主桩后，才能开始激活下一个主桩。形式化地，如果依次激活了 $$$k$$$ 个主桩，第 $$$j$$$ 个主桩选择的位置为 $$$p_{j,1} \lt p_{j,2} \lt \cdots \lt p_{j,n}$$$，那么需要满足：

$$$$$$ \begin{cases} S_{p_{j,i}} = T_i & (1 \le j \le k,\ 1 \le i \le n), \\ p_{j,n} \lt p_{j+1,1} & (1 \le j \lt k). \end{cases} $$$$$$

受地形和施工进度影响，重建队伍准备了 $$$q$$$ 种相互独立的施工方案，第 $$$i$$$ 种方案中只有编号位于区间 $$$[l_i, r_i]$$$ 内的辅桩可以使用。对于每种施工方案，请你求出该方案最多能够成功激活的主桩数量。

Input

第一行三个整数 $$$n$$$、$$$m$$$、$$$q$$$（$$$1 \le n \le 100$$$，$$$n \le m \le 2 \times 10^5$$$，$$$1 \le q \le 2 \times 10^5$$$），分别表示 01 串 $$$T$$$ 的长度、辅桩的数量、施工方案的数量。

第二行一个长度为 $$$n$$$ 的 01 串 $$$T$$$（仅包含字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$），表示激活一个主桩所需的辅桩类型顺序。

第三行一个长度为 $$$m$$$ 的 01 串 $$$S$$$（仅包含字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$），表示从左到右每个辅桩的类型。

接下来 $$$q$$$ 行，其中第 $$$i$$$ 行两个整数 $$$l_i$$$ 和 $$$r_i$$$（$$$1 \le l_i \le r_i \le m$$$），表示第 $$$i$$$ 种施工方案只能使用编号位于区间 $$$[l_i, r_i]$$$ 内的辅桩。

Output

对于每种施工方案，输出一行一个非负整数，表示该方案中最多能够成功激活的主桩数量。

Example
Input
3 10 3
110
0101101010
1 10
1 6
3 9
Output
2
1
1
Note

样例中，对于第一种施工方案，我们可以使用区间 $$$[1, 10]$$$ 内的辅桩。我们用以下策略可以依次激活两个主桩：

  • 第一个主桩选择位置 $$$2$$$、$$$4$$$、$$$6$$$ 的辅桩，由于 $$$S_2S_4S_6 = \mathtt{110} = T$$$，因此符合要求；
  • 第二个主桩选择位置 $$$7$$$、$$$9$$$、$$$10$$$ 的辅桩，由于 $$$S_7S_9S_{10} = \mathtt{110} = T$$$，因此符合要求。

可以证明，不存在激活更多主桩的方案，因此第一种施工方案的答案为 $$$2$$$。