私はとあるクッキー工場に勤めている。

この工場では「ARCたんクッキー」というかわいいクッキーを作っている。

この工場には $N$ 個のARCたんクッキー製造機があり、製造機には $1$ から $N$ まで番号がついている。製造機ごとに異なるフレーバーが設定されているため、異なる製造機から作られたクッキー同士は区別される。また製造機ごとに一度に生成するクッキーの量が設定されている。製造機は指定された製造数のクッキーを一度に全て生成する。

この度、私が勤めている工場では、$M$ 日間、工場見学ツアーを実施することになった。それぞれの日には次のいずれかの作業が実行される。

• 見学ツアーを実施する。ツアーではそれぞれの日ごとに定められた、ある連続した番号の製造機をちょうど $1$ 回ずつ稼働させ、それらの製造機が生成したクッキー全てをお土産としてツアー参加者に配る予定である。
• メンテナンスを実施し、それぞれの日ごとに定められた、ある連続した番号の製造機の製造数を一定数増減させる。

工場はとても広く迷子になりやすいので、それぞれのツアー実施日内ではツアー客の定員を固定することになっている。

ここの工場長は割り切れないことを好まず、どの製造機から作られたクッキーもその日参加した全てのツアー客に同数ずつ配らなければ気が済まない。また、ARCたんクッキーの一部を配らない、砕くなどかわいそうなことはしてはならない。つまり、作ったクッキーは全てツアー客に平等に配らなければならない。一方でこの工場の宣伝のため、このような条件を満たしつつできるだけ多くのツアー客を受け入れたいと考えている。

立案者である私は、それぞれのツアー実施日において、$1$ 回あたりのツアーに参加できるツアー客の最大値を求めることになった。しかしながら私は新しいフレーバー開発に忙しい。そこであなたに是非ともこの問題を解いてもらいたい。

N
a_1 a_2 … a_N
M
t_1 l_1 r_1
t_2 l_2 r_2
:
t_M l_M r_M

1. $1$ 行目には製造機の個数を表す整数 $N (1≦N≦100,000)$ が与えられる。
2. $2$ 行目には $N$ 個の整数が空白を区切りとして与えられる。
3. $3$ 行目にはツアー及びメンテナンスをする日数を表す整数 $M (1≦M≦100,000)$ が与えられる。
4. $4$ 行目から $M$ 回、ツアー及びメンテナンスの工程を表す $3$ つの整数が空白を区切りとして与えられる。

• 下記の条件を満たすテストケースのみで構成された、$30$ 点分のセットがある。
• 上記のセットを含む全てのテストケースに正解することで、残りの $70$ 点を得られる。

ツアーを行う回数を $T$ とする。このとき出力は $T$ 行だけ出力せよ。$i$ 行目には、初日から数えて $i$ 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。

なお、出力の最後には改行を入れること。

4
6 3 38 49
7
0 1 3
-2 3 3
0 1 3
9 2 2
0 1 2
6 3 3
0 3 4

1
3
6
7

• 初期状態における製造機ごとのクッキー製造数は、$1$ 番の製造機から順に $6,3,38,49$ となっている。
• $1$ 日目はツアーを実施する。
• $2$ 日目はメンテナンスを実施する。
• $3$ 日目はツアーを実施する。
• $4$ 日目はメンテナンスを実施する。
• $5$ 日目はツアーを実施する。
• $6$ 日目はメンテナンスを実施する。
• $7$ 日目はツアーを実施する。

3
1 3 17
6
16 1 1
8 2 2
0 1 2
0 2 2
6 2 2
0 1 3

1
11
17