Queries

Edward Elric has learnt new Alchemy technique, if he uses this technique on 1x1 block with power f[i] then height on this block increases by f[i],also his power in i_{th} move depends on powers of his previous three moves i.e.
f[i] = x*f[i1] + y*f[i2] + z*f[i3] here x,y,z are some constant and if he uses technique for first, second, third time then his power will be f1,f2,f3.
To test Edward's power Colonel Mustang gives him arena of dimension 1xN and gives him Q queries in each query Mustang gives him two integers L and R i.e. he has to perform his new technique on each block from L to R, but Alex Louis Armstrong orders Edwards to perform in reverse on for each query i.e. first perform on R then R1,R2,....L . In each query he cant skip any block, and after each operation he takes 2 min break, so that in next query he has to start again.
His brother Alphonse Elric is nervous about how his brother will perform and he cant wait for results so he is asking for your help
Input
 The first line of the input contains an integer T denoting the number of test cases . The description of T testcases follow.
 First line of each test case contains three space seperated integers x,y,z ( constants for f[i] = x*f[i1] + y*f[i2] + z*f[i3] )
 Second line of each test case contains three space seperated integers f1,f2,f3 ( Edward’s initial power )
 Next line contiains an Integer N denoting Dimension of arena .
 Next line contiains an Integer Q denoting number of Queries .
 Next Q line contains two space seperated integers L,R denoting range for i_{th} query
Output
For each test case print Arena i.e size of each block modulo (1000000007)
Constraints
 1 ≤ T ≤ 20
 100000 ≤ x , y , z ≤ 100000
 100000 ≤ f1, f2 , f3 ≤ 100000
 1 ≤ N ≤ 10000
 1 ≤ Q ≤ 100000
 1 ≤ L ≤ R ≤ N
Example
Input:
1
1 2 3
4 5 6
5
2
1 3
1 4
Output:
34 11 9 4 0
Explanation
initial arena : 0 0 0 0 0
arena after first query : 6 5 4 0 0
arena after second query : 34 11 9 4 0
According to given equation f[1]=4 f[2]=5 f[3]=6 ; f[4]=1*6 + 2*5 + 3*4=28
So in first query of 1 to 3 a[3]+=f[1], a[2]+=f[2], a[1]+=f[1]
In second query 1 to 4 a[4]+=f[1], a[3]+=f[2], a[2]+=f[3], a[1]+=f[4]
Hence the answer.
Author:  akashpatil219 
Tags  akashpatil219 
Date Added:  17032019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions