• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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

او با تحقیق بسیار بوسیله‌ی ماهواره‌ی مجهز به اشعه ایکس خود، اطلاعات ارزشمندی به دست آورده است. چون او از بالا و با ماهواره تحقیق کرده، فروشگاه را بصورت یک صفحه مختصات دکارتی می‌بیند که دیوار جنوبی و غربی فروشگاه محور‌های x و y مختصات هستند. او می‌داند که ۴ دوربین در این فروشگاه وجود دارد که مختصات آن ۴ دوربین، مختصات ۴ راس یک مستطیل روی این صفحه مختصات است که اضلاع آن موازی با محور‌های مختصات هستند.

دزد توانسته با تحقیقات فراوان، مختصات ۳ دوربین از ۴ دوربین را بفهمد. اما فهمیدن محل دوربین چهارم برای او خیلی سخت بود! با ورودی گرفتن این ۳ مختصات، مختصات دوربین چهارم را به او بگویید.

ورودی🔗

ورودی شامل سه سطر است. در هر سطر به ترتیب دو عدد $x$ و $y$ (با یک فاصله بینشان) آمده است که مختصات یکی از دوربین‌ها می‌باشد. تضمین می‌شود که این ۳ نقطه مختصات برای سه راس یک مستطیل است که مساحت آن بیش از صفر می‌باشد. $0 \le x,y \le 1\ 000\ 000\ 000$

خروجی🔗

در تنها سطر خروجی، دو عدد با یک فاصله بیشنان چاپ کنید که به ترتیب نمایانگر $x$ و $y$ دوربین چهارم هستند.

مثال🔗

ورودی نمونه ۱🔗

1 2
3 4
1 4

خروجی نمونه ۱🔗

3 2

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

دزد با مهارت، در دزدی به مهارت بالا رفتن و جانگولربازی (‌jungular play) نیاز دارد؛ چرا که بعد از پیدا کردن دوربین های فروشگاه و ورود به آن، او دریافت که تیله‌ها در طبقه‌ی آخر است. او در طبقه‌ی اول فروشگاه بوده و باید به طبقه‌ی آخر یعنی طبقه‌ی $n$ ام برود. هر طبقه دو پنجره دارد. یکی در سمت راست طبقه و یکی در سمت چپ طبقه(هر طبقه را یک پاره خط افقی فرض کنید که پنجره‌ها در دو لبه‌ی آن قرار دارد). اگر دزد در طبقه‌ی $k$ باشد، تنها می‌تواند به طبقه‌ی $k+1$ برود. اگر برای مثال او در طبقه‌ی $k$باشد، دو روش برای رفتن به طبقه‌ی بعدی وجود دارد:

۱. از پنجره‌ی سمت راست طبقه‌ی $k$ ام خارج شده و از طریق پنجره‌ی سمت راست، به طبقه‌ی $k+1$ وارد شود.

۲. از پنجره‌ی سمت چپ طبقه‌ی $k$ ام خارج شده و از طریق پنجره‌ی سمت چپ، به طبقه‌ی $k+1$ وارد شود.

متاسفانه در بعضی از طبقات، پلیس وجود دارد. در هر طبقه حداکثر یک پلیس وجود دارد. در طبقه‌ی اول و آخر پلیس وجود ندارد. هر پلیس چون خسته است(ساعت کاری شون زیاده!)، تنها می‌تواند مراقب یکی از پنجره‌های طبقه‌ای که در آن است، باشد؛ یعنی دزد نمی‌تواند از آن پنجره وارد آن طبقه شود و در عین حال نمی‌تواند در آن طبقه از پنجره‌ای که پلیس مراقب آن است، خارج شود و به طبقه‌ی بالا برود. یعنی اگر مثلا پلیسی در طبقه‌ی $k$ ام باشد و مراقب پنجره‌ی راست باشد و دزد بخواهد از طبقه‌ی $k-1$ ام به طبقه‌ی $k+1$ ام برود، باید از پنجره‌ی چپ طبقه‌ی $k-1$ ام خارج شده و از طریق پنجره‌ی چپ، به طبقه‌ی $k$ ام وارد شود. سپس باید دوباره از پنجره‌ی سمت چپ طبقه‌ی $k$ ام استفاده کرده و از طریق پنجره‌ی چپ، به طبقه‌ی $k+1$ ام وارد شود. دقت کنید که اگر در طبقه‌ای هیچ پلیسی نباشد، از هر دو پنجره‌ی آن می‌توان خارج و از هر دو پنجره‌ی آن می‌توان به آن وارد شد. دزد مکان پلیس‌ها و پنجره‌ای را که هر کدام مراقبش هستند، می‌داند. او به شما این اطلاعات را می‌دهد و شما می‌خواهد که به او بگویید که آیا می‌تواند به طبقه‌ی آخر برود یا خیر.

ورودی🔗

در هر ورودی، تعدادی تست آمده‌است که برنامه‌ی شما باید به آن‌ها به ترتیب پاسخ دهد.

