TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

40.9% (9/22)

Tags

Description

昨天ot吃飽太閒,亂改了你在Messenger綽號
你決定要讓ot付出代價★KiRa✰
你在下午把ot約出來跟他打架
戰鬥畫面異常火爆
你的每一拳都有一個LL仇恨值,代表你可以對ot造成的傷害大小
如果你在ot意識不清楚打出了Combo,那你造成的傷害大小就可以有加乘效果
計算公式為$ S_{i , j} := \prod_{x=i} ^ {j} a_x $,代表從第$i$拳到第$j$拳打出的Combo造成的傷害值
經過一番纏鬥,那個改你綽號的廢物★Nico✰終於敗在正義的手下
ot雖然發誓說它不會再亂改別人的綽號
但是他有一個條件,那就是他希望你能算出在你剛打出的傷害的某段區間中
如果加上了Combo的話,總共可以打出多少傷害,也就是計算$ \sum_{i=l} ^ {r} \sum_{j=i} ^ {r} S_{i, j} $
但總傷害值可能會太大,所以需要取除以M的餘數
你覺得這麼簡單的題目簡直是汙辱你的智商,所以跟ot說
他可以選擇兩個數字$L,R$,你則回答加上了Combo後的總傷害值
你能讓ot不再亂改別人的綽號嗎?

Input Format

第一行給定三個正整數N,Q,M
$(1 \le M \le 10 ^ 9 )$ $(1 \le N,Q \le 3 \times 10 ^ 5 )$
第二行為你打出的LL仇恨值所形成的序列
接下來Q行為詢問
美行有兩個數字$L,R$
請輸出第L拳到第R拳加上了Combo的話可以造成的傯傷害值
$(1 \le L \le R \le N )$

Output Format

對於每次詢問,請輸出加入了Combo後造成的總傷害值

Sample Input

5 3 10
1 2 3 4 5
1 3
2 4
4 5

Sample Output

0
1
9

Hints

子任務(測資)額外限制分數
1(0~4)$N \le 500,Q \le 10 ^ 3$13
2(5~14)$N,Q \le 2 \times 10 ^ 3 $36
2(15~29)51

但是你已經聽膩了他在胡說八道
所以決定把ot掛掉了

Problem Source

Problem Set By oToToT

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 14, Score: 36
For Testdata: 15 ~ 29, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 2000 262144 65536
5 2000 262144 65536
6 2000 262144 65536
7 2000 262144 65536
8 2000 262144 65536
9 2000 262144 65536
10 2000 262144 65536
11 2000 262144 65536
12 2000 262144 65536
13 2000 262144 65536
14 2000 262144 65536
15 2000 262144 65536
16 2000 262144 65536
17 2000 262144 65536
18 2000 262144 65536
19 2000 262144 65536
20 2000 262144 65536
21 2000 262144 65536
22 2000 262144 65536
23 2000 262144 65536
24 2000 262144 65536
25 2000 262144 65536
26 2000 262144 65536
27 2000 262144 65536
28 2000 262144 65536
29 2000 262144 65536