یک رنگ آمیزی مستطیلی شامل چندین مستطیل است که شرایط زیر را داشته باشند:

1. هر مستطیل یا به طور کامل درون یک مستطیل دیگر است یا با دیگر مستطیل‌ها هم‌پوشانی ندارد.
2. اضلاع هر مستطیل موازی با محورهای $x$ و $y$ هستند.
3. اضلاع هر دو مستطیل حداقل $d$ واحد با یکدیگر فاصله دارند؛ حتی اگر یکی شامل دیگری باشد.
4. به ازای هر مستطیل، کوچکترین مستطیلی که شامل آن باشد را مستطیل مافوق آن می‌نامیم. به دو مستطیل که مستطیل مافوقشان یکی باشد، هم‌مستطیلی می‌گوییم. همه‌ی هم‌مستطیلی‌ها با هم یا به صورت افقی یا عمودی هم‌ردیف هستند. دو هم‌مستطیلی به صورت افقی (عمودی) هم‌ردیف هستند اگر ضلع پایین (چپ) آن‌ها با هم در یک راستا باشند.
5. هر مستطیلی که که هیچ مستطیلی درونش نباشد، یک مستطیل عکسی نامیده می‌شود و با یک عکس به اندازه‌ی خودش پر می‌شود.
6. هر رنگ‌آمیزی مستطیلی فقط یک مستطیل دارد که مستطیل مافوق نداشته باشد. به آن مستطیل، مستطیل ریشه می‌گوییم.
7. مختصات گوشه‌های همه‌ی مستطیل‌ها اعداد صحیح هستند.

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

ورودی شامل چندین سناریو است. هر سناریو با یک خط شامل $1 \leq n \leq 100$ و $0 \leq d \leq 30$ شروع می‌شود که $n$ تعداد مستطیل‌های موجود در رنگ‌آمیزی مستطیلی است. در $n$ خط بعدی، خط $i$ام مشخصات $i$مین مستطیل است (مستطیل شماره $i$). شماره مستطیل ریشه $1$ است. فرض کنیم $R_i$ مجموعه‌ی شماره‌ی مستطیل‌هایی باشد که مستطیل مافوقشان مستطیل شماره $i$ است. اگر $R_i$ تهی نباشد، مشخصات مستطیل $i$ شامل اندازه‌ی $R_i$ و به دنبال آن اعضای $R_i$ می‌باشد که همگی با فاصله از هم جدا شده‌اند. در غیر این صورت، مستطیل یک مستطیل عکسی خواهد بود و مشخصات آن به صورت $"0\ a\ b"$ است که $1 \leq a \leq 30$ و $1 \leq b \leq 30$ به ترتیب اندازه‌های اضلاع موازی با محور $x$ و $y$ می‌باشند. ورودی با یک خط شامل $"0\ 0"$ پایان می‌یابد.

به ازای هر سناریو، در یک خط مساحت کمینه‌ی مستطیل ریشه را از میان همه‌ی چینش‌های ممکن برای رنگ‌آمیزی مستطیلی داده شده چاپ کنید.

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

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