Замки і ключі
Володар лабіринту знаходиться у системі з V кімнат і V - 1 дверей. Кожні двері з'єднують пару кімнат в обох напрямках. Відомо, що між будь-якими двома кімнатами завжди існує шлях, що проходить через певну послідовність дверей. Також є C замків і C ключів C різних кольорів (кожен ключ має свій колір) від дверей, що з'єднують кімнати в лабіринті; кожні двері мають не більше одного замка, і в кожній кімнаті знаходиться не більше одного ключа. Володарю не складає труднощів пройти через систему замків, але проблема в тому, що він забув свою чарівну книгу, без якої його магія не діє. Наразі володар знаходиться в кімнаті X, і він хоче дістатися до своєї чарівної книги, яка знаходиться в кімнаті Y, за найкоротший час. На кожному кроці володар може пройти в сусідню кімнату через двері. Звісно, якщо двері на замку, то у нього повинен бути ключ того ж кольору, що й замок (якщо раптом до цього ці двері вже не були відкриті). Володар може нести з собою лише один ключ. Після того як володар підбере ключ, він не може його залишити десь у лабіринті, щоб потім його знову взяти. Як тільки двері стають відкритими, ключ викидається, оскільки він більше не потрібен.
За заданим лабіринтом і положеннями C ключів і C замків, визначте, як дістатися до Y з X, якщо це можливо. Будь-який шлях, довжина якого не більше 4^{ . }(C + 1)^{ . }V, є допустимим.
Вхідні дані
Перша рядок кожного тесту містить чотири цілих числа: кількість кімнат V (1 ≤ V ≤ 1500) в лабіринті, кількість замків C (0 ≤ C < V), і номери кімнат X і Y. Кімнати пронумеровані числами 0, 1,..., V - 1. Далі йде (можливо порожній) рядок з C цілих чисел, що описують місцезнаходження кожного ключа, в порядку зростання кольорів. Наступні V - 1 рядків описують лабіринт: кожен рядок містить три цілі числа A B L, що позначають той факт, що між кімнатами A і B є двері, які відкриваються ключем кольору L, якщо 0 ≤ L < C; значення -1 для L означає, що двері не містять замка.
Останній рядок містить V, C, X, Y = 0, 0, 0, 0 і не обробляється.
Вихідні дані
Вихідні дані для кожного тесту слід виводити в окремому рядку. Якщо рішення не існує, вивести "Impossible". Інакше слід вивести весь шлях у форматі L: V_0,...,V_L, де L ≤ 4(C + 1)V довжина шляху від X до Y, а X = V_0, V_1,..., V_L_{-1}, V_L = Y послідовність з L + 1 вершин, відвідуваних у зазначеному порядку. Перед кожною вершиною у виведеному шляху слід друкувати один пробіл.