Гриби
Маша вирішила провідати свою бабусю. Вона взяла з собою дві корзинки - одну з пиріжками, а другу - порожню, для грибів, які вона хоче зібрати по дорозі.
Для того, щоб потрапити до бабусі, Маші необхідно пройти через ліс, який являє собою прямокутник розміром m×n, у деяких клітинках якого ростуть дерева, а у деяких - гриби. Маша виходить з клітинки (1, 1) і йде до бабусі у село, розміщене у клітинці (m, n). Кожним своїм ходом Маша може пійти праворуч або вниз (тобто збільшить одну і лише одну зі своїх координат на 1), якщо у клітинці, у якій вона після цього опиниться, не стоїть дерево. Якщо в обох клітинках і праворуч, і внизу, знаходяться дерева, то вважається. що Маша заблукала.
Вам необхідно за заданим лісом вияснити, чи може Маша дійти до бабусі, не заблукавши, і якщо зможе, то порахувати максимальну кількість грибів, які вона зможе при цьому зібрати.
Вхідні дані
У першому рядку вхідного файлу знаходяться чотири числа m, n, g, t (2 ≤ m, n≤100, 0≤g, t≤g+t≤mn-2). У наступних g рядках розміщено по 2 числа у кожному - x та y-координати i-го гриба. За ними йде t рядків з описами дерев у аналогічному форматі. Ні у якій клітинці не може рости більше одного гриба, гриб та дерево одночасно, чи більше одного дерева. Крім того, у клітинках (1, 1) та (m, n) нічого не росте.
Вихідні дані
Якщо Маша може дійти до бабусі, то у першому рядку вихідного файлу необхідно вивести максимальну кількість грибів, які вона зможе при цьому зібрати, а у наступних m+n-1 рядках потрібно видати координати клітинок, послідовно відвіданих Машею у форматі x[i]y[i], для шляху, на якому досягаєтся максимальна кількість грибів. Якщо таких шляхів декілька, необхідно вивести той, який спускається вниз.
У протилежному випадку у вихідний файл повинно бути виведено єдине число -1.