रेंज सम क्वेरीज़

आपको n तत्वों वाला एक ऐरे दिया गया है और q रेंज सम क्वेरीज़ मिली हैं। आपका काम है कि आप प्रत्येक क्वेरी के लिए, दिए गए रेंज में आने वाले तत्वों का योग सेगमेंट ट्री डेटा स्ट्रक्चर की मदद से प्रभावी तरीके से निकालें।

इनपुट

इनपुट की पहली पंक्ति में दो पूर्णांक n और q (1 ≤ n, q ≤ 100 000) आते हैं, जो क्रमशः ऐरे में मौजूद तत्वों की संख्या और क्वेरीज़ की संख्या का प्रतिनिधित्व करते हैं।

दूसरी पंक्ति में n स्पेस से अलग किए हुए पूर्णांक () होते हैं, जो ऐरे के तत्व हैं।

अगली q पंक्तियों में से प्रत्येक में दो पूर्णांक और () दिए होते हैं, जो प्रत्येक क्वेरी के लिए रेंज दर्शाते हैं।

आउटपुट

प्रत्येक क्वेरी के लिए, दिए गए रेंज में आने वाले तत्वों का योग अलग-अलग पंक्तियों पर प्रिंट करें।

Examples

व्याख्या

दिए गए ऐरे [1, 2, 3, 4, 5] में हम निम्न रेंज सम क्वेरीज़ करते हैं:

1. क्वेरी [1, 3]: रेंज [1, 3] में आने वाले तत्वों का योग 1 + 2 + 3 = 6 है।

2. क्वेरी [2, 4]: रेंज [2, 4] में आने वाले तत्वों का योग 2 + 3 + 4 = 9 है।

3. क्वेरी [1, 5]: रेंज [1, 5] में आने वाले तत्वों का योग 1 + 2 + 3 + 4 + 5 = 15 है।