Задача Z7. Межвселенский коллапс ≡

Условие

Рик и Морти в ходе своих путешествий по вселенным нарушили парочку правил и теперь за головой Рика охотится k версий Рика из альтернативных вселенных. Они объединились и договорились разойтись по разным маршрутам из измерения s, откуда сбежал оригинальный Рик, в измерение t, где он потерял своего Морти, стараясь двигаться по попарно непересекающимся (измерения могут повторяться, но их очередность - нет) путям.

Рик тоже пытается добраться из s в t, но он хочет избежать встречи с остальными версиями себя в пространстве между измерениями. Получится ли у него это сделать, если между измерениями можно передвигаться только по определённому правилу?

Считается, что Рик может спрятаться, если находится в одном и том же измерении с врагом. Однако, он не может остаться незамеченным, если совершает перемещение из измерения x в измерение y, при условии, что хотя бы один другой Рик тоже перемещается из x именно в y. Выбор путей альтернативных Риков заранее неизвестен.

Рик обязательно найдет путь, не пересекающийся с путями его врагов, если такой путь существует. Осталось понять существует ли k+1 непересекающихся по пространствам между измерениями путей. Также Рик провалится, если пути из s в t не существует вовсе - Морти погибнет, а Рик сдастся в плен.

Формат входных данных

В первой строке записано натуральное число n - количество бит в двоичном представлении измерения.

Во второй строке указаны натуральные числа s и t - начальное и конечное измерения.

В третьей строке записано число k - количество альтернативных Риков.

Далее следуют n строк, задающих правило перемещения между измерениями x и y. Каждая строка описывает операцию, результатом которой является один бит. Операции применяются по порядку: первая строка - к младшим битам чисел, вторая - к следующим и т.д.

Возможные операции над i-ыми битами чисел x и y:

• x - i-й бит результата равен i-ому биту числа x
• ~x - i-й бит результата противоположен i-му биту числа x
• y - i-й бит результата равен i-ому биту числа y
• ~y - i-й бит результата противоположен i-му биту числа y
• x & y - конъюнкция i-ых битов x_i, y_i (или их отрицаний, например x & ~y)
• x | y - дизъюнкция i-ых битов x_i, y_i (или их отрицаний)
• x ^ y - исключающее ИЛИ i-ых битов x_i, y_i (или их отрицаний)
• 0 - i-й бит результата тождественно равен нулю
• 1 - i-й бит результата тождественно равен единице

Результирующие n бит складываются (подсчитывается количество единиц) и сравниваются с числом p, указанным после описания операций. Если сумма меньше p, перемещение из x в y невозможно. Иначе между измерениями можно открыть портал.

Пояснение к примеру 1

Измерения кодируются 3-битными числами (от 0 до 7). Рик стартует в 0 (000) и должен попасть в 7 (111).

Операции по битам:

• 1-й бит: x ^ y
• 2-й бит: x ^ y
• 3-й бит: 1

Третий бит результата всегда равен 1, первые два - равны 1, если соответствующие биты x и y различаются. Портал открывается, если сумма битов ≥ p = 2.

Например, для ребра 0 → 7: 000 и 111 дают биты (1, 1, 1), сумма = 3 ≥ 2 - портал существует.

Рассмотрим подробнее, как применяется правило операций к отдельным битам на примере ребра 0 → 1.

x = 0 = 000
y = 1 = 001

1-й бит: x₀ ^ y₀ = 0 ^ 1 = 1
2-й бит: x₁ ^ y₁ = 0 ^ 0 = 0
3-й бит: 1

Сумма битов = 1 + 0 + 1 = 2 ≥ p

Так как сумма не меньше p = 2, портал между измерениями 0 и 1 существует.

Аналогично существуют портал 1 → 7, поэтому возможен путь 0 → 1 → 7.

Всего имеется как минимум три рёберно-непересекающихся пути (0→7, 0→1→7, 0→2→7), а альтернативных Риков k = 2. Рик может выбрать свободный маршрут.

Ответ: Yes

Пояснение к примеру 2

Здесь измерения - 2-битные числа. Рик идёт из 0 (00) в 3 (11).

• 1-й бит результата = первый бит x
• 2-й бит результата = 0

Порог p = 1, поэтому портал возможен только если старший бит x равен 1.

У стартового измерения 0 (00) старший бит равен 0, следовательно, из него невозможно открыть ни одного портала.

Путь из s в t отсутствует.

Ответ: No

Формат выходных данных

Вывести Yes, если Рику возможно незамеченным перейти из s в t.

Вывести No, если это невозможно.

Ограничения

1 ≤ n ≤ 30
0 ≤ s, t ≤ 2^n − 1
0 ≤ k ≤ 2^n − 1
0 ≤ p ≤ n

Примеры тестов

3
0 7
2
x ^ y
x ^ y
1
2

Yes

2
0 3
1
x
0
1

No