← 返回题目列表

AtCoder · ddcc2019_final_d

D. 迪斯科!

中文机器翻译题面 查看原题

配点: 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