Коні ходять по черзі

Переведіть кожного з двох коней з однієї клітинки в іншу за нйменшу загальну кількість ходів.

Два коня не можуть одночасно знаходитись в одній клітинці. Ходи коней повинні чергуватись.

Вхідні дані

У вхідному файлі записані координати першого та другого коня, потім координати клітинок, куди потрібно їх перемістити.

Вихідні дані

Програма повинна вивести послідовність ходів коней у вигляді декількох рядків. Першим символом у рядку повинен бути номер коня (1 чи 2), потім, через пропуск, координати клітинки, у яку він переставляється. Необхідно вивести довільний з можливих оптимальних розв'язків. Коні повинні ходити по черзі, першим може ходити довільний з коней, коні можуть зробити різне число ходів.

Приклади