Two functions F & G are defined as follows :
Here , ai ( 1<= i <= k) , bi ( 1<= i <= k+1) , c , d ,e , f,g and k are the constants which are given.
Also you are given (k+1) initial values of both the functions F and G.
i.e. you are given with Fi and Gi where 0<= i <=k.
Now you have to answer Q queries, in each query you are given X1 , X2 , Y1 ,Y2 , M and P. ( P is always prime number).
You have to print (HM mod P) for each query.
Input :
1st line : k , Q (number of queries)
2nd line : k integers a1 , a2 , … ak
3rd line : (k + 1) integers b1 , b2 , … bk+1
4rth line : c, d, e, f, g
5th line : (k+1) integers F0 , F1 , ….. , Fk
6th line : (k+1) integers G0 , G1 , ….. , Gk
Q lines follows : Each line : X1 , X2 , Y1 , Y2 , M, P
Output :
For each query print (HM mod P).
Constraints:
1 <= k <= 3
1 <= Q <= 100
1 <= X1 <= X2 <= 10^18
1 <= Y1 <= Y2 <= 10^18
k < M <= 10^18
3 <= P <= 10^9 (Prime Number)
1 <= a[i], b[i], c, d, e, f, g <= 10^9
