रेंज GCD क्वेरीज़
आपको
n तत्त्वों की एक ऐरे (array) और q क्वेरीज़ दी गई हैं। क्वेरीज़ दो प्रकार की होती हैं: किसी दिए गए खंड (range) का GCD निकालना और ऐरे के किसी विशेष स्थान पर तत्त्व को अपडेट करना। आपका कार्य इन क्वेरीज़ को कुशलता से प्रोसेस करना है।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n और q (1 ≤ n, q ≤ 100000) दिए जाते हैं, जो क्रमशः ऐरे के तत्त्वों की संख्या और क्वेरीज़ की संख्या को दर्शाते हैं।दूसरी पंक्ति में
n अंतराल से पृथक संख्याएँ (1 ≤ a_i ≤ 10^9) दी जाती हैं, जो ऐरे के प्रारंभिक तत्त्व हैं।अगली
q पंक्तियों में प्रत्येक क्वेरी का विवरण होता है:- For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices
[]for which the GCD needs to be calculated.
- For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .
आउटपुट
प्रत्येक रेंज GCD क्वेरी के लिए, उस खंड में मौजूद तत्त्वों का GCD एक अलग पंक्ति में प्रिंट करें।
उदाहरण
इनपुट | आउटपुट |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 4
2
2 |
Constraints
Time limit: 0.8 seconds
Memory limit: 512 MB
Output limit: 1 MB