+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۰ مگابایت ---------- ماجرا از این قرار است که امیر حسین اعداد اول را خیلی دوست دارد... . وی در خانه‌ی $(a,b)$ یک جدول $n \times n$ قرار گرفته و می‌خواهد به خانه‌ی $(x,y)$ برود. از شما کمک می‌خواهد تا یک مسیر مناسب از نقطه‌ی شروع به نقطه‌ی هدف را به او نشان دهید. این مسیر باید شرایط زیر را داشته باشد: + داخل هر خانه از جدول، عددی نوشته شده است و امیرحسین فقط از خانه‌ای عبور می‌کند که عدد روی آن اول باشد. + هنگامی که امیرحسین روی یکی از خانه‌های جدول ایستاده است، در حرکت بعدی فقط می‌تواند به یکی از خانه‌های مجاور ضلعی‌اش برود.(بالا، پایین ، چپ یا راست) + در مسیری که وی طی می‌کند، نباید هیچ یک از خانه‌های جدول را دوبار ملاقات کند. # ورودی ابتدا عدد $t$ که نشان دهنده‌ی تعداد تست‌های سوال است داده می‌شود. $$1 \le t \le 100$$ به ازای هر تست: عدد $n$ به عنوان سایز ماتریس و سپس $n^2$ عدد که نشان دهنده‌ی مقادیر خانه‌های ماتریس هستند وارد می‌شوند. $$1 \le n \le 100$$ $$1 \le a_{i,j} \le 10^9$$ سپس در یک خط، مختصات شروع و در خط بعدی مختصات پایان داده می‌شود.(برای فهم بهتر سوال، حتماً مثال را ببینید.) تضمین می شود: + محتویات خانه‌ی $(a,b)$ و خانه‌ی $(x,y)$ حتما اعدادی اول هستند. + جواب سوال یکتاست (دو مسیر مناسب وجود نداشته باشد). + خانه‌ی شروع حداکثر یک همسایه‌ی اول دارد و هر یک از خانه‌های مسیر حداکثر دو همسایه‌ی اول دارند.(سعی کنید به عنوان تمرین بیشتر، سوال را در حالتی حل کنید که مسیرهای انحرافی نیز وجود داشته باشند.) # خروجی در $t$ خط به ازای هر تست، اگر مسیر مناسبی با شرایط گفته شده از نقطه‌ی آغاز به نقطه‌ی هدف وجود دارد، آن مسیر را با کاراکترهای $U,D,L,R$ نشان دهید و در غیر اینصورت "!No Monaseb Masir" را چاپ کنید. # مثال ## ورودی نمونه ``` 3 4 5 2 6 11 4 5 13 8 7 10 3 7 2 13 15 11 0 0 3 3 3 5 2 7 8 4 1 7 5 3 2 0 0 1 6 15 2 3 5 11 77 14 5 1 4 2 1 12 7 13 6 2 4 6 8 76 9 7 95 5 11 13 7 5 8 2 96 10 4 100 17 2 2 5 0 ``` ## خروجی نمونه ``` RDRDRD No Monaseb Masir! LUURRRDDDDLLLLD ```

حل سؤال در بانک سؤالات