Задача C. Йою Ньерк ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Смон Джит впервые приехал в Йою Ньерк. Именно по этой причине он плохо ориентируется в этом огромном городе.

Устройство дорог города весьма просто. Дороги города состоят из n улиц, идущих с востока на запад, и m авеню, простирающихся с севера на юг. Все улицы занумерованы числами от 1 до n, начиная с самой северной улицы. Аналогичным образом, начиная с самой западной, пронумерованы авеню. Все расстояния между соседними улицами и авеню совпадают. Все улицы и авеню являются односторонними.

У Смона есть карта, в которой указаны направления всех дорог города. Смон знает, что сейчас он находится на пересечении a-ой авеню и s-ой улицы. Он очень хочет попасть на своем автомобиле на перекресток b-ой авеню и t-ой улицы. Помогите ему найти лучший маршрут.

Маршрут — это описание пути по которому необходимо двигаться Смону. Это описание состоит из набора целых чисел c_i, которые означают, что от первого перекрестка до первого поворота необходимо проехать c₁ кварталов, затем повернуть и ехать c₂ кварталов до следующего поворота и т.д. Последнее число в описании маршрута соответствует расстоянию от последнего поворота до конечной точки пути. Длиной маршрута считается длина пути, который ему соответствует.

Смон Джит считает, что короткие маршруты лучше длинных. Среди маршрутов одинаковой длины, Смон считает, что маршруты с меньшим числом поворотов лучше. А среди маршрутов одинаковой длины и с одинаковым числом поворотов, Смон считает лучше маршруты, в которых минимальное c_i максимально. Оставшиеся маршруты Смон считает равноценными.

Решения, работающие в случае, если все авеню направлены с севера на юг, а все улицы направлены с запада на восток, будут оцениваться из 30 баллов.

Решения, работающие в случае, если все авеню направлены с севера на юг, будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла содержит два целых числа n и m (1 ≤ n, m ≤ 1000) — число улиц и авеню в Йою Ньерке. В следующей строке записаны n целых чисел, задающих направление улиц. Число на i-ой позиции соответствует направлению i-ой улицы. Значение 1 соответствует тому, что по улице разрешено движение с запада на восток, значение −1 — с востока на запад. В следующей строке аналогичным образом заданы направления авеню, при этом 1 соответствует движению с севера на юг.

Последние две строки входного файла содержат по два целых числа s, a, и t, b, соответственно (1 ≤ s, t ≤ n; 1 ≤ a, b ≤ m). Гарантируется, что начальная и конечная позиции не совпадают.

Формат выходного файла

Если доехать до конечной точки невозможно, то выведите в выходной файл единственное слово "Impossible". Иначе, в выходной файл выведите лучший маршрут. В первой строке выведите "Street", если движение в начале пути необходимо начинать по улице, или "Avenue", если по авеню. Во второй строке выведите k — количество чисел в описании пути, а в третьей строке k целых чисел — описание маршрута. Если ответов несколько, выведите любой.

Примеры тестов

3 2
1 -1 -1
-1 1
3 1
3 2

Avenue
3
2 1 2 

3 2
-1 -1 -1
-1 1
3 1
3 2

Impossible