Задача: Пешки
В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с \(N\) строками и \(M\) столбцами (\(1 \le N \le 100\), \(1 \le M \le 100\)) по следующим правилам. В нижней строке, имеющей номер 1, стоит \(P\) белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер \(N\) (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел достичь хотя бы одной пешкой самой верхней строки, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть.
Формат входных данных
Сначала вводятся четыре целых числа \(N\), \(M\), \(P\), \(K\) (\(1 \le N \le 100\), \(1 \le M \le 100\), \(0 \le P \le M\), \(1 \le K \le (N - 1)M\). Далее записано \(P\) различных чисел — номера столбцов \(p_j\) (\(1 \le p_j \le M\)), в которых стоят белые пешки. Далее идут \(K\) различных пар целых чисел — номера строк и столбцов чёрных фигур \(r_i\), \(c_i\) (\(2 \le r_i \le N\), \(1 \le c_i \le M\)).
Формат выходных данных
Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.
Ваш ответ: