You have been given an array num[1..n] contains N integers and have to do some operations on it. Each operation can be indicated by four integers L, R, J, P, which means: change the value of a[P] to the maximum value among a[L], A[L+J], A[L+2J], ... , A[R]. Finally, calculate the sum of all elements of the array.
There are several testcases. Each testcase begin with a positive integer N(<=10,000) followed by N integers (<=109). Then there are a positive integer M(<=10,000) and next M lines are the operations you have to do. Each line has four integers L,R,J,P (1<=L,R,J,P<=N, L<=R, J|R-L).
For each testcase output an interger: the sum of final array.
5 1 2 3 4 5 3 1 3 2 4 1 1 2 5 1 5 1 3
10
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|