配点: 700 点
問題文
Takahashi 是一个字符串 我写了 S 。下一个 请回答 Q 问题。 一组使得
- 質問 q (1 \leq q \leq Q): 整数 L_q, R_q 。
来自行S_i =
D, S_j =I, S_k =S, S_l =C, S_m =O存在多少个 (i, j, k, l, m) (L_q \leq i < j < k < l < m \leq R_q) ?数量 除以 2^{32} 时的余数 查找 。 长度由
制約
- S 是
D,I,S,C,O组成 1 \ 000 \ 000 以下字符串 输出 - 1 \leq Q \leq 100 \ 000
- 1 \leq L_q \leq R_q \leq |S|
- L_q, R_q 是整数
入力
输入将以以下形式通过标准输入给出。
S Q L_1 R_1 L_2 R_2 L_3 R_3 : L_Q R_Q
出力
Q 行。q 在线提问 输出 q 的答案。
入力例 1
DDDDDDISCOOOOOO 7 6 10 5 11 4 12 3 13 2 14 1 15 1 8
出力例 1
1 4 9 16 25 36 0
入力例 2
DDDIIISSSCCCOOO 12 1 12 1 13 1 14 1 15 2 12 2 13 2 14 2 15 3 13 3 14 3 15 4 15
出力例 2
0 81 162 243 0 54 108 162 27 54 81 0