یک حلزون در یک ماتریسی $n \times n$ از خانه $(0,0)$ شروع کرده و به صورت حلزونی ماتریس را دور می‌زند تا به درونی‌ترین نقطه ماتریس برسد. حلزون در این راه هر خانه که جلو می‌رود، عددها را جمع می‌کند. هرگاه این مجموع، مربع کامل بود، برای او حکم یک امتیاز دارد که ما در خروجی برنامه مجموع این امتیازها را می‌خواهیم.

نحوه‌ی حرکت حلزونی:

               S..........>..........
               ..>                  .
               .                    .
               ∧                    ∨
               .                    .
               .                    .
               ...........<.......... 

حرکت از بالا سمت چپ شروع میشود اول به راست حرکت میکنیم سپس به پایین و مانند شکل بالا حرکت را ادامه میدهیم.

ورودی🔗

در ورودی در سطر اول عدد $n$ می‌آید که نشان‌ دهنده ابعاد ماتریس است $(1 \leq n \leq 100)$. سپس یک ماتریس $n \times n$ می‌آید که به ترتیب داده‌های سطر صفرم تا $n-1$ ام ماتریس می‌باشد.

خروجی🔗

در تنها سطر خروجی مجموع امتیازها را چاپ کنید.

مثال🔗

ورودی نمونه ۱

4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

خروجی نمونه ۱

2

ورودی نمونه ۲

5
1 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49

خروجی نمونه ۲

7

در یک پادگان نظامی، $n$ سرباز وجود دارد که با شماره‌های ۱ تا $n$ مشخص شده‌اند. یک روز وقتی سربازان در یک صف ایستاده بودند، فرمانده که از تنبلی سربازان خود خسته شده بود، تصمیم به کار عجیبی گرفت.

او از سربازان خواست تا آرایش صف را به گونه‌ای تغییر دهند که افرادی که در جاهای فرد صف هستند برحسب شماره‌شان به صورت نزولی و افرادی که در جاهای زوج هستند به صورت صعودی مرتب شوند. فرمانده کسی را که در جای درستی نباشد به سختی مجازات می‌کند. سربازان از شما خواسته‌اند تا ترتیب صحیح قرار گیری آنها در صف را پیدا کنید.

ورودی🔗

در اولین خط ورودی، عدد $n$ که تعداد سربازان است به شما داده می‌شود ($1\leq n \leq 10000$). سپس در خط بعد $n$ عدد صحیح می‌آید که شماره‌ی سربازان در ترتیب اولیه‌ی صف است. این اعداد با فاصله از هم جدا شده‌اند.

خروجی🔗

در تنها خط خروجی $n$ عدد که شماره سربازان را در صف نهایی نشان می‌دهد بنویسید.

مثال🔗

ورودی نمونه ۱

5
1 2 3 4 5

خروجی نمونه ۱

5 2 3 4 1

ورودی نمونه ۲

10
20 13 45 7 0 1 3 5 6 1

خروجی نمونه ۲

45 1 20 1 6 5 3 7 0 13

ورودی نمونه ۳

8
-1 0 0 0 -1 -2 -3 10

خروجی نمونه ۳

0 -2 -1 0 -1 0 -3 10

روزی سپهر و دوستانش در حال پیاده روی در جنگل بودند. به طور کلی، $n$ نفرداشتند راه می رفتند که شامل سپهر هم می شد. ولی ناگهان به یک رود برخورد کردند. افراد فورا تصمیم گرفتند در عرض رود حرکت کنند. خوشبختانه یک قایق در کنار رود بود. می دانیم این قایق افراد حداکثر با مجموع وزن $k$ کیلوگرم را می تواند حمل کند. سپهر بلافاصله کاغذی برداشت و وزن افراد را نوشت. مشخص شد که افراد یا ۵۰ کیلوگرم وزن دارند یا ۱۰۰ کیلوگرم. حال سپهر می خواهد بداند حداقل تعداد باری که قایق باید از رودخانه عبور کند تا همه را منتقل کند چقدر است. با این فرض که هر دفعه حداقل یک نفر به عنوان قایقران نیاز است. همچنین او می خواهد بداند به چند طریق میتوان با حداقل گذر از رودخانه همه افراد را منتقل کرد. (اگر افراد در قایق متفاوت باشند آن طرق مختلف به حساب می آیند).

