描述

n阶魔方有6个面,分别为U(p),D(own),L(eft),R(ight),F(orward),B(ack)。即上,下,左,右,前,后面。下图是一个6阶魔方,图中展示了其U面,F面和R面。如图所示建立坐标系,则黄色标注的块的坐标是(6,6,1)。

每次可以把魔方的某一层旋转90°或180°。下面是一个旋转90°的例子。

魔方的一个色块可以用其坐标及其朝向表示。例如左上图中,两个橙色色块可以表示为(5,2,1)F和(5,5,1)F,它们经过旋转以后的位置分别是(5,6,2)U和(5,6,5)U。
现在给出一个色块的位置和一个目标位置,求最少的旋转次数,使得色块到达目标位置。

输入格式

共一行,依次为魔方阶数n,起始位置的坐标与朝向,目标位置的坐标与朝向。

输出格式

输出一个整数,即最小步数。特殊地,如果目标位置无法到达,输出-1。

样例输入与输出

输入1:
6 5 2 1 F 5 6 2 U
输出1:
1
输入2:
6 5 2 1 F 5 6 5 U
输出2:
2
输入3:
6 5 2 1 F 6 6 1 F
输出3:
-1

数据范围与约定

1≤n≤1000,1≤x,y,z≤n。保证所有提到的色块都在魔方的某个面上。

样例解释

第二个样例数据中,一个可行的方法是:先通过旋转F面将色块移至(5,5,2)F,然后的方法同题目描述。