C - 工場見学ツアー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は、大きな工場の見学ツアーのガイドとして働いています。

この工場には N 個の製造エリアがあり、それぞれのエリアには 1 から N までの番号が付けられています。各エリア i の見学にはちょうど T_i 分かかります。

今日は M 組の見学グループが工場を訪れます。各グループ j は、時刻 S_j 分に工場に到着し、到着後すぐにエリア番号 L_j から R_j までの範囲に含まれるすべてのエリアを見学します。グループは番号の小さいエリアから順に一つずつ見学し、一つのエリアの見学が終わると即座に次のエリアの見学を開始します（エリア間の移動時間はかかりません）。

各エリアは十分に広いため、複数のグループが同時に同じエリアを見学していても、互いに影響を受けることはありません。

高橋君は、各グループがすべての見学を終える時刻を事前に計算し、グループに伝えたいと考えています。

各グループについて、すべての指定されたエリアの見学が完了する時刻（分）を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 0 \leq S_j \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 入力はすべて整数

入力

N M
T_1 T_2 \ldots T_N
S_1 L_1 R_1
S_2 L_2 R_2
\vdots
S_M L_M R_M
  • 1 行目には、エリアの個数 N とグループの数 M が、スペース区切りで与えられる。
  • 2 行目には、各エリアの見学時間 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、各グループの情報が与えられる。
  • 2 + j 行目には、 j 番目のグループの到着時刻 S_j 、見学するエリア番号の範囲の始点 L_j 、終点 R_j が、スペース区切りで与えられる。

出力

M 行出力せよ。

j 行目には、 j 番目のグループがすべての見学を終える時刻を分単位で出力せよ。

入力例 1

5 3
10 20 30 40 50
0 1 3
5 2 4
100 5 5

出力例 1

60
95
150

入力例 2

4 5
15 25 10 30
0 1 4
10 1 1
20 2 3
0 3 4
50 1 2

出力例 2

80
25
55
40
90

入力例 3

10 6
100 200 300 150 250 50 400 100 350 200
0 1 10
1000 3 7
500 1 5
0 6 10
200 4 6
999999999 1 1

出力例 3

2100
2150
1500
1100
650
1000000099

Score : 333 pts

Problem Statement

Takahashi works as a guide for a tour of a large factory.

The factory has N manufacturing areas, each numbered from 1 to N. Visiting each area i takes exactly T_i minutes.

Today, M tour groups will visit the factory. Each group j arrives at the factory at time S_j minutes, and immediately after arrival, they visit all areas with numbers from L_j to R_j. The group visits the areas one by one in order of increasing area number, and as soon as they finish visiting one area, they immediately begin visiting the next area (there is no travel time between areas).

Each area is spacious enough that even if multiple groups are visiting the same area at the same time, they do not affect each other.

Takahashi wants to calculate in advance the time at which each group finishes all their visits, and inform the groups.

For each group, determine the time (in minutes) at which they complete visiting all of their designated areas.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 0 \leq S_j \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • All input values are integers.

Input

N M
T_1 T_2 \ldots T_N
S_1 L_1 R_1
S_2 L_2 R_2
\vdots
S_M L_M R_M
  • The first line contains the number of areas N and the number of groups M, separated by a space.
  • The second line contains the visiting times T_1, T_2, \ldots, T_N for each area, separated by spaces.
  • The following M lines contain the information for each group.
  • The (2 + j)-th line contains the arrival time S_j of the j-th group, and the start L_j and end R_j of the range of area numbers to visit, separated by spaces.

Output

Print M lines.

The j-th line should contain the time in minutes at which the j-th group finishes all their visits.

Sample Input 1

5 3
10 20 30 40 50
0 1 3
5 2 4
100 5 5

Sample Output 1

60
95
150

Sample Input 2

4 5
15 25 10 30
0 1 4
10 1 1
20 2 3
0 3 4
50 1 2

Sample Output 2

80
25
55
40
90

Sample Input 3

10 6
100 200 300 150 250 50 400 100 350 200
0 1 10
1000 3 7
500 1 5
0 6 10
200 4 6
999999999 1 1

Sample Output 3

2100
2150
1500
1100
650
1000000099