Big Queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
WARNING: This problem has large input / output files. Use of faster I/O methods is recommended.
You are given an array A consisting of N integers. You have to answer M queries on it. Each query belongs to one of the following three types:
 1 L R X : multiply each number in the range A_{L}, A_{L + 1}, ..., A_{R} by X.
 2 L R Y : Replace the elements A_{L}, A_{L + 1}, ..., A_{R} by Y, 2 * Y, ... (R  L + 1) * Y. In other words, the number A_{i} will be equal to (i  L + 1) * Y for each i from L to R.
 3 L R : Find the product of all numbers in the range A_{L}, A_{L + 1}, ..., A_{R}. As this number could be very large, you have to just find the number of trailing zeros of this number when represented in decimal notation.
Input
The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
The first line of each test case contains two spaceseparated integers N and M.
The second line contains N spaceseparated integers denoting A_{1}, A_{2}, ..., A_{N}
For next M lines, each line contains a query._{}
Each query is given by three or four (please refer to the statement) space separated integers._{}
The first integer denotes type of the query. For every type of query next two integers denote L and R. For each query of type 1, next integer denote X. For each query of type 2, next integer denote Y.
Output
For each test case, output a single line containing the sum of answers of all the queries of type 3.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, M, N + M ≤ 10^{5}
 1 ≤ L ≤ R ≤ N^{}
 1 ≤ X, Y, A_{i} ≤ 10^{9}
Subtasks
 Subtask #1 (18 points): 1 ≤ N, M, X, Y, A_{i} ≤ 10
 Subtask #2 (31 points): 1 ≤ N, M ≤ 1000
 Subtask #3 (51 points): original constraints
Example
Input: 1 5 5 2 4 3 5 5 3 2 4 3 2 5 2 2 4 1 1 3 3 10 3 1 5 Output: 5
Explanation
Array: [2, 4, 3, 5, 5]
 1st query: [4, 3, 5], 4 * 3 * 5 = 60 : answer 1.
 2nd query: [4, 3, 5, 5], 4 * 3 * 5 * 5 = 300 : answer 2.
 3rd query: [2, 4, 3, 5, 5] => [2, 1, 2, 3, 5].
 4th query: [2, 1, 2, 3, 5] => [2, 1, 20, 3, 5].
 5th query: [2, 1, 20, 3, 5], 2 * 1 * 20 * 3 * 5 = 600  answer 2.
Sum of all answers = 5.
Author:  antoniuk1 
Tester:  alex_2oo8 
Tags  antoniuk1 chasethered 
Date Added:  27012015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, 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.4, 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. 