POTIONS - Potions Class

no tags 

Its time for the Potions class. Harry absolutely HATES potions because he has to face mockery by the potions teacher Snape everytime he has a potions class. Snape never leaves any chance of insulting him in front of everyone.

Snape is not in a good mood today, which is not good for Harry. Snape challenges Harry to answer his question. If Harry fails to answer, he will have to spend the whole week in detention!.

He gives Harry n numbers ( a1, a2, a3,...., an ) and q queries. Each query will consist of four integers,w, x, y, z . The result of a query is given by the following equation:

Equation

Help Harry or else he'll miss his Quidditch match against Slytherin because of his detention..!!

Input

The first line of the input contains T, the number of test cases. T test cases follow.

The first line of each test case contains n and q.

The second line of each test case contains n integers (a1, a2, a3,..,an)

Each of the next q lines contain w, x, y, z.

Output

For each test case output the result as given by the equation.

The answer may be very large, so output it modulo 10^9+7

Constraints:

1<= T <=10

1<= n, q <=10^5

1<= x+i <=n ( for all y<=i<=z )

0<= ai <=10^9 ( for all 1<=i<=n)

1<= w <=10^6

0<=y<=z

Example

Input:
1
5 2
2 1 4 7 2
1 1 0 2
1 5 0 0
Output:
16
2

hide comments
code_aim: 2017-10-31 17:52:20

No need of segment tree!! Easy one

viratian_070: 2017-07-04 16:11:58

segment tree without any optimization....nice problem

Abhilash: 2015-01-12 03:11:55

careful while doing modulo op
costed me so many WA

master_blaster: 2014-07-16 22:46:02

@Abhinav92003 can you please check my code and tell the error. all test cases are working fine
11961373

you_know_why: 2014-06-05 15:11:26

@Abhinav92003 could you please check this submission and tell me where i am going wrong....
11707759

P_Quantum: 2014-05-25 06:40:57

Finally AC..!!

The_ROCK: 2014-05-23 20:26:53

correct the constraints. It is said that 0 < y <= z but in the example itself y and z both are 0.
--ans(Francky)--> Done

Last edit: 2014-05-24 09:05:13
SanchitK: 2014-04-26 23:36:22

@admin-please can you provide a test case where i am wrong.

Francky: 2014-04-13 13:39:25

@psetter : please use "upload files" possibility for the image, it will prevent broken link in the future. If you need help, just ask ;-)

રચિત (Rachit): 2014-04-13 13:39:25

@Abhinav92003, Can you please fix "Equation" image link?


Added by:Abhinav92003
Date:2014-04-06
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All