这个问题在某些国家可能广为人知，但如果没人提出，其他国家的人又该如何了解这类问题呢？

给定一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。$s$ 的字符编号从 $1$ 到 $n$。

同时给定 $m$ 个模式串，其中第 $i$ 个模式串为 $s[tl_i \dots tr_i]$（包含两端）。

现在有 $q$ 次询问。每次询问由两个端点 $ql_i$ 和 $qr_i$ 表示。对于每次询问，你需要求出有多少个模式串在 $s[ql_i \dots qr_i]$（包含两端）中至少出现过一次。

输入格式

第一行包含三个整数：$n, m, q$ ($1 \le n \le 4 \cdot 10^5$; $1 \le m, q \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串 $s$。

接下来的 $m$ 行描述模式串。第 $i$ 行包含两个整数 $tl_i$ 和 $tr_i$ ($1 \le tl_i \le tr_i \le n$)。

接下来的 $q$ 行描述询问。第 $i$ 行包含两个整数 $ql_i$ 和 $qr_i$ ($1 \le ql_i \le qr_i \le n$)。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 次询问的答案。

样例

输入 1

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

输出 1

1
2