# #697. 【候选队互测2022】广为人知题

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?

### 输出格式

$q$ 行，每行一个整数，依次表示每个查询的答案。

### 样例一

#### input

5 2 2
abaab
3 4
4 5
2 4
1 5



#### output

1
3



### 数据范围

$1$ $10^3$ $10^3$ $10^3$ $10$
$2$ $5 \times 10^4$ $10^5$ $5 \times 10^4$ $25$
$3$ $4 \times 10^5$ $10^6$ $10^5$ 保证 $S$ 的所有字符独立地在 bc 中均匀随机生成 $20$
$4$ $4 \times 10^5$ $10^6$ $10^5$ $45$