Fragmentation

Not long ago, a rare type of meteorite called mesosiderite fell on the grounds of Tomorrow Programming School and was collected at once. The school was given the job of organizing the cutting of the meteorite into smaller pieces, which will be exported to laboratories around the world. Swiss Precision Cutting Agency (SPCA) was hired to do the cutting.

SPCA operates several cutting machines. Each machine cuts the meteorite, or a piece of it, into a fixed number of smaller pieces of exactly equal weight. That number is the characteristic of the machine and cannot change. Each machine can process any number of pieces in one day. A piece produced by a machine cut cannot be cut again by the same machine on the same day, because of possible cross-contamination and the resulting loss of precision.

Each day exactly one cutting machine is available. The order of machines over successive days is fixed. SPCA made a cutting schedule, a list of upcoming days with the characteristic of the machine available on each day. The cutting process takes one or more days until a satisfactory number of pieces is obtained.

The following rules apply.

• All laboratories must receive the same total weight of pieces.
• No piece can be shared among laboratories.
• Every piece must go to some laboratory. No leftovers.
• At the end of each day, all pieces must have the same weight.
• The whole process must finish within consecutive days, with no day without cutting in between.

The school has the schedule and chooses when to cut. A cutting period is any consecutive sequence of days in the schedule. A period is favourable if a cutting process starting on its first day produces pieces that meet the laboratories' demands at the end of its last day.

Write a program that decides, for a given cutting period, whether it is favourable.

The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of days in the cutting schedule. The next line contains the schedule as integers $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 10^6$), where $a_i$ is the characteristic of the machine available on day $i$. The next line contains an integer $Q$ ($1 \le Q \le 10^5$), the number of queries. Each of the next $Q$ lines contains three integers $s_i$, $t_i$, and $k$ ($1 \le s_i \le t_i \le N$, $1 \le k \le 10^6$), where $s_i$ is the first day of the cutting period, $t_i$ is the last day, and $k$ is the number of laboratories involved.

For each query, print Yes on its own line if the cutting period is favourable, otherwise print No.