Зачароване кладовище#1256
Сьогодні Хелловін, і Наляканий Джон разом із друзями вирішили зробити щось веселе з цієї нагоди: перейти через кладовище. Хоча Наляканий Джон зовсім не вважає це веселим, зрештою він погодився приєднатися до їхньої пригоди. Опинившись біля входу, друзі почали перетинати кладовище по одному, і тепер настав час Джона. Він досі пам'ятає казки, які бабуся розповідала йому в дитинстві. Вона казала, що в ніч Хелловіну на кладовищі з'являються "містичні діри". Це не звичайні діри — вони переносять тих, хто у них впаде, в іншу точку кладовища, можливо дуже далеко. Але найстрашніше в цих дірах те, що вони дозволяють мандрувати не лише у просторі, а й у часі; тобто, якщо ти потрапиш у "містичну діру", з'явишся десь у кладовищі, причому раніше (або пізніше), ніж ти туди зайшов, у паралельному світі, в усьому іншому ідентичному нашому.
Кладовище організоване у вигляді ґратки з W \times H клітинок, при цьому вхід знаходиться у клітинці з координатами , а вихід — у (W - 1, H - 1). Незважаючи на темряву, Наляканий Джон завжди може впізнати вихід і одразу ж піде, як тільки дістанеться до нього, вирішивши більше ніколи не ступати у це кладовище. По дорозі до виходу він може рухатися з однієї клітинки до сусідньої, і може рухатися лише на північ, схід, південь або захід. У кожній клітинці може бути або один надгробок, або одна "містична діра", або трава:
- Якщо у клітинці надгробок, йти через неї не можна, оскільки надгробки занадто високі, щоб їх перелазити.
- Якщо у клітинці "містична діра" і ти проходиш через неї, ти з'явишся десь у кладовищі, можливо, в інший момент часу. Часова різниця залежить від конкретної "містичної діри", у яку ти потрапиш, і вона може бути як додатною, так і від'ємною, або ж рівною нулю.
- В іншому випадку клітинка вкрита травою, і ти можеш вільно по ній йти.
Він дуже наляканий, тож хоче дістатися до виходу якомога швидше. Саме тому він подзвонив вам, відомому програмісту. Він хоче, щоб ви написали програму, яка за описом кладовища обчислить мінімальний час, необхідний для переходу від входу до виходу. Наляканий Джон готовий користуватися "містичними дірами", якщо це допоможе йому швидше перейти кладовище, але він до смерті боїться можливості загубитися й подорожувати назад у часі безкінечно по дірах, тому ваша програма повинна повідомляти й про такі ситуації.
На малюнку зображено можливе кладовище (другий приклад із вхідних даних). У цьому випадку є два надгробки у клітинках і , і "містична діра" з клітинки у клітинку з різницею у часі секунд. Мінімальний час перетнути кладовище: секунди, маршрут:
(0, 0) \rightarrow схід сек (1, 0) \rightarrow схід сек (2, 0) \rightarrow схід сек (3, 0) \rightarrow діра сек (2, 2) \rightarrow схід сек
Без використання "містичної діри" потрібно щонайменше секунд.
Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілих числа та (1 \leq W, H \leq 30). Ці числа означають ширину та висоту кладовища. Наступний рядок містить число (G \geq 0) — кількість надгробків на кладовищі, після чого слідує рядків з позиціями цих надгробків. Кожна позиція задається двома цілими числами та (0 \leq X < W, 0 \leq Y < H).
Далі у рядку задано число (E \geq 0) — кількість "містичних дір", а за ним рядків. Кожен з них містить п'ять цілих чисел X_1, Y_1, X_2, Y_2, T. (X_1, Y_1) — позиція "містичної діри" (0 \leq X_1 < W, 0 \leq Y_1 < H). (X_2, Y_2) — позиція, куди веде "містична діра" (0 \leq X_2 < W, 0 \leq Y_2 < H). Зауважте, що початкова і кінцева позиції "містичної діри" можуть збігатися. (-10\ 000 \leq T \leq 10\ 000) — це різниця в секундах між моментом падіння у "містичну діру" і моментом появи у кінцевій позиції; додатне число означає, що ти дістанешся туди після потрапляння у діру. Ви можете бути впевнені, що немає двох "містичних дір" із однаковим початком, а кінцева позиція "діри" не містить надгробка. Також ні у , ні у (W-1, H-1) немає ані надгробків, ані "містичних дір".
Введення закінчується рядком , який не слід обробляти.
Для кожного тестового випадку, якщо для Наляканого Джона існує можливість мандрувати у часі нескінченно, виведіть Never. Інакше виведіть мінімальний час у секундах, за який він зможе пройти кладовище від входу до виходу, якщо це можливо, і Impossible — якщо ні.
Приклад 1