NAJHQ - Hazzat’s Query

Hazzat is a new guy in computer science. Now he read in 4th semester. Recently he completed the course data structure. After finished data structure course he can realize that those are not enough for his. Every day he fall in a new (data structure) problem and want solve it, but those problem he can’t solve using his know data structure. He want to establish new data structure. But he always failed to establish it. Now help Hazzat to establish a new data structure following problems.

Today Hazzat problem is:

Given a N size array (arr[N]) initialize all the element value to exactly c.

Pseudocode:

for(i=1; i<=N; i++)
    arr[i] = c;

Today Hazzat want to do 6 types of task.

i) add k to array index u to v

Pseudocode:

for(i=u; i<=v; i++)
    arr[i] = arr[i] + k;

ii) subtract k from array index u to v

Pseudocode:

for(i=u; i <= v; i++)
    arr[i] = arr[i] - k;

iii) add k to array index u

Pseudocode:

arr[u] = arr[u] + k;

iv) subtract k from array index u

Pseudocode:

arr[u] = arr[u] - k;

v) reset a array index u with k value

Pseudocode:

arr[u] = k;

vi) find the current value of array index u

Pseudocode:

print arr[u];

Here the array is 1 base index.

Input

Input start with an integer number T (≤ 10), which is number of test cases.

For each test case, first line contains N Q c where N is array size, Q number of queries and c is the initial value of array elements.

Next Q line give Hazzat's tasks

add u v k (add k to array index u to v)

minus u v k (subtract k from array index u to v)

addin u k (add k to array index u)

minusin u k (subtract k from array index u)

reset u k (reset array index u to k)

find u (print current value of array index u)

Constraints

  • T ≤ 10
  • 1 ≤ N, Q ≤ 10^5
  • 1 ≤ u ≤ v ≤ N
  • 0 ≤ c, k ≤ 10^9

Output

For each case, print “Case #X” where X is the case number.

After next line print value of array index u where Hazzat want to know. (only for find u task)

Output a blank line between two cases.

Sample

Input:
2
10 3 3
find 4
add 3 7 3
find 5
10 10 3
find 4
add 3 7 2
find 6
minus 3 4 1
find 4
addin 4 5
find 4
minusin 4 2
find 4
find 10

Output:
Case #1
3
6

Case #2
3
5
4
9
7
3

Note

Output number may be negative.

Data set is so huge, use faster I/O


Added by:Najmuzzaman
Date:2014-10-26
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2023-01-11 10:44:04
Normal lazytag but AC by colse stream synchronization (~ ̄▽ ̄)~

Last edit: 2023-01-11 10:44:38
2016-07-06 00:10:19
Lazy needed some constant opti (i.e. minimize # of operations with long long num). These kinds of problems would be a little nicer with +10% TL.
2014-12-25 12:11:26 Archit Jain
lazy straight forward
2014-12-22 19:22:59 RIVU DAS
Nice ques!
2014-11-29 08:45:01 Archangel
@Varun try solving using BIT
2014-11-21 12:47:38 vb30
Lazy Prop giving TLE ...


Last edit: 2014-11-22 06:36:59
2014-11-18 11:22:58 Archangel
@Md. Najmuzzaman thank you for this problem :)

You are welcome @Archangel.

Last edit: 2015-06-17 17:19:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.