Product on the segment by modulo

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Given an array A of N integers and an integer P ( not necessarily prime ). You are required to answer Q queries, ith query is described by two numbers L_{i}, R_{i}, the answer to the query is the product of all numbers in array A from index L_{i} to index R_{i} modulo P. You have to answer the queries in online mode, that is you can't know a query before you answer all queries that are before it.
Input
the first line contains one integer T , the number of testcases.
the first line of each testcase contains N, P, Q .
the third line contains N spaceseparated integers, the of elements array A .
the fourth line contains array B which consists of floor(Q/64) + 2 integers . Let's number the queries starting from 0. If i is divisible by 64 then:
L_{i} = (B_{i / 64} + x) mod N, R_{i} = (B_{i / 64 + 1} + x) mod n .
Otherwise: L_{i} = (L_{i1} + x) mod N, R_{i} = (R_{i1} + x) mod N . If L_{i} > R_{i} you should swap them. here x is equal to 0 if it's the first query, otherwise it's equal to the answer of the previous query plus 1 modulo P.
Output
After each testcase you have to print one number  the value of x after the the last query modulo P
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 10^{6}
 1 ≤ Q ≤ 2 * 10^{7}
 2 ≤ P ≤ 10^{9}
 0 ≤ A _{ i } ≤ 10^{9}
 0 ≤ B_{ i } ≤ n  1
 The sum of N over all testcases does not exceed 10^{6} and sum of Q over all testcases does not exceed 2 * 10^{7}
Subtasks
 Subtask 1 (20 points) : P is prime and all numbers of A in range [1; P  1]
 Subtask 1 (20 points) : P = x^{k} where x is prime and k is integer and all numbers of A in range [1; P  1]
 Subtask 3 (60 points) : Original constraints
Example
Input: 2 6 113 3 1 2 3 4 5 6 1 4 6 113 70 1 2 3 4 5 6 1 4 3 Output: 8 21
Author:  altruist_ 
Editorial  https://discuss.codechef.com/problems/SEGPROD 
Tags  altruist_, mediumhard, nov17 
Date Added:  22082017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions