Fragmentation
本题没有可用的提交语言。
Description
Not so long ago, a rare type of meteorite, called mesosiderite, fell on the premises of Tomorrow Programming School and was immediately collected. The school was given the honour 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 job. SPCA operates various cutting machines. Each machine can cut the meteorite or a piece of the meteorite into a number of smaller pieces, each of which weighs exactly the same. The number of resulting smaller pieces is the characteristic of that particular machine and cannot be changed.
SPCA is quite sure that each of their machines can process any number of meteorite pieces in one day. A piece of meteorite produced by a machine cut cannot be cut again by the same machine in the same day, because of possible cross-contamination and ensuing loss of precision.
Each day, there is exactly one cutting machine available. The order of available machines in successive days is fixed. SPCA created a list of days in the near future and assigned to each day the characteristic of the machine available that day. SPCA calls this list a cutting schedule. The cutting process will take one or more days to complete, before a satisfactory number of meteorite pieces is obtained.
There are a few additional rules governing the cutting and exporting process.
- All laboratories demand that they all receive the same total weight of meteorite pieces.
- No meteorite piece can be shared among laboratories.
- Each piece of the meteorite must go to some laboratory, there should be no leftovers.
- At the end of each day in the cutting process, the weights of all meteorite pieces must be the same, to simplify cutting management.
- The whole cutting process has to be completed in a period of successive days, which should not be interrupted by any day without cutting.
The school has been given the cutting schedule and it is up to them to choose when to perform the actual cutting. A cutting period can be any sequence of consecutive days in the cutting schedule. Clearly, some cutting periods are favourable and some are not. A cutting period is favourable if a cutting process that starts in the first day of the cutting period would produce meteorite pieces, which satisfy the laboratories' demands at the end of the last day of the cutting period.
The school needs a program that can decide for a cutting period whether it is favourable or not.
The first input line contains integer $N$ ($1 \leq N \leq 10^5$), the number of days in the cutting schedule. The next line contains the cutting schedule in the form of integer sequence $a_1, a_2, \ldots , a_N$ ($1 \leq a_i \leq 10^6$). The value ai represents the characteristic of the machine available on $i$-th day in the cutting schedule. The next line contains integer $Q$, ($1 \leq Q \leq 10^5$), the number of following queries. Each of the next $Q$ lines represents one query and it contains three integers $s_i, t_i, k$ ($1 \leq s_i \leq t_i \leq N, 1 \leq k \leq 10^6$), the first day of the cutting period, the last day of the cutting period, and the number of laboratories involved.
For each input query output, on a separate line, Yes if the cutting period specified by the query is favourable, otherwise output No.
Input
The first input line contains integer $N$ ($1 \leq N \leq 10^5$), the number of days in the cutting schedule. The next line contains the cutting schedule in the form of integer sequence $a_1, a_2, \ldots , a_N$ ($1 \leq a_i \leq 10^6$). The value ai represents the characteristic of the machine available on $i$-th day in the cutting schedule. The next line contains integer $Q$, ($1 \leq Q \leq 10^5$), the number of following queries. Each of the next $Q$ lines represents one query and it contains three integers $s_i, t_i, k$ ($1 \leq s_i \leq t_i \leq N, 1 \leq k \leq 10^6$), the first day of the cutting period, the last day of the cutting period, and the number of laboratories involved.
Output
For each input query output, on a separate line, Yes if the cutting period specified by the query is favourable, otherwise output No.
8
2 3 6 12 4 8 16 4
8
2 4 72
1 8 7
1 4 16
1 4 32
4 4 6
5 5 4
2 5 864
2 5 1296
Yes
No
Yes
No
Yes
Yes
Yes
No