D. Алена и обогреватель
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

"Мы пробовали одиночное заключение, утопление и прослушивание группы Just In Beaver, но безрезультатно. Нам нужно что-то экстремальное."

"Маленькой Алене подарили массив на день рождения..."

Пусть есть массив a длиной n и два числа l и r (l ≤ r). Тогда массив b имеет размер n и получается следующим образом:

b1 = b2 = b3 = b4 = 0.

Для всех 5 ≤ i ≤ n:

  • bi = 0 если ai, ai - 1, ai - 2, ai - 3, ai - 4 > r и bi - 1 = bi - 2 = bi - 3 = bi - 4 = 1
  • bi = 1 если ai, ai - 1, ai - 2, ai - 3, ai - 4 < l и bi - 1 = bi - 2 = bi - 3 = bi - 4 = 0
  • bi = bi - 1 иначе

Даны массивы a и b' одинакового размера. Найдите числа l и r (l ≤ r) такие, что применив описанный выше алгоритм, мы получим массив b, равный массиву b'.

Гарантируется, что ответ существует.

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

В первой строке задано целое число n (5 ≤ n ≤ 105) — размер массивов a и b'.

Во второй строке входных данных задаются n целых чисел a1, ..., an ( - 109 ≤ ai ≤ 109) — элементы массива a.

В третьей строке входных данных задается строка из n символов, состоящая из 0 и 1 — элементы массива b'. Обратите внимание, что они не разделены пробелами.

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

В единственной строке выведите два целых числа l и r ( - 109 ≤ l ≤ r ≤ 109), удовлетворяющие условиям, описанным выше.

Если подходящих пар значений несколько, выведите любую из них.

Гарантируется, что ответ существует.

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

В первом тестовом примере подходит любая пара l и r, где 6 ≤ l ≤ r ≤ 109, в таком случае b5 = 1, так как a1, ..., a5 < l.