T. 骑士周游

传统 1000 ms 256 MiB
标准 IO
Special Judge

题目描述

8×88\times 8 的国际象棋棋盘上,给定一个起始格子 (x0,y0)(x_0,y_0)
请你输出一条“马走日字”的路径,使得:

  1. (x0,y0)(x_0,y_0) 出发;
  2. 恰好访问所有 6464 个格子各一次;
  3. 任意两步之间均遵循马的移动规则(日字,横向 ±1\pm1 纵向 ±2\pm2 或横向 ±2\pm2 纵向 ±1\pm1)。

任意输出一条合法路径即可;若无解,输出 -1

输入格式

一行两个整数 x0,y0 (1x0,y08)x_0,y_0\ (1\le x_0,y_0\le 8),表示起始行列。

输出格式

第一行 6464 个整数,按访问顺序给出格子的坐标;
第二行 6464 个整数,按访问顺序给出格子的坐标。
若无解,仅输出 -1

样例

样例输入

1 1

样例输出

1 2 1 2 4 6 8 7 6 8 7 8 7 5 3 1 2 1 2 3 1 3 5 7 8 7 8 6 4 2 1 3 5 6 8 7 5 4 2 1 3 2 4 6 4 3 5 4 6 8 7 5 3 4 2 1 3 4 6 5 7 5 6 8
1 3 5 7 8 7 8 6 8 7 5 3 1 2 1 2 4 6 8 6 7 8 7 8 6 4 2 1 2 1 3 2 1 3 4 2 3 1 2 4 3 5 4 5 6 4 5 3 2 1 3 4 5 7 6 8 7 5 4 6 7 8 6 5

数据范围与提示

  • 棋盘固定 8×88\times 8
  • 1010 组数据,起点随机。
  • 本题中,不要求你的输出和标准输出完全一样,只要满足输出格式并且满足题目要求即可判定为正确