للقيام بذلك ، ذهبت ناتاليا إلى Grigory وأعلنت أنها تستطيع حل أي مشكلة ، مهما كان ما اقترحه. قبل مليخوف التحدي.
Grigory ناتاليا
A مصفوفة تتكون من
n أعداد صحيحة غير سالبة. ثم يطلب منها إجراء عمليات
q من نفس النوع ، والتي تتكون مما يلي: "مع الأخذ في الاعتبار الأرقام
l و
r و
ك . علاوة على ذلك ، بالنسبة لكل فهرس
i من
l إلى
r ، يتم استبدال الرقم
k بدلاً من الرقم
A i ويعتبر حصريًا على مستوى البت "أو" جميع الأرقام في المقطع
\ ([l؛ r] \) ، وبعد ذلك يتم إرجاع الرقم
A i المكان مرة أخرى> أنا & quot ؛.
وبالتالي ، هناك
\ (r - l + 1 \) استبدالات مستقلة لا تغير المصفوفة ، وبالتالي
\ ( r - l + 1 \) ينتج عنه "حصري قليلاً" "أو". تحتاج ناتاليا إلى إخبار غريغوري قليلاً "حصريًا" "أو" جميع نتائج الاستبدال (لفهم أفضل ، راجع الأمثلة).
& nbsp؛
ساعد ناتاليا كورشونوفا في التعامل مع هذه المهمة! ثم سيعود غريغوريوس لها بالتأكيد!
& nbsp؛
إدخال
السطر الأول هو عدد صحيح
n (
\ (1 & lt؛ = n & lt؛ = 10 ^ 5 \) ) & ndash؛ عدد عناصر المصفوفة.
يحتوي السطر الثاني على n أعداد صحيحة غير سالبة لا تتجاوز \ (10 ^ 8 \) .
السطر الثالث هو عدد صحيح
q (
\ (1 & lt؛ = q & lt؛ = 10 ^ 5 \) ) & ndash؛ عدد الطلبات.
يحتوي ما يلي على q سطور ، كل منها يحتوي على 3 أعداد صحيحة: l ، r ، k ( \ (1 & lt؛ = l & lt؛ = r & lt؛ = n \) ، \ (0 & lt؛ = k & lt؛ = 10 ^ 8 \) ).
& nbsp؛
الإخراج
أنت بحاجة إلى إخراج ردود
q لكل استعلام في سطر واحد مفصولة بمسافة.
نبسب ؛
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
شرح
الطلب الأول:
1) 7 و oplus ؛ 2 و oplus. 3 = 6
2) 1 و oplus ؛ 7 وأبلس. 3 = 5
3) 1 & oplus؛ 2 و oplus. 7 = 4
6 و oplus ؛ 5 وأبلس. 4 = 7
الإجابة: 7.
& nbsp؛
الطلب الثاني:
1) 10 & oplus؛ 5 = 15
2) 4 و oplus ؛ 10 = 14
15 & oplus؛ 14 = 1
الإجابة: 1.
& nbsp؛