Evakum

Jaeseong is the strongest guy in the real world! He is so strong that every student at school gets weak in the knees when they see him, and the story of how he got that strong is as follows.

Jaeseong originally had a natural talent for magic, giving him the mana to use the attack techniques Air Pressure, which instantly increases air pressure, and Bakum Press, as well as a time machine technique that lets him return to an earlier time. But Jaehyeok beat him up without knowing this, so at some point Jaeseong got so angry that he awakened.

After awakening, in order to settle the grudge that had piled up until then, Jaeseong hit Jaehyeok on day i with a shock of ai. Sometimes he would get fickle, return to days j through m, and hit each of them with an added shock of l, but since using the time machine technique is very difficult, the shock can become negative and he himself can end up getting hit in return.

As Jaehyeok kept getting beaten, he became curious about how much he had been hit from day n through day m.

For the pitiful Jaehyeok, let us tell him how much Jaeseong hit from day n through day m.

You are given the number of days N on which Jaeseong hit Jaehyeok, the number of days Q1 on which Jaeseong got fickle, and the number of intervals Q2 about which Jaehyeok is curious how much he was hit. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000)

The next line gives the shock ai that Jaehyeok received on day i. (1 ≤ ai ≤ 1,500,000)

The next Q1+Q2 lines give queries of the following kinds.

1. 1 n m : print how much Jaehyeok was hit from day n through day m. Q2 queries of this kind 1 are given. (1 ≤ n, m ≤ N)
2. 2 s e l : Jaeseong can return to days s through e and hit them with an added shock of l. Q1 queries of this kind 2 are given. (-1,000 ≤ l ≤ 1,000, 1 ≤ s, e ≤ N)

Print the answers to the kind 1 queries over Q2 lines in order.