Зимы в Берляндии снежные, и нынешняя зима не исключение. Каждую зиму правительство страны решает задачу чистки дорог от снега. И эта задача особенно сложна для столицы. Можно считать, что столица Берляндии состоит из \textbf{n} перекрестков и \textbf{m} односторонних дорог. Каждая дорога соединяет два различных перекрестка \textbf{x_i}, \textbf{y_i} и направлена от \textbf{x_i} к \textbf{y_i}. На \textbf{i}-ой дороге лежит \textbf{w_i} тонн снега. Для чистки дорог правительство наняло частную компанию "\textit{Snow White}". Каждый день компания высылает одну снегоуборочную машину. Она начинает работу на перекрестке с номером \textbf{A}, проходит несколько перекрестков до \textbf{B}-го и останавливается. Путь машины может содержать повторяющиеся дороги и перекрестки, включая \textbf{A} и \textbf{B}. Грузовик за день проделывает путь от перекрестка \textbf{A} до перекрестка \textbf{B}, водитель, конечно, не нарушает правила дорожного движения. Каждый проход машины по дороге со снегом уменьшает количество снега на ней на \textbf{1} тонну. Так как жители столицы могут уличить правительство в бесцельном растрачивании бюджета, водитель запрещено вести машину по дороге, на которой нет снега. Некоторые городские дороги представляют историческую ценность, потому что на них стоят правительственные здания. Поэтому по завершении работы компании "\textit{Snow White}" эти дороги должны быть свободны от снега. Известно, что на перекрестке \textbf{A} находится исторический центр столицы, что означает пешую досягаемость всех исторических дорог из центра по историческим дорогам. Помните, что с точки зрения пешехода дороги являются двусторонними. Правительство платит компании за каждый день работы, поэтому руководство "\textit{Snow White}" заинтересовано в том, чтобы растянуть работу на наибольшее количество дней. Ваша задача --- найти последовательность маршрутов из \textbf{A} в \textbf{B}, удовлетворяющих ограничениям: ограничение направления движения, чистота исторически значимых дорог, максимальное количество рабочих дней. \InputFile Первая строка содержит целые числа \textbf{n}, \textbf{m}, \textbf{A}, \textbf{B} (\textbf{2} ≤ \textbf{n} ≤ \textbf{100}, \textbf{0} ≤ \textbf{m} ≤ \textbf{5000}, \textbf{1} ≤ \textbf{A}, \textbf{B} ≤ \textbf{n}, \textbf{A} ≠ \textbf{B}), где \textbf{n} --- число перекрестков в столице Берляндии, \textbf{m} --- число дорог. Следующие \textbf{m} строк содержат по четыре числа \textbf{x_i}, \textbf{y_i}, \textbf{w_i}, \textbf{t_i}(\textbf{1} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{n}, \textbf{x_i} ≠ \textbf{y_i}, \textbf{0} ≤ \textbf{w_i} ≤ \textbf{100}, \textbf{0} ≤ \textbf{t_i} ≤ \textbf{1}), где \textbf{x_i}, \textbf{y_i} --- концы дороги, \textbf{w_i} --- количество снега на ней, \textbf{t_i} --- тип дороги (\textbf{0} означает, что дорога обычная, \textbf{1} --- историческая). Между парой перекрестков может быть не более одной дороги в каждом направлении. \OutputFile Выведите \textbf{p} --- максимальное количество рабочих дней. Следующие \textbf{p} строк должны содержать описания ежедневных маршрутов снегоуборочной машины. Маршрут выводите как список номеров перекрестков, начинающийся с \textbf{A}, заканчивающийся в \textbf{B}, разделенных пробелом. Если есть несколько решений, выведите любое, если решения нет, выведите \textbf{0}.