#P929D. Пограничные врата

Пограничные врата

Cannot parse: NaNs error parsing time

Description

Герой Аркадий находится на узкой полоске земли, разделенной на n зон, пронумерованных от 1 до n. Из i-й зоны можно пройти лишь в (i - 1)-ю зону и в (i + 1)-ю зону, если они существуют. При этом между каждой парой соседних зон находятся пограничные врата, которые могут быть разных цветов, цвет врат между i-й и (i + 1)-й зоной равен gi.

Аркадий может пройти пограничные врата некоторого цвета, только если он перед этим побывал в одном из шатров хранителей ключей этого цвета и взял ключ. В каждой зоне находится ровно один шатер хранителя ключей некоторого цвета, цвет шатра в i-й зоне равен ki. После посещения шатра определенного цвета Аркадий может неограниченное число раз проходить через любые врата этого цвета.

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

Первая строка содержит три целых числа n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит n - 1 целое число g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100 000), где gi означает цвет пограничных врат между зонами i и i + 1.

Третья строка содержит n целых чисел k1, k2, ..., kn (1 ≤ ki ≤ 100 000), где ki означает цвет шатра хранителя ключей в i-й зоне.

Если Аркадий не может попасть из зоны a в зону b, не имея изначально ключей, выведите -1.

Иначе выведите минимальное количество ходов, которое потребуется Аркадию.

Input

Первая строка содержит три целых числа n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит n - 1 целое число g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100 000), где gi означает цвет пограничных врат между зонами i и i + 1.

Третья строка содержит n целых чисел k1, k2, ..., kn (1 ≤ ki ≤ 100 000), где ki означает цвет шатра хранителя ключей в i-й зоне.

Output

Если Аркадий не может попасть из зоны a в зону b, не имея изначально ключей, выведите -1.

Иначе выведите минимальное количество ходов, которое потребуется Аркадию.

Samples

5 4 1
3 1 1 2
7 1 2 1 3

7

5 1 5
4 3 2 1
4 3 2 5 5

-1

Note

В первом примере, чтобы попасть из зоны 4 в зону 1, Аркадию нужно сначала взять ключ цвета 1, пройти в зону 3, там взять ключ цвета 2 и пройти обратно в зону 4 и затем в зону 5, взять там ключ цвета 3 и дойти до зоны 1 за четыре хода.

Во втором примере Аркадий может дойти лишь до четвертой зоны, так как шатров хранителей ключей цвета 1 нет совсем.