एल्गोरिदम और डेटा संरचनाएँ

Alternating Sum

आपके पास n पूर्णांकों की एक array और q क्वेरीज़ हैं। इन क्वेरीज़ के दो प्रकार हैं: किसी दिए गए इंडेक्स p पर array को अपडेट करना, तथा उपarray [l; r] का alternating sum निकालना।

उपarray [l; r] का alternating sum इस तरह परिभाषित है कि इसमें सब-एरे के सम में समांक (even) इंडेक्स के तत्वों को जोड़कर, विषम (odd) इंडेक्स के तत्वों को घटाया जाता है। दूसरे शब्दों में, यदि उपarray [l; r] में तत्व [al, a{l+1}, ..., a_r] हैं, तो इसका alternating sum

al - a{l+1} + a{l+2} - a{l+3} + ... + (-1)^{r-l} · a_r

इनपुट

पहली पंक्ति में दो पूर्णांक n और q दिए जाते हैं, जो क्रमशः array का आकार और क्वेरीज़ की संख्या दर्शाते हैं (1 ≤ n, q ≤ 10^5)।

आउटपुट

प्रकार 2 की प्रत्येक क्वेरी के लिए, प्राप्त alternating sum को एक पृथक पंक्ति में प्रदर्शित करें।

उदाहरण

Input

Output

8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8

4
-9

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue