83. 活在恐懼中的老師

活在恐懼中的老師

• 在校園中，有一位不為人知的英文老師，他每天都在學生的威脅下害怕的上課，這樣的情況他也習慣了，但有些學生更進一步的積極爭取幹掉他的機會，也幸好他有天生的防禦技能—閃光彈，得以躲過來自四面八方的攻擊，不過每次上課還是要戰戰兢兢，而且學生有個特殊的功能，就是英文老師走過的地方會讓那些學生的仇恨值加總起來，仇恨值就是學生想幹掉老師的程度，因為老師可以投擲閃光彈，所以說有些學生是不會看到他走過去的，也就不會累積仇恨值，雖然你的英文不好，但為了救助瀕危的英文老師，你決定寫個程式來救他，如果你不寫的話他會叫小老師扣你分喔
• 我們可以假設所有學生是排成一直線，老師會給你每個學生的仇恨值，並且問你某一段學生的仇恨值總和

輸入說明

• 只有一筆測資，第一行有二個正整數$n$($0 \leq n \leq 100000$)、$q$($0 \leq q \leq 100000$)，代表有幾個學生，跟幾筆詢問
• 第二行有$n$個正整數$s$($0 \leq s \leq 1000$)，代表每個學生的仇恨值
• 接下來有$q$行，每行有兩個整數$a$,$b$表示要求第$a$個學生跟第$b$個學生的仇恨值總和

輸出說明

• 輸出每筆詢問的仇恨值總和，每筆輸出完要換行

範例輸入:

5 3
1 2 3 4 5
0 4
1 4
0 2

範例輸出:

15
14
6

配分:

配分	限制
1%	$n = 0$
9%	$s = 0$
20%	$n \leq 1000$ & $q \leq 1000$
70%	沒有限制
時限	100ms
記憶體	100000 bytes

Judge Setting

run-time limit: 100 ms
memory limit: 100000 byte
測資數量: 0