+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در یک زمین مستطیلی رباتی وجود دارد. این زمین را میتوان با $m$ سطر و $n$ ستون نمایش داد. ربات میتواند در ۴ جهت اصلی بالا، پایین، چپ و راست حرکت کند. ربات در ابتدا در خانه گوشه چپ پایین قرار دارد. در این نقشه خانه‌هایی وجود دارد که ربات باید به یکی از این خانه‌ها برسد. همچنین خانه‌هایی نیز هستند که اگر ربات وارد آنها شود دیگر نمیتواند از آنها خارج شود. وظیفه شما این است که برنامه‌ای بنویسید که با دانستن نقشه زمین در صورتی که مسیری برای رسیدن به یکی از اهداف وجود دارد کوتاهترین مسیر را برای رسیدن به یکی از این اهداف پیدا کند. ## ورودی در ورودی ابتدا $2\leq m,n \leq 1000$ که ابعاد زمین را نشان می‌دهند، به ترتیب از چپ به راست می‌آیند. سپس در $m$ سطر بعدی هر کدام یک رشته‌ای به طول $n$ وجود دارد که نقشه را نمایش می‌دهند. نقطه شروع حرکت ربات با ```'^'``` در نقشه مشخص شده است. اهداف با ```'*'``` و تله‌ها با ```'#'``` مشخص شده اند. ## خروجی اگر مسیری برای رسیدن به هیچ‌کدام از اهداف وجود ندارد در خروجی باید ```1-``` چاپ شود.در صورتی که مسیر وجود دارد در خروجی باید مسیر به صورت دنباله‌ای از کاراکتر‌ها بیاید که به ازای هر حرکت به سمت بالا ```u```، حرکت به سمت چپ ```l```، حرکت به سمت پایین ```d``` و حرکت به سمت راست ```r``` چاپ شده است. اگر چندین مسیر با طول یکسان وجود داشته باشد باید مسیری چاپ شود که از نظر ترتیب در دیکشنری (lexicographical order) اول باشد. ## ورودی-خروجی نمونه ورودی نمونه ۱ 2 2 -* ^- خروجی نمونه ۱ ru ورودی نمونه ۲ 5 5 -*-#* *---# ###-# ----# ^--#* خروجی نمونه ۲ rruruulll