محمدسهیل در تلاش برای استخدام در بخش تحقیقاتی شرکت شیررضا است. او برای استخدام شدن نیاز دارد که در آزمون ورودی این شرکت قبول شود. آزمون این شرکت به صورت یک سوال شمارشی-الگوریتمی است که برای محمدسهیل ارسال شده و او باید تا پایان امروز آن را حل کند.

سوال آزمون ورودی او بدین صورت است؛ «عدد شکعط» آرایه‌ی $x=\langle x_1,x_2,\cdots,x_k\rangle$ را برابر با مقدار زیر تعریف می‌کنیم:

$$shakat(x)=\sum_{i=1}^{k}x_i\oplus gcd(x)$$

در این فرمول $gcd(x)$ برابر با ب.م.م کل اعداد آرایه‌ی $x$ است. محمدسهیل باید برای قبول شدن در آزمون استخدامی شرکت شیررضا جمع عدد شکعط تمام زیرآرایه‌های¹⁾ ناتهی آرایه‌ی ورودی را حساب کرده و به عنوان خروجی چاپ کند.

ورودی

در خط اول ورودی عدد $n$ آمده است. در خط بعدی $n$ عدد آمده است که عدد $i$ام نشان‌دهنده‌ی $a_i$ است. چهار فایل با نام‌های ocd-1.in و ocd-2.in و ocd-3.in و ocd-4.in در اختیار شما قرار داده شده‌اند که هر یک شامل ورودی برای یک زیرمسئله از سوال است. محدودیت‌های هر فایل در بخش زیرمسئله‌ها نوشته شده و اطلاعات آن‌ها از طریق خود فایل نیز قابل مشاهده است.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

بخش اول (۱۳ نمره) : اگر جواب برای حالت توصیف شده در فایل ocd-1.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=6, 1\leq a_i\leq6$ است.

بخش دوم (۱۹ نمره) : اگر جواب برای حالت توصیف شده در فایل ocd-2.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=300, 1\leq a_i\leq10^9$ است.

بخش سوم (۲۹ نمره) : اگر جواب برای حالت توصیف شده در فایل ocd-3.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=3000, 1\leq a_i\leq10^9$ است.

بخش چهارم (۳۹ نمره) : اگر جواب برای حالت توصیف شده در فایل ocd-4.in را $x$ بنامیم، مقدار $x^{10}$ را به پیمانه‌ی $\Delta$ چاپ کنید. در این فایل $n=3\times10^5, 1\leq a_i\leq10^{18}$ است.