یک توری $N\times N$ $(N\leq 100)$ داده شده است. نقاط این توری با مختصات $(i,j)$ مشخص می‌شوند. مختصات نقطه‌ی واقع در گوشه‌ی سمت چپ و پایین توری $(0,0)$ و مختصات نقطه‌ی واقع در گوشه‌ی بالا و سمت راست $(N-1,N-1)$ است. هر نقطه مانند $(i,j)$ از این توری به چهار نقطه‌ی $(i,j \pm 1)$ و $(i\pm 1 , j)$ در صورت وجود وصل است.

$M$ نقطه در این توری داده شده‌اند. می‌خواهیم هر یک ا ز این نقطه‌ها را با مسیری مستقیم به عنوان راه فرار به یکی از نقاط مرزی توری وصل کنیم، به طوری که این مسیرها یک‌دیگر را قطع نکنند $(M\leq 100)$.

1. با فرض این که مسیرها متصل‌کننده‌ی نقاط به نقاط مرزی، همگی یا به سمت راست و یا به سمت پایین باشند این مسئله را حل کنید.
2. در صورتی که قسمت اول جواب نداشته باشد، با فرض این که مسیرها همگی به سمت راست، چپ و یا به سمت پایین باشند مسئله را حل کنید.

در فایل ورودی چند مجموعه داده که با یک سطر فاصله‌ی خالی از هم جدا شده‌اند قرار دارد. در سطر اول هر مجموعه داده‌ی ورودی به ترتیب اعداد $N$ و $M$ و در $M$ سطر بعد، مختصات $M$ نقطه از توری قرار دارند.

در فایل خروجی که در آن خروجی مربوط به هر مجموعه داده با یک سطر خالی از هم جدا می‌شوند. شکل خروجی مربوط به هر مجموعه داده به این صورت است: در صورتی که قسمت (۱) جواب داشته باشد، در $M$ سطر، در هر سطر مختصات یک نقطه‌ی ورودی و جهت راه فرار آن را بنویسید. جهت‌های راست، چپ و پایین را به ترتیب با نویسه‌های $R$، $L$ و $D$ مشخص کنید. در صورتی که قسمت (۱) جواب نداشته باشد، ابتدا پیغام زیر را بنویسید:

$$Part \quad 1 \quad has \quad no \quad solution.$$

و در سطر‌های بعد، در صورتی که قسمت (۲) جواب داشت، جواب آن را به همین صورت و در غیر این صورت پیغام زیر را بنویسید.

$$Part \quad 2 \quad has \quad no \quad solution.$$

به مثال زیر توجه کنید. مجموعه داده‌های اول و دوم این مثال در شکل زیر نشان داده شده است. همان‌طور که در مثال مشاهده می‌کنید در مورد مجموعه داده‌ی سوم هیچ یک از دو قسمت مسئله جواب ندارد.

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