Copy and Paste

All submissions for this problem are available.
In an exam in IIT Kanpur, the question paper consists of infinite questions. Ram, being a studious guy, aims to attempt infinite questions. In the ith question, Ram answers are worth R[i] marks. However, he does not know the answer to all, and instead of thinking about the questions, repeats his answer after every S questions, i.e., the answer given by Ram for the Kth question is same as the answer for (K  S)th question and so the marks obtained for question K and question KS are also the same.
Shyam, on the other hand, hardly studies and has made up his mind to attempt atmost N questions. He plans to copy the answer to these questions from Ram. If Shyam wishes to write answers to all between question X and question Y, he wants to know the corresponding answers by Ram for all questions between M and M+YX, where M is a parameter decided by Shyam. For each answer copied, he would earn same marks as Ram earned for the corresponding answer. If at the end of the exam, Shyam has not attempted any of the N questions, he receives zero marks for that question.
Now while correcting Shyam's answer sheet, the teacher wishes to check answers for questions between A and B. She asks Ram as what would be the maximum marks he would obtain if she checks some continuous questions in between A and B.
Help Ram in answering these questions and passing the exam.
Input Format
First Line contains 3 space separated integers S N T.
Next Line Contains S space separated integers, representing the marks worth of first S answers of Ram, i.e., ith integer represents R[i].
T lines follows, containing T operations, one per line.
Each operation is either of the two forms
U X Y M  To copy Ram's answer from M to M+YX.
Q A B  To report the maximum marks that can be obtained on correcting continuous questions between A and B.
Output Format
For each of the query operation (ones starting with Q), output a single integer in a line, the result of that query.
Constraints
 1 ≤ S ≤ 1000
 1 ≤ N ≤ 10^5
 1 ≤ M ≤ 10^9
 1 ≤ T ≤ 10^5
 abs(R[i]) ≤ 1000
 1 ≤ A,B,X,Y ≤ N
Sample Input
5 10 4
10 6 7 11 12
U 1 5 3
Q 2 4
U 2 9 3
Q 3 9
Sample Output
33
43
Explanation
Initially scores of N questions:: 0 0 0 0 0 0 0 0 0 0
Marks After Update :: 7 11 12 10 6 0 0 0 0 0
Result of Query(Maximum Sum Subarray from 2 to 4):: 33 (11+12+10)
Marks After Update:: 7 7 11 12 10 6 7 11 12 0
Result of Query(Maximum Sum Subarray from 3 to 9):: 43 (11+12+10+(6)+(7)+11+12)
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions