[Hidden ☆ before use]
#### 1146. Stock

#### Description

There are n stocks in the market, and after researching, the variance of the i-th stock’s price is a_i per dollar you devoted.

Master Dong is reluctant to taking risk, so he wants to put the money on hand into n shares in a certain proportion, so that the total amount of total investment in all stocks fluctuates to a minimum.

We use the variance as a measure of volatility. We assume the money Master Dong invested into stocks is a real number. And we just define the unit minimum variance (UMV) as the variance of each dollar Mater Dong invested, under the optimal strategy.

There are m days now. For each day we have a cmd.

cmd = 1 indicates that the market was uniformly regulated on that day, and the stock price was adjusted by x % for the stocks from l to r.

cmd = 2 means if only stocks l to r are considered, what is UMA.

It’s guaranteed the answer is a rational number in the form of p/q. You only need to output p × q-1 mod 10^9+7 in order to avoid accuracy error and high precision.

n ≤ 2 × 10^5， m ≤ 2 × 10^5, 1 ≤ di < 10^9, all inputs are integers.

#### Input

The first line contains two intergers : n, m.

The next line contains n integers a1 ... an

The next m lines: first input cmd, if cmd = 1, input l, r, x, or l ,r#### Output

For every cmd = 2, output an integer in a line.
#### Samples

#### Source

第九届山东省赛

Master Dong is reluctant to taking risk, so he wants to put the money on hand into n shares in a certain proportion, so that the total amount of total investment in all stocks fluctuates to a minimum.

We use the variance as a measure of volatility. We assume the money Master Dong invested into stocks is a real number. And we just define the unit minimum variance (UMV) as the variance of each dollar Mater Dong invested, under the optimal strategy.

There are m days now. For each day we have a cmd.

cmd = 1 indicates that the market was uniformly regulated on that day, and the stock price was adjusted by x % for the stocks from l to r.

cmd = 2 means if only stocks l to r are considered, what is UMA.

It’s guaranteed the answer is a rational number in the form of p/q. You only need to output p × q-1 mod 10^9+7 in order to avoid accuracy error and high precision.

n ≤ 2 × 10^5， m ≤ 2 × 10^5, 1 ≤ di < 10^9, all inputs are integers.

The next line contains n integers a1 ... an

The next m lines: first input cmd, if cmd = 1, input l, r, x, or l ,r

Time Limit: | 1000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |