Пан Дивак вирішив поїхати до своєї сестри. Плануючи поїздку, він дізнався  про вартість проїзду в усіх автобусних рейсах їхнього району. Але пан таки був дивак,  бо вирішив, що  вартість його проїзду до сестри повинна дорівнювати непарній кількості копійок. А з другого боку, він хоче  дістатися якнайдешевше, тобто знайти найдешевший серед тих маршрутів, в яких сумарна вартість поїздки є непарною. Пересадки Дивака не лякають. Окремі частини маршруту можуть коштувати парну кількість копійок; непарною має бути сума вартостей усіх використаних рейсів.
     Рейси виконуються між N населеними пунктами, серед яких село пана Дивака позначене як №1, сестри — як №2. Для кожної пари пунктів або взагалі не існує прямого сполучення, або вартість проїзду відома й однакова в обох напрямках. Із будь-якого пункту гарантовано можна дістатися до інших, але не виключено, що всі можливі способи коштуватимуть парну кількість копійок.

У Країні Правильних Трикутників  (КПТ) міста розташовано у вузлах нескінченної сітки  доріг, що показана на малюнку. Довжина дороги між найближчими містами складає 1 УК (умовний кілометр), тобто кожне місто з'єднано дорогами з 6 іншими містами. Міста задаються своїми координатами, столиця країни – початок координат. Король КПТ планує відвідати деяке місто.
Звичайно, маршрут повинен починатись у столиці. Одначе Його Величності хочеться проїжджати тільки дорогами і тільки так, щоб кожне наступне місто знаходилося строго ближче до мети (в геометричному сенсі, тобто по прямій), ніж будь-яке раніше відвідане, включаючи столицю.   Щоб підрахувати кілкість різних маршрутів короля, радники Його Величності звернулись до Вас.
Допоможіть їм.

Програма Triangles читає з клавіатури через пропуск координати міста x,y – цілі числа, що не перевищують 200 за