Задачі
Велика стіна
Велика стіна
У короля Людовика двоє синів. Вони ненавидять один одного, і король побоюється, що після його смерті країна буде знищена страшними війнами. Тому Людовик вирішив розділити свою країну на дві частини, у кожній з яких буде володарювати один з його синів. Він посадив їх на трон у міста \textbf{A} та \textbf{B}, і хоче побудувати мінімально можливу кількість фрагментів стіни таким чином, щоб не існувало шляху з міста \textbf{A} і місто \textbf{B}.
Країну, у якій володарює Людовик, можна спрощено уявити у вигляді прямокутника \textbf{m}×\textbf{n}. У деяких клітинках цього прямокутника розміщені гори, по іншим же можна вільно переміщуватись. Крім того, ландшафт у деяких клітинках зручний для будівництва стіни, у інших же будівництво неможливо.
При поїздках по країні можна переміщуватись із клітинки у сусідню по стороні, лише якщо жодна з цих клітинок не містить гори або збудованого фрагмента стіни.
\InputFile
У першому рядку вхідного файлу містяться числа \textbf{m} і \textbf{n} (\textbf{1} ≤ \textbf{m}, \textbf{n} ≤ \textbf{50}). У другому рядку задано числа \textbf{k} і \textbf{l}, де \textbf{0} ≤ \textbf{k}, \textbf{l}, \textbf{k + l} ≤ \textbf{m}·\textbf{n}-\textbf{2}, \textbf{k} -- кількість клітинок, на яких розміщено гори, а \textbf{l} -- кількість клітинок, на яких можна будувати стеіу. Звичайно, що у горах будувати стіну неможна. Наступні \textbf{k} рядків містять координати клітинок з горами \textbf{x_i} і \textbf{y_i}, а за ними йде \textbf{l} рядків, які містять координати клітинок, на яких можна побудувати стіну -- \textbf{x_j} и \textbf{y_j}. Останні два рядки містять координати міст \textbf{A} (\textbf{x_A} і \textbf{y_A}) та \textbf{B} (\textbf{x_B} і \textbf{y_B}) відповідно. Серед клітинок, описаних у цих \textbf{k+l+2} рядках, немає двох співпадаючих. Гарантується, що \textbf{1} ≤ \textbf{x_i}, \textbf{x_j}, \textbf{x_A}, \textbf{x_B}_\{ \}≤ \textbf{m} і \textbf{1} ≤ \textbf{y_i}, \textbf{y_j}, \textbf{y_A}, \textbf{y_B}_\{ \}≤ \textbf{n}.
\OutputFile
У першому рядку вихідного файлу повинно бути виведена мінімальна кількість фрагментів стіни \textbf{F}, які необхідно побудувати. У наступних \textbf{F} рядках необхідно вивести один з можливих варіантів забудови.
Якщо неможлив здійснити потрібну забудову, то необхідно вивести у вихідний файл єдине число \textbf{-1}.
Вхідні дані #1
5 5 3 8 3 2 2 4 3 4 3 1 1 3 2 3 3 3 4 3 5 3 1 4 1 5 2 1 5 5
Вихідні дані #1
3 1 3 2 3 3 1