У короля Людовика двое сыновей. Они ненавидят друг друга, и король боится, что после его смерти страна будет уничтожена страшными войнами. Поэтому Людовик решил разделить свою страну на две части, в каждой из которых будет властвовать один из его сыновей. Он посадил их на трон в города A и B, и хочет построить минимально возможное количество фрагментов стены таким образом, чтобы не существовало пути из города A в город B.
Страну, в которой властвует Людовик, можно упрощенно представить в виде прямоугольника m×n. В некоторых клетках этого прямоугольника расположены горы, по остальным же можно свободно перемещаться. Кроме этого, ландшафт в некоторых клетках удобен для строительства стены, в остальных же строительство невозможно.
При поездках по стране можно перемещаться из клетки в соседнюю по стороне, только если ни одна из этих клеток не содержит горы или построенного фрагмента стены.
В первой строке входного файла содержатся числа m и n (1 ≤ m, n ≤ 50). Во второй строке заданы числа k и l, где 0 ≤ k, l, k + l ≤ m·n-2, k – количество клеток, на которых расположены горы, а l – количество клеток, на которых можно строить стену. Естественно, что на горах строить стену нельзя. Следующие k строк содержат координаты клеток с горами x_i и y_i, а за ними следуют l строк, содержащие координаты клеток, на которых можно построить стену – x_j и y_j. Последние две строки содержат координаты городов A (x_A и y_A) и B (x_B и y_B) соответственно. Среди клеток, описанных в этих k+l+2 строках, нет двух совпадающих. Гарантируется, что 1 ≤ x_i, x_j, x_A, x_B_{ }≤ m и 1 ≤ y_i, y_j, y_A, y_B_{ }≤ n.
В первой строке выходного файла должно быть выведено минимальное количество фрагментов стены F, которые необходимо построить. В последующих F строках необходимо вывести один из возможных вариантов застройки.
Если невозможно произвести требуемую застройку, то необходимо вывести в выходной файл единственное число -1.