تا حالا کاغذ نت‌های یک موسیقی را دیده‌اید؟ متون موسیقی از چپ به راست خوانده می‌شوند و می‌توان آن‌ها را دنباله‌ای از نت‌ها مانند شکل زیر در نظر گرفت.

یکی از ایده‌های معروف برای کوتاه ساختن این متون، استفاده از ارجاع است. می‌دانیم یک موسیقی معمولا دارای قطعات تکراری است. پس اگر به جای نوشتن محدد تکرارهای یک تکه، به جایی که آن تکه قبلاه نوشته شده اشاره کنیم توانسته‌ایم این متن را تا حدی فشرده کنیم. مثلا در شکل بالا، قسمتی که در آن $<A-B>$ نوشته شده، به قسمتی از نت‌ها اشاره می‌کند که شروع و پایانش با حروف $A$ و $B$ نشان داده شده است.

نت‌های موسیقی در این مسئله با اعداد صحیح مدل شده‌اند. در عین حال، نت‌ها از چپ به راست به ترتیب با ۱، ۲ و … شماره‌گذاری شده‌اند. برای ارجاع به جاهای دیگر موسیقی از همین شماره‌گذاری استفاده می‌شود.

در این مسئله، قرار است یک متن موسیقی را از حالت فشرده در آوردید. شکل ارجاعات در موسیقی‌های فشرده‌ی این مسئله، کمی تعمیم‌یافته‌تر از نسخه‌های واقعی آن است:

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

برنامه‌ای بنویسید که:

• موسیقی فشرده را از ورودی بخواند.
• موسیقی را از حالت فشرده خارج کند.
• موسیقی غیر فشرده را در خروجی چاپ کند.

متن موسیقی فشرده شده، از چپ به راست در یک سطر آمده و از تعدادی «کلمه» درست شده است که با یک فاصله از هم جدا شده‌اند.

به ازای هر مقدار واقعی نت، یک کلمه در ورودی نوشته شده که عدد آن نت است.

به ازای هر ارجاع، ۵ کلمه در ورودی نوشته شده است:

$$<a-b>$$

کلمه‌های اول، سوم و پنجم به ترتیب کارکترهای ‘<’ و ‘−’ و ‘>’ هستند. کلمه‌ی دوم $(a)$، ابتدا و کلمه‌ی چهارم $(b)$، انتهای بازه‌ای از نت‌ها است که این ارجاع به آن اشاره می‌کند $(a\leq b)$.

بدیهی است این ارجاع به تنهایی $b-a+1$ نت را در دل خود دارد و این نکته در شماره‌گذاری نت‌های بعدی تاثیر دارد. اگر $a=b$ بود، ممکن است ارجاع با ۳ کلمه هم در ورودی نوشته شود:

$$<a>$$

ورودی به گونه‌ای است که هیچ ارجاعی به بیرون آهنگ ندارد. پایان ورودی با کلمه‌ی $\$$ مشخص می‌شود.(طول آهنگ فشرده نشده جداکثر $10^5$ است. اعداد ورودی در محدوده‌ی اعداد صحیح علامت‌دار ۳۲ بیتی هستند.)

در تنها سطر خروجی، مقدار واقعی نت‌های آهنگ را از چپ به راست با یک فاصله از هم بنویسید. برای نت‌هایی که مقدار واقعی‌شان قابل محاسبه نیست از 0?، 1?، 2? و … استفاده کنید. برای نت‌های نامعینی که لزوما با هم برابرند از $i$? های یکسان استفاده کنید. خروجی باید از نظر الفبایی کوچک‌ترین باشد.

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

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