به سپهر در حل این سوال کمک کنید!

ورودی🔗

خط اول به ترتیب اعداد $n$ و $k$ را شامل میشود (که تعداد افراد و وزن قابل حمل توسط قایق است) و خط بعدی شامل $n$ عدد است که وزن افراد می‌باشد.

خروجی🔗

در خط اول حداقل تعداد راه گذر از رودخانه برای حمل همه افراد چاپ می‌شود و اگر حمل همه غیرممکن است $-1$ چاپ میشود. در خط دوم باقیمانده تعداد حالات حمل افراد با کمترین گذر را بر عدد $1000000007$ ($10^{9}+7$) چاپ می‌شود.

مثال🔗

ورودی نمونه اول

1 50
50

خروجی نمونه اول

1
1

ورودی نمونه دوم

3 100
50 50 100

خروجی نمونه دوم

5
2

آقای م.س. قصد دارد از تعدادی از بچه‌هایی که کارشان به او گیر کرده، کار بکشد تا بعدا اگر دلش خواست کار آنها را راه بیاندازد. برای همین به آنها گفته است: «به شما $n$ عدد میدهم شما باید XOR هر جفت از آنها را حساب کنید و نتیجه ها را باهم جمع بزنید و نتیجه را به من بگویید».

از آنجایی که شما انسان نجیب و دل‌رحمی هستید میخواهید به بچه‌‌ها کمک کنید و برنامه‌ای بنویسد که این کار را برای آن‌ها انجام دهد. به عنوان مثال فرض کنید مهندس سه عدد ۱، ۳ و ۵ را بدهد نتیجه برابر است با:

$(1 \oplus 3) + (1 \oplus 5) + (3 \oplus 5) = 2 + 4 + 6 = 12$

ورودی🔗

در اولین خط ورودی عدد $n$ ( $1 \leq n \leq 10^6$ ) می‌آید که بیانگر طول دنباله میباشد در $n$ خط بعدی در هر خط یک عدد می‌آید که اعضای دنباله هستند. اعضای دنباله در بازه $[1, 10^6]$ هستند.

خروجی🔗

در تنها خط خروجی خواسته مسئله را چاپ کنید.

مثال🔗

ورودی نمونه

3
1
3
5

خروجی نمونه

12

درخت، گرافی همبند است که بین هر دو رأس آن مسیر یکتایی وجود دارد. درختی $n$-رأسی که رئوسش از ۱ تا $n$ شماره
گذاری شده اند داریم که هر یک از یال
هایش به یکی از دو رنگ آبی و قرمز است. در $m$ پرسش، هر بار دو رأس $u$ و $v$ داده می
شوند و باید معین کنید که آیا مسیر بین آن دو رأس تک‌
رنگ است یا خیر.

به مسیری تک‌
رنگ گوییم که رنگ تمامی یال
های آن یکسان باشد.

ورودی🔗

در ابتدا $n$ ($2 \leq n \leq 10^5$) تعداد رئوس درخت و سپس $m$ ($1 \leq n \leq 10^5$) تعداد پرسش می‌آیند. در $n-1$ خط بعدی، در هر خط یکی از یال‌های درخت معرفی می‌شود به این صورت که ابتدا شماره رئوس متناظر با آن یال و سپس رنگ آن می
آید. عدد ۱ معرف رنگ آبی و عدد ۲ معرف رنگ قرمز است. در $m$ خط بعدی پرسش
‌ها می
‌آیند. بدین صورت که هر خط شامل شماره ۲ رأس متمایز است.

خروجی🔗

خر وجی شامل $m$ خط است. در خط $i$-اُم پاسخ پرسش $i$-اُم را چاپ کنید. اگر مسیر تک‌
رنگ بود مقدار ۱ و در غیر این صورت مقدار ۰ را چاپ کنید.

