+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شما بایستی از الگوریتم $A*$ برای حل مسئله راه‌بندان استفاده کنید. در این مسئله، یک خودروی قرمز رنگ به همراه چند خودروی دیگر در یک پارکینگ مشابه شکل پارک شده‌اند. می‌خواهیم با جابجا کردن خودرو‌‌ها، برای خودروی قرمز رنگ که بین سایر خودروها گرفتار شده است، راهی باز کرده و آن را از پارکینگ خارج نماییم. همه‌ی خودروها در این پارکینگ به صورت افقی و عمودی پارک شده‌اند. از آنجایی که اکنون امکان دور زدن وجود ندارد، خودروهایی که به صورت افقی قرار دارند تنها می‌توانند به چپ و راست حرکت کرده و خودروهای عمودی نیز فقط امکان بالا و پایین رفتن دارند.  هدف این است که با کمترین تعداد حرکت، خودروی قرمز رنگ را که همواره به صورت افقی و روبروی درب خروجی (که در ضلع شرقی پارکینگ قرار دارد) پارک شده است، از پارکینگ خارج نماییم. در هر حرکت، یک خودرو می‌تواند در راستایی که قرار دارد به هر تعداد خانه دلخواه جابجا شود، مشروط بر اینکه با سایر خودروها و یا دیوار برخورد نکند. همچنین خارج کردن خودروهای دیگر به جز خودروی قرمز رنگ از پارکینگ مجاز نمی‌باشد. # ورودی ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد $T$ است که تعداد پارکینگ‌ها را مشخص می‌کند. پس از آن مشخصات $T$ پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد $N$ ،$M$ و $V$ قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص می‌کند. $V$ خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد $R$ و $C$ قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص می‌کنند. در ادامه راستای خودرو با یک کاراکتر $h$ برای افقی و یا $v$ برای عمودی مشخص می‌شود. در انتهای خط نیز عدد $L$ طول خودرو را نشان می‌دهد. لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر $N$ و ستون $M$ قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است. # خروجی به ازای هر پارکینگ، برنامه باید کمترین تعداد حرکات که منجر به خروج خودروی قرمز رنگ از پارکینگ می‌شود را چاپ کند. نمونه خروجی برای شکل در زیر آمده است. ## ورودی نمونه ``` 1 6 6 13 3 1 h 2 1 1 v 2 1 2 v 2 1 4 h 3 2 3 h 2 2 5 h 2 3 4 v 2 4 2 v 2 5 3 h 2 5 5 v 2 5 6 v 2 6 1 h 2 6 3 h 2 ``` ## خروجی نمونه ``` Test #1: 16 ```