Сәлем қазақ! Біз сенің сұраныстар туралы есепке бей-жай қарамайтыныңды білдік.

Бүтін сандардан тұратын \(n\) ұзындығындағы массив \(a_1, \ldots, a_n\) берілген. Сізге екі түрлі \(q\) сұранысты өңдеу керек:

• \(1\ l\ r\) – \(a_l + a_{l+1} + \ldots + a_r\) сомасын шығару;

• \(2\ l\ r\) – келесі псевдокодты орындау:

</center>

Ас болсын!

Енгізу

Бірінші жолда \(n\) және \(q\) (\(1\le n,q \le 2\cdot 10^5\)) – массивтің ұзындығы және сұраныстар саны беріледі.

Келесі жолда \(n\) сан: \(a_1, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) – массивтің элементтері.

Келесі \(q\) жолда үш саннан тұрады: \(t\ l\ r\) (\(t\in{1,2}, 1\le l \le r \le n\)) – сұраныстар сипаттамасы.

Шығару

Әрбір бірінші типтегі сұраныс үшін жеке жолда бір санды – көрсетілген бөліктің қосындысын шығарыңыз.

Мысалдар

Енгізу 1

5 9
40 30 2 1 10
1 1 4
2 3 4
1 2 5
2 2 4
1 1 5
2 1 3
1 1 4
2 1 5
1 1 5

Жауап 1

73
44
140
150
200

Енгізу 2

6 5
5 1 30 2 1 20
1 1 5
2 1 5
1 1 5
2 2 6
1 1 6

Жауап 2

39
100
130