Fantastic Four

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Given an array A consisting of N integers, you have to perform Q operations on it. These operations can be of following two types.
 Type 1 is update operation in which you update the value of a particular element of the array
 Type 2 is range query from L to R in which you have to decompose the product of the elements in this range as sum of 4 square numbers.
Note  There can be more than one possible solution for a particular query, you can output any of them.
Input
The first line of the input contains T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space separated integers N, Q and P denoting the number of of elements in the array, the number of queries and the modulo value respectively.
The second line contains N spaceseparated integers  A_{1}, A_{2}, ..., A_{N} denoting the input array A.
The next Q lines contain 2 types of queries.
Type 1 operations are given as "1 X Y" (without the double quotes) where X denotes the indice to be updated and Y denotes the value it needs to be set to, ie. A[X] = Y
Type 2 operations are given as "2 L R" (without the double quotes) where L and R are the left and right end point for the given query.
Output
For each query of the type 2, output the respective 4 numbers in arbitrary order that when squared and summed under modulo P make that respective product modulo P. In case there is no such quadruple then output 1. All the 4 numbers should be between 0 to P  1(inclusive)
Constraints
Note that X, L and R for the queries will always be in the range from 1 to N where L ≤ R
Subtasks
Subtask #1 (10 points):
 1 ≤ T ≤ 3
 1 ≤ N, Q ≤ 10^{3}
 1 ≤ P ≤ 10^{3}
 1 ≤ A[i], Y ≤ 10^{3}
 Time limit = 1 second
Subtask #2 (30 points):
 1 ≤ T ≤ 3
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ P ≤ 10^{6}
 1 ≤ A[i], Y ≤ 10^{3}
 Time limit = 4 seconds
Subtask #3 (60 points):
 1 ≤ T ≤ 3
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ P ≤ 10^{12}
 1 ≤ A[i], Y ≤ 10^{6}
 Time limit = 5 seconds
Example
Input: 1 5 4 100 1 2 3 4 5 2 1 5 2 1 3 1 1 4 2 1 3 Output: 8 6 4 2 0 1 1 2 0 2 4 2
Explanation
1 x 2 x 3 x 4 x 5 mod 100 = 120 mod 100 = ( 8^{2} + 6^{2} + 4^{2} + 2^{2} ) mod 100
1 x 2 x 3 mod 100 = 6 mod 100 = ( 0^{2} + 1^{2} + 1^{2} + 2^{2 ) mod 100}
4 x 2 x 3 mod 100 = 24 mod 100 = ( 0^{2} + 2^{2} + 4^{2} + 2^{2} ) mod 100
Author:  sidhant007 
Tester:  iscsi 
Editorial  https://discuss.codechef.com/problems/FOURSQ 
Tags  datastructure, foursquare, jan17, lagrange, segmenttree, sidhant007 
Date Added:  31122016 
Time Limit:  1  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 