1. Спільний елемент

Максимальна оцінка: 15 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: common.in
Вихідний файл: common.out
Програма: common.*

Завдання
Створіть програму, яка знайде найменше натуральне число, що одночасно належить даним n нескінченним арифметичним проґресіям натуральних чисел.

Вхідні дані
Файл містить (2n + 1) невід'ємне ціле число. Перше число — n. В j-ій парі чисел після n (у вказаному порядку) — перший член j-ої проґресії та її різниця. Всі числа вхідного файлу не перевищують 10000, причому n < 100.

Вихідні дані
Файл має містити лише шукане число. Якщо такого числа немає, то файл містить 0.

Приклад

2. Лабіринт

Максимальна оцінка: 9 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: labirint.in
Вихідний файл: labirint.out
Програма: labirint.*

Завдання
Створіть програму, яка допоможе герою твору Джерома К.Джерома «Троє у човні, не рахуючи собаки» Гаррісу якнайшвидше вийти з Гемптон-Кортського лабіринту. Лабіринт на плані має вид прямокутника, сторони якого спрамовані із заходу на схід або з півночі на південь (наскільки це можливо, враховуючи кулясту форму Землі). Розміри лабіринту в ярдах (анґлійська міра довжини, приблизно 91,44 см) вздовж паралелі та мередіану виражено натуральними числами n та m відповідно, а його загальна площа mn не перевищує 10000 (квадратних ярдів). Всю територію лабіринту поділено на квадрати з довжиною сторони 1 ярд. Частину квадратів засаджено кущами з колючками, які можна лише обійти.

Вхідні дані
Перший рядок файлу містить два натуральних числа m і n — розміри лабіринту в ярдах.

Наступні m рядків по n символів цього файлу містять схему лабіринту, в якій символ « » (пропуск) означає вільний квадрат поверхні, інший символ — квадрат з кущем, хрестик (знак додавання) «+» — початкове розташування Гарріса. Виходу з лабіринту відповідають елементи 1-го та m-го рядка і 1-ий та n-ий елемент кожного рядка, якщо вони є пропуском або знаком додавання. Рух у лабіринті здійснюють у напрямку сторін світу на вільний від кущів сусідній квадрат. Рухові на північ південь, захід чи схід відповідає рух вгору, вниз, ліворуч чи праворуч на один символ на схемі, поданій вхідним файлом.

Вихідні дані
Перший рядок файлу має містити ціле число — найменшу кількість кроків довжиною 1 ярд, які має зробити Гарріс, щоб вийти з лабіринту.

Другий рядок цього файлу має містити опис такого найкоротшого шляху — кроків від першого до останнього, у якому літера n позначає крок на північ (анґлійською north), s — на південь (south), e — на схід (east), w — на захід (west).

Якщо Гарріс вже знаходяться на виході, то єдиний рядок файлу містить число 0.

Якщо вийти з лабіринту неможливо (не будемо обговорювати, яким чином у цьому випадку Гарріс потрапив у відповідне місце лабіринту), то єдиний рядок файлу містить число –1.

Приклад

9 9
ШШШШШШШШШ
Ш        
Ш ШШШШШШШ
Ш Ш   + Ш
Ш Ш Ш Ш Ш
Ш Ш Ш Ш Ш
Ш Ш Ш Ш Ш
Ш   Ш   Ш
ШШШШШШШШШ

22
wwwsssswwnnnnnneeeeeee