مثال🔗

ورودی نمونه

3 3
1 2 1
1 3 2
1 2
1 3
2 3

خروجی نمونه

1
1
0

جدولی $n \times 4$ دار یم که بعضی از خانه‌
های آن مسدود است. می
دانیم که دو ستون ۱ و $n$، خانه مسدود ندارند. به دنبال تعداد مسیر
های موجود در جدول از خانه بالا سمت چپ به خانه بالا سمت راست هستیم. هر مسیر دنباله
ای $n$-تایی از خانه‌
های نامسدود جدول است که از خانه بالا سمت چپ آغاز شده و به خانه بالا سمت راست منتهی می
شود و هر دو خانه متوالی آن با یکدیگر اشتراک رأسی یا یالی دارند. از آن
جایی که ممکن است این تعداد زیاد باشد، باقی
مانده‌
ی جواب در تقسیم بر $10^9 + 7$ را در خروجی نشان دهید.

ورودی🔗

در ابتدا $n$ ($1 \leq n \leq 10^{18}$ ) تعداد ستون
های جدول و سپس $m$ ($1 \leq m \leq 100$ ) تعداد خانه های مسدود می
آید. سپس در $m$ سطر بعد در هر سطر مختصات خانه های مسدود می
آید به این صورت که ابتدا شماره سطر و سپس شماره ستون خانه مسدود می
آیند.

خروجی🔗

در تنها سطر خروجی، پاسخ مسأله را چاپ کنید (پاسخ مسئله باقی
مانده‌
ی جواب در تقسیم بر $10^9 + 7$ است).

مثال🔗

ورودی نمونه ۱

5 2
1 2
2 3

خروجی نمونه ۱

3

ورودی نمونه ۲

28 2
3 10
2 10

خروجی نمونه ۲

368245731

جایگشت $\pi$ به طول $n$ از اعداد ۱، ۲، ... و $n$ را در نظر بگیرید. به زوج مرتب $(i,j)$ نابجایی می‌گوییم هرگاه $i \leq j$ و $\pi_{j} \leq \pi_{i}$.

خواسته‌ی مسأله پیدا کردن تعداد نابجایی های جایگشت داده شده در ورودی است.

ورودی🔗

در اولین سطر ورودی، طول جایگشت می آید. در سطرهای دوم تا $n+1$ اُم، اعضای جایگشت می
‌آیند. $1 \leq n \leq 10^6$

خروجی🔗

در تنها سطر خروجی تعداد نابجایی‌های جایگشت را بنویسید.

مثال🔗

ورودی نمونه اول

3
3
1
2

خروجی نمونه اول

2

ورودی نمونه دوم

4
2
4
1
3

خروجی نمونه دوم

3

تعداد $n$ خانه در نقاط صحیح مختصات قرار دارند. می‌خواهیم بین هر دو خانه یک سیم تلفن بکشیم. میزان سیم مورد نیاز برای وصل کردن دو خانه به اندازه‌ی فاصله‌ی منهتن آن‌ها است. برنامه‌ای بنویسید که طول بزرگترین سیم موردنیاز را پیدا کند.

ورودی🔗

در خط اول ورودی ابتدا عدد $n$ داده می‌شود. سپس در $n$ خط بعد در هر خط دو عدد که نشان‌دهنده‌ي مختصات خانه‌ی $i$ام است داده می‌شود.

خروجی🔗

طول بزرگترین سیم مورد استفاده را چاپ کنید.

محدودیت‌ها🔗

$1 \leq n \leq 100000$ $-1000000 \leq x_i,y_i \leq 1000000$

فاصله‌ی منهتن بین دو نقطه‌ی $(x_i,y_i)$ و $(x_j,y_j)$ برابر است با: $|x_i - x_j|+|y_i - y_j|$

مثال🔗

ورودی نمونه

5
2 2
4 6
3 8
9 2
5 5

خروجی نمونه

12