Найкоротший шлях двох коней

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

Вхідні дані

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

Вихідні дані

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

Приклади