Йою Ньєрк

Смон Джит вперше приїхав у Йою Ньєрк. Саме тому він погано орієнтується у цьому величезному місті.

Будова міських доріг досить проста. У місті $n$ вулиць, що йдуть зі сходу на захід, та $m$ авеню, що простягаються з півночі на південь. Усі вулиці пронумеровані від $1$ до $n$, починаючи з найпівнічнішої. Аналогічно, авеню пронумеровані, починаючи з найзахіднішої. Відстані між сусідніми вулицями та авеню однакові. Усі вулиці та авеню — односторонні.

Смон має карту з розміткою напрямків усіх міських доріг. Він знає, що зараз знаходиться на перехресті $a$-ї авеню та $s$-ї вулиці. Дуже хоче дістатися до своєї машини на перехресті $b$-ї авеню та $t$-ї вулиці. Допоможіть йому знайти найкращий маршрут.

Маршрут — це опис шляху, яким Смон має рухатися. Це послідовність цілих чисел c_i, які означають: від першого перехрестя до першого повороту потрібно проїхати c_1 кварталів, потім повернути і проїхати c_2 кварталів до наступного повороту, і так далі. Останнє число у маршруті відповідає відстані від останнього повороту до кінцевої точки шляху. Довжина маршруту — це довжина відповідного йому шляху. Смон Джит вважає кращими короткі маршрути. Серед маршрутів однакової довжини Смон віддає перевагу тим, у яких менше поворотів. Якщо довжина і кількість поворотів співпадають, Смон обирає той маршрут, у якому мінімальне c_i є найбільшим. Усі інші маршрути Смон вважає рівноцінними.