در سطر اول هر ورودی یک عدد $t$ آمده است که نمایانگر تعداد تست‌هایی است که باید در این ورودی جواب داده شوند. سپس در هر تست:

در سطر اول هر تست دو عدد $n$ و $k$ آمده‌ است که نمایانگر تعداد طبقات و تعداد پلیس‌‌ها در این تست است. در $k$ سطر بعدی، در سطر i، ابتدا $a_i$ که نمایانگر طبقه‌ی حضور پلیس $i$ ام است،آمده است. سپس یک عدد آمده است که نمایانگر پنجره ایست که پلیس $i$ ام مراقب آن است که این عدد یا 0 است و یا 1:

0: به معنای اینکه پلیس $i$ ام مراقب پنجره‌ی راست است.

1: به معنای اینکه پلیس $i$ ام مراقب پنجره‌ی چپ است.

$3 \le n \le 100\ 000$ $0 \le k \le n-2$ $2 \le a_i \le n-1$

مجموع $n$ در تست‌های هر ورودی از $200\ 000$ بیشتر نیست.

خروجی🔗

در تنها سطر خروجی هر تست یکی از دو کلمه‌ی زیر را خروجی دهید:

• No: به معنای دزد نمی‌تواند به طبقه‌ی آخر برسد
• Yes: به معنای اینکه دزد می‌تواند به طبقه‌ی آخر برسد

مثال🔗

ورودی نمونه🔗

3
5 1
2 0
5 3
3 0
2 1
4 0
4 2
2 1
3 1

خروجی نمونه🔗

Yes
No
Yes

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

دزد با مهارت، باید بتواند خوب تمرکز کند. متاسفانه دزد با وجود تمام شایستگی‌هایش موفق نشد که از سد پلیس‌ها رد شود و به طبقه‌ی آخر برود. بنابراین او یک راه دیگر را برای رسیدن به طبقه‌ی آخر انتخاب کرده است. او می‌خواهد با استفاده از تمرکز ذهنی، به پرواز در آمده و به طبقه‌ی آخر برود. اما متاسفانه مسئله‌ای بدجور فکرش را مشغول کرده و به او اجازه‌ی تمرکز نمی‌دهد. او از شما می‌خواهد که این مسئله را برایش حل نمایید تا فکرش آزاد شود. مسئله این است:

اعداد یک تا $n$ بدون تکرار و به ترتیب دلخواه در یک ردیف نوشته‌ شده‌اند. به این ردیف به ترتیب دلخواه از اعداد، جایگشت می‌گوییم. برای مثال 5،6،4،1،3،2 یک جایگشت شش تایی است. پس ما یک جایگشت داریم. حالا از روی این جایگشت بدین گونه یک گراف می‌سازیم:

اگر جایگشت را بصورت $p_1, p_2, ..., p_n$ نشان دهیم و راس های گراف ما با اعداد ۱ تا $n$ شماره گذاری شده باشند، یالی بین راس شماره $i$ و راس شماره $j$ وجود دارد اگر و تنها اگر $i < j$ و $p_i > p_j$.

برای مثال اگر جایگشت ما 2،3،1 باشد، در گراف متناظر، راس شماره‌ی سه به دو راس دیگر متصل است ولی راس شماره‌ی دو به راس شماره‌ی یک متصل نیست.

حالا سوال این است که این گراف چند مولفه‌ی همبندی دارد. (برای توضیحات بیشتر راجع به گراف و مولفه همبندی، اینجا را ببینید.)

ورودی🔗

در سطر اول ورودی $n$ آمده است که نمایانگر تعداد اعداد در جایگشت است. در سطر بعدی $n$ عدد آمده است که جایگشت را نشان می‌دهند. $i$مین عدد از این اعداد نمایانگر $p_i$ است. این اعداد، عددهای 1 تا $n$ هستند که به ترتیب دلخواه کنار هم چیده شده‌اند و هیچ عددی در این سطر دوبار نیامده است.

$1 \le n \le 1\ 000\ 000$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

6
3 2 4 1 6 5

خروجی نمونه🔗

2

توضیح:

یال‌ها در گراف ساخته شده بین راس‌های زیر هستند:

یک و دو، چهار و یک، دو و چهار، سه و چهار و پنج و شش.

که باعث به وجود آمدن دو مولفه همبندی می‌شود که مولفه‌ی اول شامل راس‌های شماره‌ی 1 و 2 و 3 و 4 و مولفه‌ی دیگر شامل راس‌های 5 و 6 می‌باشد.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

