- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۱۲۸ مگابایت
برنامهای بنویسید که عدد \(n\) و سپس یک دنباله \(n\)-تایی \(a_1, a_2, a_3, ..., a_n\) را از ورودی بخواند. سپس به برنامهی شما \(q\) پرسش داده میشود که هر پرسش بصورت یک عدد \(r\) است و برنامهی شما باید نتیجهی این پرسش را چاپ کند. نتیجهی پرسش \(r\) برابر مقدار زیر است:
\[\sum _{i = 1} ^ r a_i \ xor\ (r - i)\]
برنامهتان را طوری بنویسید که پیشپردازش طولانی نداشته باشد و پاسخ هر پرسش را سریع بدهد؛ یعنی پیش از پرسش اول و پس از دریافت هر پرسش تا پایان خروجی دادن کمتر از ضریب ثابتی از \(n\) دستور (مستقل از دیگر متغیرهای ورودی بجز \(n\)) انجام بشود. همچنین کل اجرای برنامهی شما نباید بیش از ۲ ثانیه طول بکشد.
راهنمایی:
روشهای مختلفی برای پیادهسازی بهینه وجود دارد؛ یکی از آنها اینچنین است: برای هر پرسش مقدار گفتهشده را با یک حلقه ساده بدست آورید؛ در این روش تنها کاری که برای بهینهسازی زمان برنامه باید بکنید این است که پس از محاسبهی نتیجهی یک پرسش، این نتیجه را جایی ذخیره کنید که اگر در ادامه دقیقاً همان پرسش دوباره مطرح شد، دوباره آن را محاسبه نکنید و مقداری که از قبل محاسبه شده بود را خروجی دهید.
ورودی
در سطر اول ورودی دو عدد \(n\) و \(q\) آمده است و در سطر دوم \(n\) عدد طبیعی آمده است که عدد \(i\)-ام نمایانگر \(a_i\) است. سپس در \(q\) سطر بعدی هر خط یک سوال بصورت یک عدد طبیعی آمده است که برابر \(r\) است.
\[1 \le a_i \le 1\ 000\ 000\] \[1 \le r \le n \le 10\ 000\] \[1 \le q \le 500\ 000\]
خروجی
در \(q\) سطر هریک یک عدد چاپ کنید که پاسخ به یکی از پرسشهای داده شده است.
مثال
ورودی نمونه
4 4
4 3 6 2
1
2
3
4
خروجی نمونه
4
8
14
17
پاسخ پرسشها به ترتیب:
\(4\ xor\ 0 = 4\)
\((4 \ xor\ 1) + (3 \ xor\ 0) = 5 + 3 = 8\)
\((4 \ xor\ 2) + (3 \ xor\ 1) + (6 \ xor\ 0) = 6 + 2 + 6 = 14\)
\((4 \ xor\ 3) + (3 \ xor\ 2) + (6 \ xor\ 1) + (2 \ xor\ 0) = 7 + 1 + 7 + 2 = 17\)