آرام دان №3
گریگوری به ناتالیا یک آرایه A می دهد که از n اعداد صحیح غیر منفی تشکیل شده است. سپس از او می خواهد که عملیات q از همان نوع را انجام دهد که شامل موارد زیر است: "با توجه به اعداد l، r و k . علاوه بر این، برای هر فهرست i از l تا r، عدد k به جای عدد جایگزین می‌شود. >A i و از لحاظ بیتی یک انحصاری “یا” همه اعداد در بخش \([l;r]\)، پس از آن عدد Aiمکان دوباره >i".
بنابراین، \(r – l + 1\) جایگزین‌های مستقلی وجود دارد که آرایه را تغییر نمی‌دهد، و بر این اساس \( r – l + 1\) منجر به یک بیت انحصاری “یا” می شود. ناتالیا باید کمی انحصاری به گریگوری بگوید “یا” همه نتایج جایگزینی (برای درک بهتر، نمونه ها را بررسی کنید).
به ناتالیا کورشونوا کمک کنید تا با این کار کنار بیاید! سپس گرگوری قطعا به او باز خواهد گشت!
ورودی
خط اول یک عدد صحیح n است (\(1 <= n <= 10^5\)) – تعداد عناصر آرایه.
خط دوم حاوی n اعداد صحیح غیر منفی است که از \(10^8\) تجاوز نمی کنند.
خط سوم یک عدد صحیح q است (\(1 <= q <= 10^5\)) – تعداد درخواست ها.
خط زیر حاوی خطوط q است که هر کدام شامل 3 عدد صحیح است: l، r، k (\(1 <= l <= r <= n\)، \(0 <= k <= 10^8\)).
خروجی
شما باید پاسخ های
q را برای هر پرس و جو در یک خط که با یک فاصله از هم جدا شده است، خروجی بگیرید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
توضیح
اولین درخواست:
1) 7 + 2+ 3 = 6
2) 1 + 7+ 3 = 5
3) 1 + 2+ 7 = 4
6 ⊕ 5 + 4 = 7
پاسخ: 7.
درخواست دوم:
1) 10 + 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
پاسخ: 1.