eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Йою Ньерк

Йою Ньерк

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

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

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

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

prb5505

Маршрут - это описание пути по которому необходимо двигаться Смону. Это описание состоит из набора целых чисел c[i], которые означают, что от первого перекрестка до первого поворота необходимо проехать c[1]кварталов, затем повернуть и ехать c[2] кварталов до следующего поворота и т.д. Последнее число в описании маршрута соответствует расстоянию от последнего поворота до конечной точки пути. Длиной маршрута считается длина пути, который ему соответствует. Смон Джит считает, что короткие маршруты лучше длинных. Среди маршрутов одинаковой длины, Смон считает, что маршруты с меньшим числом поворотов лучше. А среди маршрутов одинаковой длины и с одинаковым числом поворотов, Смон считает лучше маршруты, в которых минимальное c[i] максимально. Оставшиеся маршруты Смон считает равноценными.

Входные данные

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

Последние две строки содержат по два целых числа s, a и t, b соответственно (1s, tn, 1a, bm). Гарантируется, что начальная и конечная позиции не совпадают.

Выходные данные

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

Пример

Входные данные #1
3 2
1 -1 -1
-1 1
3 1
3 2
Выходные данные #1
Avenue
3
2 1 2
Входные данные #2
3 2
-1 -1 -1
-1 1
3 1
3 2
Выходные данные #2
Impossible
Источник 2011 Цикл Интернет-олимпиад для школьников, Восьмая индивидуальная олимпиада, 27 марта, Задача C