دزد با مهارت، به طبقه‌ی آخر رسید. او در آنجا با یک گاوصندوق مواجه شد که شنیده بود که پر از تیله است. اما او در اینجا با یک سد دفاعی محکم مواجه شد. پروفسورباقر که مسئول طراحی سیستم دفاعی فروشگاه بود(و خیلی هم ناشی بود)، موقع طراحی طبقه‌ی آخر، برای اینکه دزدی نتواند به گاوصندوق راه پیدا کند، بر روی زمین تیله ریخته بود تا هر کس بخواهد به گاوصندوق برسد، روی این تیله‌ها لیز بخورد و سپس به زمین نیز (چی؟) بخورد. وقتی دزد به طبقه‌ی آخر رسید، متوجه شد که بر روی زمین مقدار زیادی تیله ریخته شده است و او هم که به دزدی تیله آمده بود؛ پس شروع کرد به جمع کردن تیله‌های روی زمین. او تیله ها را در ‌$n$ کیسه ریخت. بعد از آن از ساختمان خارج شد و به پیش عمو (که بسیار پول پرست است) رفت تا کیسه‌هایش را بفروشد اما عمو در حال پرستش بود و در آن لحظه نمی‌توانست به دیدار دزد بیاید. برای همین دزد به اتاق انتظار رفت تا منتظر عمو بماند.

دزد کیسه‌ها را بر روی یک میز در یک ردیف چید و منتظر ماند تا عمو بیاید. او کیسه‌ها را از یک تا $n$ به ترتیب از چپ به راست نام گذاری کرد و می‌داند که در کیسه‌ی $i$، $a_i$ تیله وجود دارد. در همین حین ناگهان نکته‌ای به ذهن دزد رسید: عمو همیشه موقع خرید تیله، یک بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب می‌کند و اگر تعداد تیله ها در این $d$ کیسه زوج بود، پولش را می‌دهد و گرنه با لگد دزد را از دفترکارش بیرون می‌اندازد(بالاخره عمو که نمی‌تواند خدایش را به راحتی به دست دزد بدهد که.خدایش است ها علف خرس که نیست). به همین دلیل دزد مجبور است که تعداد تیله‌ها در برخی کیسه‌ها را تغییر دهد تا اگر عمو هر بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب کرد، تعداد تیله‌ها در مجموع این کیسه ها زوج باشد. خوشبختانه دزد تعدادی تیله در جیبش دارد. او در یک عملیات می‌تواند یک کیسه را انتخاب کند و دقیقا یک تیله به آن اضافه کند. به او بگویید که کمینه‌ی تعداد عملیات برای این که کیسه‌ها را مطابق میل عمو کند چقدر است.

ورودی🔗

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

سپس در خط بعد $n$ عدد آمده است که عدد $i$ ام نمایانگر تعداد تیله‌ها در کیسه‌ی $i$ است.

$1 \le d \le n \le 1\ 000\ 000$ $0 \le a_i \le 1\ 000\ 000\ 000$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

5 3
1 3 0 5 2

خروجی نمونه🔗

1

توضیح نمونه:

تنها کافیست که دزد یک تیله به کیسه‌ی آخر بیافزاید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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

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

برای مثال اگر ۵ کیسه روی میز باشد و دنباله‌ی "صاحب‌ها"ی آن‌ها برابر با aabcd باشد، عمو ۴ حالت برای انتخاب بازه‌ی برای خرید دارد: دو کیسه‌ی اول، کیسه‌ی سوم، کیسه‌ی چهارم و یا کیسه‌ی پنجم. اگر ۳ کیسه روی میز باشد و دنباله‌ی "صاحب‌ها" برابر "aba" باشد نیز عمو ۳ حالت برای انتخاب بازه‌ برای خرید دارد: همه‌ی بازه‌های شامل تنها یک کیسه.

عمو دید که حداکثر ۱۰۰ انتخاب برای بازه‌‌ی خرید دارد؛ پس بعنوان یک فرد پول‌پرست شروع به چانه‌زنی کرد که "الان توی دزد، اومدی یجوری این کیسه‌ها رو چیدی که من مجبور شم بین این تعداد گزینه انتخاب کنم! تو منو محدود کردی، و انتظار پول داری؟!"

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

برای مثال اگر دنباله‌ی "صاحب‌ها" برابر aabcd باشد، دزد شروع به توضیح میکند که "اگر دقت کنید اگر من کیسه‌ها را طوری می‌چیدم که دنباله‌ی aacbd درست میشد هنوز هم شما ۴ انتخاب داشتید عموی بزرگ. aadbc هم! baacd هم!" و ...

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

چون این عدد ممکن است بسیار بزرگ باشد و در نتیجه عمو نتواند بخواندش، او از شما خواسته که باقی‌مانده‌ی جواب را بر 1000003 (که تعداد کلید گنج‌های عمو است) اعلام کنید.

ورودی🔗

در تنها سطر ورودی یک رشته از حروف کوچک انگلیسی آمده‌است که نمایانگر دنباله‌ی "صاحب‌ها"ی کیسه‌های روی میز است.

طول این دنباله حداکثر $500\ 000$ است.

تضمین می‌شود که عمو حداکثر ۱۰۰ انتخاب برای بازه‌ی خرید دارد.

خروجی🔗

در تنها سطر خروجی باقی‌مانده‌ی جواب را بر 1000003 اعلام چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

aabcd

خروجی نمونه ۱🔗

24

ورودی نمونه ۲🔗

bzzooeerep

خروجی نمونه ۲🔗

7200

ورودی نمونه ۳🔗

aba

خروجی نمونه ۳🔗

1