Haymouth wants to be a rocket scientist. Or a programmer. Or a professional banana-eating champion.
What's that you say? Cows can't type? Of course they can't! But they have dreams and ambitions and are brave enough to chase them. Are you?
Haymouth is working on a high school science project. It's a rocket propulsion device—a jetpack for cows that works by shooting bananas. To be able to build it, he must first answer a few important questions about Mootonian bananajectile dynamics.
Q: How does a cow with a jetpack moove?
A: Well, first let us consider a spherical cow.
The spherical cow lives in a 1-dimensional discrete-time world. The jetpack can thus shoot bananas either to the left or to the right.
- Since time occurs in 1-second intervals, if the cow is moving at v meters per second in one time-step, the cow's position advances by v meters in the next time-step.
- Since the mass of a banana is negligible compared to that of the spherical cow, shooting a banana always accelerates the cow by a constant amount in the opposite direction, regardless of how many bananas have been shot already.
- Since we are already making so many simplifying assumptions, shooting 1 banana produces an impulse of 1 Mooton second in the opposite direction on the 1 kg spherical cow, also applied only in the next time-step.
Let the velocity and position of the spherical cow at time-step t be v(t) meters per second and x(t) meters respectively.
From (1), we have:
x(t + 1) = x(t) + v(t)
Let b(t) be the net banana-shootage in time-step t, positive if more bananas have been shot to the left than to the right and negative otherwise.
Then, from (2) and (3), we have:
v(t + 1) = v(t) + b(t)
And so, Haymouth solved the tough physics problem and went on to win the professional banana-eating championship. Meanwhile, you have been sitting in front of a computer and reading this useless drivel. Why not be a little more productive and help Haymouth plan the motion of the jetpack-enabled cow on the mission to land a cow on the moon? You can be what Haymouth cannot be: a programmer!
We are concerned with T time-steps, numbered from 0 to T - 1. At time-step 0, the spherical cow is at x(0) = 0 meters with a velocity of v(0) = 0 meters per second. The initial values for b(t) are given at all time-steps 0 ≤ t < T - 1, but Haymouth will be changing and tweaking this for the mission. Your job is to help figure out the spherical cow's position and velocity at any time-step Haymouth asks for.
Input and Output
The first line contains two integers T and Q. T is the number of time-steps and Q is the number of queries.
The second line contains T - 1 integers. The tth integer (0 ≤ t < T - 1) is the initial b(t).
The next Q lines contain one query each. Each query begins with an integer A.
If A is 0, three integers ta, tb (0 ≤ ta ≤ tb< T - 1) and B follow. Haymouth has added B to b(t) for all time-steps t in the range ta ≤ t ≤ tb.
If A is 1, one integer t (0 ≤ t < T) follows. Print the two integers x(t) and v(t) on one line seperated by a space.
For all subtasks, it is guaranteed that -106 ≤ b(t) ≤ 106 for all time-steps t, before and after every update.
Subtask 1 (13%): 1 ≤ T ≤ 5000, 1 ≤ Q ≤ 5000.
Subtask 2 (20%): 1 ≤ T ≤ 500000, 1 ≤ Q ≤ 500000. In each query where A is 1, t is greater than all tb given in the queries before.
Subtask 3 (67%): 1 ≤ T ≤ 500000, 1 ≤ Q ≤ 500000.
9 4 1
0 0 1 -6
After the updates, b(0) = 3, b(1) = -2 and b(2) = 1. For t = [1, 2, 3], v(t) is [3, 1, 2] and x(t) is thus [0, 3, 4].