“我们尝试过单独监禁、水刑和听Just In Beaver,但都没有效果。我们需要一些极端的东西。”
“小阿莱娜得到了一个数组作为生日礼物……”
长度为 n 的数组 b 是使用以下过程从长度为 n 的数组 a 和两个整数 l 和 r (l ≤ r) 获得的:
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),符合上述要求。
如果有多个解,则输出其中任意一个。
保证答案存在。
示例
输入 #1
5 1 2 3 4 5 00001
输出 #1
6 15
输入 #2
10 -10 -9 -8 -7 -6 6 7 8 9 10 0000111110
输出 #2
-5 5
注意
在第一个测试用例中,任何一对 l 和 r 对都是有效的,如果 6 ≤ l ≤ r ≤ 109,在这种情况下 b5 = 1,因为 a1, ..., a5 < l。