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

محصول رنگ نشده که آماده شده در یک نقطه مشخصی است (نقطه منبع ) و باید به نقطه داده شده دیگر(مقصد) بعد از نقاشی شدن توسط رنگ‌های مختلف به ترتیب داده شده تحویل داده بشود. تعدادی تونل وجود دارد، فرض می‌کنیم هر تونلی یک خط بین دو بازه در نقشه با رنگ مشخص است رنگ‌های هر تونل لزوما مختلف نیستند حالا فرض کنیم:$<C_1,C_2,...,C_n>$ یک رشته ای از$N$ رنگ باشد یک محصول قرار است با آن رنگ شود، محصول حتما باید از تونل های $<T_1,T_2,…T_n>$ به صورتی که رنگ $T_i=C_i$ است عبور کند. این نیز ذکر می‌شود که امکان دارد از یک تونل بدون رنگ شدن رد شود. حالا این $<T_1,T_2,..T_n>$ شاید در حقیقت یک زیر محجموعه‌ای از همه تونل‌ها باشند به صورتی که محصول از آن‌ها می‌گذرد. مسیری که محصول از تونل می‌گذرد مهم نیست هدف این است که کوتاه‌ترین مسیر از مبدا به مقصد محصول به رنگ های محدود شده پیدا شود. مسیر ممکن است از خودش یا حتی از یک تونل بگذرد و همین‌طور دوبار گذشتن از یک تونل مجاز است. باید ذکر شود که دوتا تونل می‌توانند بگذرند یا همپوشانی کنند ولی باید مختلف باشند .

فایل وردودی شامل چند تست‌کیس است خط اول ورودی شامل یک عدد صحیح $T$ (بین یک تا بیست ) که تعداد تست‌کیس است. در ادامه خط اول یک سری داده برای $T$ تست‌کیس وجود دارد. خط اول هر تست کیس شامل چهار عدد حقیقی $X_s,Y_s,X_t,Y_t$ که $X,Y$ مختصات نقاط منبع و مقصد پشت سر هم هستند. خط دوم تست کیس‌ها شامل رنگ رشته هستند عدد اول تعداد رشته است بین یک تا سی و بقیه خط خود رشته هستند٬ هر رنگ این رشته شامل یک عدد بین یک تا صد است. سومین خط شامل یک عدد صحیح بین یک تا شصت است که تعداد تونل‌هاست. در آن خط که هر کدام شامل پنج عدد است٬ اولین و دومین عدد طول و عرض نقاط و سومین و چهارمین عدد طول و عرض مختصات نقطه دیگر هستند٬ مختصات اعدادی حقیقی هستند٬ پنمجمین عدد یک عدد صحیح بین یک تا صد است که رنگ تونل را مشخص می‌کند.

فایل خروجی باید $T$ خط داشته باشد که هر کدام شامل حداقل فاصله‌ی یک مسیر از منبع به مقصد محصول در مسئله است. جواب چاپ شده با جواب نهایی تا سه رقم اعشار مقایسه شده و باید برابر باشد.

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

• سوال بعد