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)$
输入解释
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})$ .