#HT9066. 环形补给线

环形补给线

环形补给线

时间限制:1 s  内存限制:256 MB

题目背景

罗德岛本舰的外围有一条环形补给公路,沿顺时针方向分布着 nn 个补给站,编号 1∼n1\sim n。第 ii 个补给站存放 aia_i 份物资。

公路是环形的,所以从 ll 号站沿顺时针走到 rr 号站,不一定只经过编号 l,l+1,…,rl,l+1,\dots,r 的站:如果 l>rl>r,还会先经过 nn 号站,再回到 11 号站。

凯尔希给了博士 qq 次查询。每次给出 l,rl,r,博士想知道:从 ll 号站顺时针走到 rr 号站(包含起点和终点),一共能收集多少份物资?

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

接下来 qq 行,每行两个整数 l,rl,r。

输出格式

输出 qq 行,每行一个整数,表示对应查询的答案。

样例

样例输入 #1

5 3
2 3 5 7 11
1 3
4 2
3 3
`

### 样例输出 #1

```text
10
23
5

样例解释

  • 1→31\to 3:经过 1,2,31,2,3 号站,物资为 2+3+5=102+3+5=10。
  • 4→24\to 2:经过 4,5,1,24,5,1,2 号站,物资为 7+11+2+3=237+11+2+3=23。
  • 3→33\to 3:只经过 33 号站,物资为 55。

数据范围

  • 对于 20%20\% 的数据,1≤n,q≤101\le n,q\le 10。
  • 对于 50%50\% 的数据,1≤n,q≤10001\le n,q\le 1000。
  • 对于 100%100\% 的数据,1≤n,q≤1051\le n,q\le 10^5,0≤ai≤1090\le a_i\le 10^9,1≤l,r≤n1\le l,r\le n。

提示

  • l≤rl\le r 时,答案就是普通区间和。
  • l>rl>r 时,可以拆成 [l,n][l,n] 和 [1,r][1,r] 两段,也可以用“总和减去没有走到的那一段”。
  • 答案可能超过 int,请使用 long long。