MAS - Moumita and Assignments


Moumita doesn’t like assignments. Whenever she is given any assignment, she feels helpless and wants to destroy the world. Unfortunately, she has a pending assignment. As she doesn’t know how to do it, she is preparing to destroy everything. Can you help her to complete it and save the world???

The assignment is, you are given an array A of n elements and a function F(A) which is defined as:

where mod = 2,760,727,302,517

You have to perform Q queries of the following types:

  • 1 x v (which means set A[x] = v.)
  • 2 x v (which means add v to A[x] i.e., A[x] = A[x]+v.)
  • 3 (which means compute F(A) and output it in a single line.)

Input

Input starts with an integer T denoting the number of test cases.

The first line of each case contains two integers n and Q. The next line contains n space separated integers, where ith integer denotes the value of A[i].

Each of next Q lines contains a query of the above specified types.

Constraints

1 ≤ T ≤ 6

1 ≤ x ≤ n ≤ 100000

1 ≤ Q ≤ 100000

0 ≤ A[i], v ≤ 1000000000

Output

For each case, print the case number first. Then for each query of type 3, print the value of F(A) in each line. See sample I/O for more clarification.

Example

Input:
1
3 5
1 2 3
3
1 1 5
3
2 3 6
3

Output:
Case 1:
6
14
74

hide comments
dhirajkhali: 2023-01-18 14:02:02

can anyone give me @Bhuvnesh Jain solution

Last edit: 2023-01-18 14:02:13
Supto: 2017-02-16 20:56:44

@Vipul Srivastava, yeah.. you are right! output does not have blank lines after each line and there are no blank lines in the input.

Last edit: 2017-02-16 20:59:42
Supto: 2017-02-16 20:55:06

@Anand, the output have no blank line after each line. The description has been updated!

Sushovan Sen: 2017-02-02 08:21:05

@Author can you please check cases where my code fails?

Last edit: 2017-02-03 12:05:17
Anand: 2017-01-23 08:25:27

Can anyone please help me here :
http://discuss.spoj.com/t/wrong-answer-in-mas-http-www-spoj-com-problems-mas/20736?u=abundavia

Vipul Srivastava: 2017-01-22 19:59:52

output does not have blank lines after each line and also I don't think there are any blank lines in the input.

Vipul Srivastava: 2017-01-22 17:57:01

Python 3 can pass the time limit.

Last edit: 2017-01-22 19:57:58
Anand: 2017-01-22 14:42:01

@supto
Can you please specify the sample input output precisely with exact "\n" ?
There seems to unnecessary "\n" in the given sample input.
Does output have one blank line after each line ?

Bhuvnesh Jain: 2017-01-21 06:42:54

Too strict time limit for python3.
EDIT: Done in python. Your algorithm should be fast enough.

Last edit: 2017-01-23 12:15:33

Added by:Supto
Date:2017-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:https://algo.codemarshal.org/contests/new-year-2017