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

この工場では「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$ 行目には製造機の個数を表す整数 $N (1≦N≦100,000)$ が与えられる。
• $2$ 行目には $N$ 個の整数が空白を区切りとして与え