问题 J: Widely Known Problem

You are given m patterns, where the i-th pattern is s[li…ri] (indices of s start from 1).

Now, there are q queries, and each query provides [Li,Ri]. For each query, you need to find how many j that the j-th pattern occurs in s[Li…Ri].

The first line of each test case contains three integer n, m, qn,m( 1≤n≤5×105, 1≤m,q≤106).

The second line contains a string ss of length n.

Each of the following mm lines contains two integers li,ri (1≤li≤ri≤n).

Each of the following q lines contains two integers Li,Ri (1≤Li≤Ri≤n).

It's guaranteed that ∑n≤9×105,∑m,∑q≤2×106.