بازی با نوار

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

در هر نوبت می‌توانیم هر مهره را که خواستیم حرکت بدهیم. قواعد حرکت برای مهره‌ی اول به شکل زیر هستند:

• مهره یک شمارنده دارد، که اول بازی برابر صفر است. این شمارنده را $i$ می‌نامیم.
• «اعداد حرکت» $a_1,a_2,…,a_k$ داده شده‌اند.
• وقتی می‌خواهیم مهره را حرکت بدهیم، اول یکی به مقدار $i$ اضافه می‌کنیم. سپس یک جهت (جلو یا عقب) انتخاب می‌کنیم. مهره را $a_i$ بار در آن جهتی که انتخاب کردیم، هر بار یک خانه، جابه‌جا می‌کنیم. در ضمن، حرکتی که در طی آن مجبور شویم از روی مهره‌ی دیگر رد شویم، مجاز نمی‌باشد! توجه کنید که نوار دایره‌ای شکل است، پس خانه‌ی بعد از $n$، ۱ است و خانه‌ی قبل از ۱،$n$ است. به عنوان مثال، فرض کنید $n$ برابر ۱۰ است، مهره در خانه ۷ است، مهره‌ی دیگر در خانه‌ی ۵ و $a_i$‌ ۴ است. آن‌گاه مهره می‌تواند به طرف جلو از ۷ به ۱ برود، اما نمی‌تواند از ۷ به ۳ برود، زیرا نمی‌تواند از محل مهره‌ی دیگر رد شود. توجه کنید که اینجا رفتن از ۷ به ۱، یک حرکت محسوب می‌شود.
• تعداد دفعاتی که مهره حرکت می‌کند نباید از $k$ بیش‌تر شود. به عبارت دیگر، همواره $i\leq k$.

حرکت مهره‌ی دوم هم به همین صورت است. توجه کنید که هر مهره، شمارنده و «اعداد حرکت» مخصوص خودش دارد. وقتی یک مهره را حرکت می‌دهیم، فقط شمارنده‌ی آن مهره تغییر می‌کند و از همان شمارنده برای تعیین اندازه حرکت استفاده می‌کنیم.

در خط اول فایل ورودی اعداد $x،k،n$ و $y$ نوشته شده‌اند. $x$ و $y$ به ترتیب مکان‌های اولیه‌ی مهره‌ی اول و مهره‌ی دوم هستند. توجه کنید که $x \neq y$. در خط بعد، $a_1$ تا $a_k$ به ترتیب نوشته شده‌اند که «اعداد حرکت» برای مهره‌ی اول هستند. در خط سوم هم به همین صورت، اعداد $b_1$ تا $b_k$ آمده‌اند که «اعداد حرکت» برای مهره‌ی دوم هستند.($n$ و $k$ به ترتیب از ۱۰۰۰ و ۵۰۰ بیش‌تر نیستند.)

در این فایل، ابتدا کم‌ترین تعداد حرکت را بنویسید. سپس حرکت‌ها را به ترتیب از اول به آخر بنویسید. برای هر حرکت، ابتدا شماره‌ی مهره‌ای را که حرکت می‌کنید را بنویسید( ۱ برا مهره‌ی اول و ۲ برای مهره‌ی دوم). سپس شماره‌ی خانه‌ی این مهره پس از حرکت را بنویسید.

اگر بیش از یک راه‌حل وجد داشته باشد، یک راه‌حل بنویسید. اگر هیچ راه‌حلی وجود نداشته باشد، در فایل خروجی تنها عدد ۰ را بنویسید.

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

• سوال بعد
• سوال قبل