Открытие сверхсветовых нейтрино вызвало к жизни целую цепочку научных достижений. Сначала учёным удалось разогнать до сверхсветовых скоростей отдельные протоны и нейтроны, затем — целые атомы, а вскоре и небольшие объекты. Но самым удивительным эффектом стало то, что при попытке разогнать какой-нибудь предмет до сверхсветовой скорости вдоль замкнутой траектории тот просто отправлялся в прошлое. Причём схема такого ускорителя оказалась настолько проста, что даже обычная микроволновка после небольшой доработки смогла отправить неспелый банан на неделю назад, чтобы тот дозрел.

Хотя эксперименты по отправке объектов в прошлое и дали отличные результаты, они не всегда проходили гладко. Порой предмет, отправленный назад во времени, сталкивался со своей версией из прошлого. После одного такого столкновения образовалась чёрная дыра, которая, прежде чем схлопнуться, успела поглотить половину исследовательской лаборатории. Несмотря на подобные инциденты, учёные продолжали работы по стабильному перемещению всё больших объектов. Вскоре в массовое производство был запущен транспортный корабль «Валькирия-500». Сверхсветовое перемещение позволяло ему прилетать в точку назначения в любой момент времени, даже в предшествовавший моменту отлёта.

Разведка доложила, что на одну из отдалённых планет прибывает с визитом лидер повстанческого движения. Вам, как самому талантливому спецагенту, дан приказ уничтожить его прямо в момент прибытия, пока на него не набросилась жадная до сенсаций пресса. У вас есть график всех рейсов «Валькирий» в этом секторе Галактики и право воспользоваться любыми из них. Но помните, что, если вы дважды окажетесь на одной и той же планете в одно и то же время, вы рискуете столкнуться с самим собой. Поскольку подобная встреча наверняка окажется фатальной, её нельзя допускать, пока задание не выполнено.

В первой строке записаны целые числа n и m — общее количество планет в секторе и рейсов «Валькирий» между ними (1 ≤ n ≤ 10⁵; 0 ≤ m ≤ 10⁵). В следующих m строках описываются рейсы. Описание каждого рейса состоит из четырёх целых чисел: номеров планет вылета и прилёта, времени вылета и времени прилёта. В последней строке записаны четыре целых числа — номер планеты, где вы находитесь, номер планеты, на которую прилетает лидер повстанцев, текущее время и время, когда прилетает лидер повстанцев. Все времена — целые числа в пределах от 0 до 10⁶. Планеты пронумерованы целыми числами от 1 до n.

Если маршрута не существует, выведите «Impossible». В противном случае в первой строке выведите число k. В следующей строке выведите k чисел — номера рейсов, которыми стоит воспользоваться, в порядке следования по маршруту. Если существует несколько способов вовремя добраться до пункта назначения, выведите любой из них. Рейсы пронумерованы целыми числами от 1 до m в том порядке, в котором они описаны во входных данных.