A. Горная задача
ограничение по времени на тест
5 секунд (13 секунд для Java)
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Порядком устав от соревнований по программированию и решения алгоритмических задач, Аркадий решил взять небольшую паузу и кардинально сменить род деятельности. Нашего героя всегда тянуло в горы, поэтому, используя заработанные на различных соревнованиях призовые деньги, он прикупил себе небольшой горнолыжный курорт и занялся его подготовкой к зимнему сезону.

Единственная имеющаяся трасса состоит из n контрольных пунктов, пронумерованных от 1 до n. Контрольный пункт i находится на высоте hi, причём никакие два пункта не находятся на одной высоте. Поскольку на трассе только один подъёмник, то спуск всегда начинается в контрольном пункте номер s и заканчивается в контрольном пункте номер t. Некоторые m пар контрольных пунктов соединены участками трассы, которые ведут от более высокого контрольного пункта к более низкому.

Привлекательность участка трассы, непосредственно соединяющего контрольный пункт u с контрольным пунктом v, равна разности высот пунктов, то есть hu - hv. При этом привлекательностью маршрута, последовательно посещающего контрольные пункты v1, v2, ..., vk, называется минимальная из привлекательностей его участков, то есть минимум среди величин hv1 - hv2, hv2 - hv3, ..., hvk - hvk - 1.

Туристов, посещающих курорт Аркадия, с одной стороны волнует привлекательность маршрута, а с другой — его длина, которая определяется как количество участков трассы в маршруте. Поскольку Аркадий уже не силён в решении подобного рода задач, то именно вам придётся вычислить для каждой возможной длины маршрута x от 1 до n - 1 максимально возможную привлекательность маршрута из s в t, имеющего длину не менее x.

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

В первой строке входных данных записаны четыре целых числа n, m, s и t (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000, 1 ≤ s, t ≤ n, s ≠ t) — количество контрольных пунктов на трассе, количество участков трассы, номер стартового контрольного пункта и номер финишного контрольного пункта соответственно.

Во второй строке записаны n различных целых чисел h1, h2, ..., hn (0 ≤ hi ≤ 100 000) — высоты, на которых расположены контрольные пункты.

Далее следуют m строк, описывающих участки трассы. В i-й из них записаны два числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), означающих, что i-й участок трассы идёт от контрольного пункта ui к контрольному пункту vi. Гарантируется, что никакие два участка трассы не соединяют напрямую одну и ту же пару контрольных пунктов, что высота контрольного пункта ui больше высоты контрольного пункта vi, и что существует хотя бы один маршрут от контрольного пункта s до контрольного пункта t.

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

Выведите n - 1 чисел по одному в строке, i-е из которых должно равняться максимально возможной привлекательности маршрута из s в t, имеющего длину не меньше i. Если для некоторого i не существует маршрута длиной не меньше i, то выведите в соответствующей строке  - 1.

Примеры
Входные данные
4 4 2 4
3 4 2 1
2 4
2 1
1 3
3 4
Выходные данные
3
1
1
Входные данные
3 2 1 3
3 2 1
1 2
1 3
Выходные данные
2
-1
Входные данные
5 10 1 5
8 6 4 3 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Выходные данные
7
3
2
1
Примечание

В первом примере существует прямой участок трассы из стартового контрольного пункта в конечный. Привлекательность такого маршрута равна 3, а длина 1. Также существует путь длины 3, проходящий через контрольные пункты 2, 1, 3 и 4, c привлекательностью равной 1. Для x = 2 ответом будет являться данный путь длины 3, поскольку это самый привлекательный путь длиной не менее 2.