Зачароване кладовище
Сьогодні ввечері Хелловін, і Наляканий Джон та його друзі вирішили зробити щось веселе, щоб відзначити цю подію: перетнути кладовище. Хоча Наляканий Джон зовсім не вважає це веселим, він нарешті погодився приєднатися до них у цій пригоді. Опинившись на вході, друзі почали перетинати кладовище один за одним, і тепер настав час для Наляканого Джона. Він досі пам’ятає казки, які розповідала йому бабуся, коли він був дитиною. Вона розповідала йому, що в ніч на Хелловін на кладовищі з’являються «зачаровані ями». Це не звичайні ями, але вони переносять людей, які в них потрапляють, у якусь точку на кладовищі, можливо, далеко. Але найстрашніша особливість цих ям полягає в тому, що вони дозволяють подорожувати в часі, а також у просторі; тобто, якщо ви потрапите в «зачаровану яму», ви з’явитеся десь на кладовищі в певний момент часу до (або після) того, як ви увійшли в яму, у паралельному всесвіті, інакше ідентичному нашому.
Кладовище організовано у вигляді сітки з W × H клітинок, з входом у клітинці на позиції (0, 0) і виходом у клітинці на позиції (W − 1, H − 1). Незважаючи на темряву, Наляканий Джон завжди може впізнати вихід, і він піде, як тільки досягне його, вирішивши більше ніколи не ступати на кладовище. На шляху до виходу він може йти з однієї клітинки в сусідню, і він може рухатися лише на північ, схід, південь або захід. У кожній клітинці може бути або один надгробок, або одна «зачарована яма», або трава:
• Якщо клітинка містить надгробок, ви не можете пройти по ньому, тому що надгробки занадто високі, щоб їх перелазити.
• Якщо клітинка містить «зачаровану яму» і ви йдете по ній, ви з’явитеся десь на кладовищі в можливо інший момент часу. Різниця в часі залежить від конкретної «зачарованої ями», в яку ви потрапили, і може бути позитивною, негативною або нульовою.
• В іншому випадку клітинка містить лише траву, і ви можете вільно ходити по ній.
Він наляканий, тому хоче перетнути кладовище якомога швидше. І саме тому він зателефонував вам, відомому програмісту. Він хоче, щоб ви написали програму, яка, враховуючи опис кладовища, обчислює мінімальний час, необхідний для переходу від входу до виходу. Наляканий Джон погоджується використовувати «зачаровані ями», якщо вони дозволяють йому швидше перетнути кладовище, але він до смерті боїться можливості загубитися і мати змогу подорожувати назад у часі нескінченно, використовуючи ями, тому ваша програма повинна повідомляти про ці ситуації.
На малюнку вище показано можливе кладовище (другий тестовий випадок із зразкового вводу). У цьому випадку є два надгробки в клітинках (2, 1) і (3, 1), і «зачарована яма» з клітинки (3, 0) до клітинки (2, 2) з різницею в часі 0 секунд. Мінімальний час для перетину кладовища становить 4 секунди, що відповідає шляху:
(0, 0) → Схід 1 сек (1, 0) → Схід 1 сек (2, 0) → Схід 1 сек (3, 0) → яма 0 сек (2, 2) → Схід 1 сек (3, 2)
Якщо не використовувати «зачаровану яму», потрібно щонайменше 5 секунд.
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа W і H (1 ≤ W, H ≤ 30). Ці цілі числа представляють ширину W і висоту H кладовища. Наступний рядок містить ціле число G (G ≥ 0), кількість надгробків на кладовищі, і за ним слідують G рядків, що містять позиції надгробків. Кожна позиція задається двома цілими числами X і Y (0 ≤ X < W і 0 ≤ Y < H).
Наступний рядок містить ціле число E (E ≥ 0), кількість «зачарованих ям», і за ним слідують E рядків. Кожен з них містить п’ять цілих чисел X1, Y1, X2, Y2, T. (X1, Y1) — це позиція «зачарованої ями» (0 ≤ X1 < W і 0 ≤ Y1 < H). (X2, Y2) — це місце призначення «зачарованої ями» (0 ≤ X2 < W і 0 ≤ Y2 < H). Зверніть увагу, що початкова точка та місце призначення «зачарованої ями» можуть бути ідентичними. T (−10 000 ≤ T ≤ 10 000) — це різниця в секундах між моментом, коли хтось входить у «зачаровану яму», і моментом, коли він з’являється в місці призначення; позитивне число вказує на те, що він досягає місця призначення після входу в яму. Ви можете бути впевнені, що немає двох «зачарованих ям» з однаковим початком, і клітинка призначення «зачарованої ями» не містить надгробка. Крім того, на позиціях (0,0) і (W-1,H-1) немає ні надгробків, ні «зачарованих ям».
Вхід закінчиться рядком, що містить 0 0, який не слід обробляти.
Вихідні дані
Для кожного тестового випадку, якщо Наляканий Джон може подорожувати назад у часі нескінченно, виведіть Never. В іншому випадку виведіть мінімальний час у секундах, який потрібен йому, щоб перетнути кладовище від входу до виходу, якщо це можливо, і Impossible, якщо ні.