Problem Description

One day, Inu asked Neko a question:
Give you a sequence with $n$ elements. The index for the first element is $0$, the last is $n-1$.
They are arranged in rings. $0$ and $n-1$ are next to each other.
The $i$-th element has a character $s[i]$ which is '(' or ')'.
Let $f(i, d)$ means the last place to arrive by starting with $i$ and taking $d$ steps.
If you are in $i$-th element now and $s[i] = $'(', you will arrive $(i-k+n)\%n$-th element in next step, or you will arrive $(i+k)\%n$-th element.
And there are $q$ questions.Each question has three integers $l, r, d$. You have to calculate $\sum_{i = l}^{r} f(i,d)$

Input

The first line contains three integers $n, q, k(1 \leq n, q \leq 10^{5}, 1 \leq k < n)$ .
The second line contains a sequence, the $i$-th element means $s[i]$ .
The next $q$ line, each line contains three integers $l,r,d(0 \leq l \leq r < n, 1 \leq d \leq 10^{9})$ .

Output

For each question output the sum in one line.

6 5 1
())()(
0 1 3
1 3 2
1 4 3
2 5 6
0 3 4

7
8
12
14
12