Ученый с мировым именем Иннокентий продолжает свои инновационные эксперименты с колодами карт. Теперь у него есть колода из n карт и k шаффл-машин для перемешивания этой колоды. Как мы знаем, i-ая шаффл-машина характеризуется своими собственными числами pi, 1, pi, 2, ..., pi, n, такими, что если положить в нее n карт, занумерованных по порядку 1, 2, ..., n, и нажать на машине кнопку, то карты будут перемешаны таким образом, что образуется колода pi, 1, pi, 2, ..., pi, n, где числа pi, 1, pi, 2, ..., pi, n — это те же номера карт, но переставленные в некотором порядке шаффл-машиной.
В начале эксперимента карты в колоде располагаются в порядке a1, a2, ..., an, т.е. на первом месте находится карта с номером a1, на втором — карта с номером a2, и т.д. Ученый хочет сделать так, чтобы карта с номером x была на первом месте. Он может использовать все свои шаффл-машины столько раз, сколько ему захочется. Выясните, получится ли у него добиться желаемого результата.
В первой строке записано единственное натуральное число n — количество карт в колоде Иннокентия.
Во второй строке записаны n различных натуральных чисел a1, a2, ..., an (1 ≤ ai ≤ n) — первоначальное расположение карт в колоде.
В третьей строке записано единственное натуральное число k — количество шаффл-машин, имеющихся у ученого.
В каждой из следующих k строк записаны n различных натуральных чисел pi, 1, pi, 2, ..., pi, n (1 ≤ pi, j ≤ n), характеризующих соответствующие шаффл-машины.
В последней строке записано единственное натуральное число x (1 ≤ x ≤ n) — номер карты, которую Иннокентий желает видеть на первом месте в колоде.
Числа n и k удовлетворяют соотношению 1 ≤ n·k ≤ 200000.
Выведите «YES», если ученый сможет добиться того, чтобы карта с номером x встала на первое место, и «NO» иначе.
4
4 3 2 1
2
1 2 4 3
2 3 1 4
1
YES
4
4 3 2 1
2
1 2 4 3
2 1 3 4
1
NO