Shivansh wants to give chapo to Arpit, but only if he is able to solve the following problem. As you are a dear friend of Arpit, you decide to help Arpit solve the problem. Given an array Arr of N numbers. You have to process Q queries on that array. Queries can be of following types :

(1)add x to index y

(2) given y compute sum of (Arr[i]*(y%i)) for i from 1 to N.

Input

First Line of input contains two space separated integers N and Q. Second Line contains N space separated integers Arr[1] Arr[2] ..... Arr[N] Next Q lines describe one query each and can be one of the two type:

-> 1 i X — Add X to index i.

-> 2 Y — compute sum of (Arr[i]*(Y%i)) for i from 1 to N.

Constraints

1 <= N,Q <= 100000 1 <= Arr[i], X, Y <= 100000 1 <= i <= N

Output

For each second type query output one integer per line — answer for this query.

Sample input

4 3

3 2 3 4

1 2 1

2 10

2 12

Sample output

11

0

I think it can be solved by segment tree, but I'm not able to figure out how to handle 'y'?

tourist Errichto mango_lassi Radewoosh

There are N food items lined up in a store. Given the nutritional value and weights of each of them, you need to buy a set of these food items such that they do not exceed the capacity of your carrying bag W and the overall sum of the nutritional value of the bought items is maximized. You can assume that you have enough money to buy all of these items. Also, you have 2 magic potions, using which you can increase the nutrition value of any two distinct food items by certain factors. That is, given two integers X and Y, you can choose any two distinct food items and multiply their nutritional value by a factor of X and Y respectively. The magic potion does not affect the weight of the items. Now, find the maximum sum of nutritional values that you can buy, given the weight constraint.

Input: 1 1 2 3 4 2 6

Output: 16

Hari is a Food Delivery guy and he has to pick food from restaurant R and deliver it to home H. Distance of H from R is D.When Hari reached at the restaurant R , he checked and found that his motorbike has P units of petrol left. Now, there are N fuel stations on the path from R to H and he may use these fuel stations to get petrol for his motorbike if any need arises. These N fuel stations are at distance D1, D2, D3,…, DN units from the restaurant R and these N fuel stations have P1, P2, P3,…, P N units of petrol. Hari’s motorbike tank is large enough to store any quantity of petrol. if Hari stops at any fuel station to get petrol, it takes K minutes. If at any point of time, there is no petrol in Hari’s motorbike, he will have to drag his motorbike on foot to nearest fuel station or his delivery location. If Hari drags his motorbike on foot, he takes 5 minutes to cover 1 unit distance and if he drives the motorbike, he takes 1 minute to cover 1 unit distance. Hari may drag his motorbike on foot even if there is petrol in motorbike to minimise the delivery time. Now, Hari has to deliver this order in minimum amount of time. Find the minimum possible time required to deliver the order.

Input: First line will contain 4 integers denoting N, D, P and K. Next line will contain integers denoting D1 , D2, D 3 ,…, DN . Next line will contain N integers denoting P1, P 2, P3,…, PN.

Testcase : 3 10 1 3

3 5 9

6 1 2

Ans — 24

Please someone explain the logic.