まず, \((X_i, Y_i)\) へのルートを辿った距離とその点へのマンハッタン距離の差は2の倍数でなければならない. よって各点へのマンハッタン距離の偶奇はすべて一致していなくてはならない. これを満たさない場合は -1 である.

以下 \(X_i+Y_i\) を \(2\) で割った余りは \(1\) とする. 余りが \(0\) の場合は \((1, 0)\) に向かう腕を用意して \((1, 0)\) をスタート地点と考えればいい.

ここで, \(u = x+y, v = x-y\) とする. こうすると, \(u_i, u_i\) は以下のようになる.

腕のモードが L のとき: \((u_i, v_i) = (u_{i-1}-d_i, v_{i-1}-d_i)\)

腕のモードが R のとき: \((u_i, v_i) = (u_{i-1}+d_i, v_{i-1}+d_i)\)

腕のモードが D のとき: \((u_i, v_i) = (u_{i-1}-d_i, v_{i-1}+d_i)\)

腕のモードが U のとき: \((u_i, v_i) = (u_{i-1}+d_i, v_{i-1}-d_i)\)

このとき, \(u_m\) は以下のようになる.

\[u_m = \sum_{i=1}^m d_i - 2\sum_{i \in S} d_i\]

ただし, \(S\) は腕のモードが L か D である \(i\) の集合である.

ここで \(d_i = 2^{i-1}\) とすると,

\[\sum_{i \in S} 2^{i-1} = \frac{2^m - 1 - u_m}{2}\]

となる.

\(-2 \times 10^9 \leq u_m \leq 2 \times 10^9\) であるので, \(m = 31\) とすれば右辺は \(2^{31}\) 以内に収まる. よって \(S\) は右辺を2進数に展開することで求めることができる.

同様に \(v_m\) についても腕のモードが L か U である \(i\) の集合 \(T\) を求め, \(S\) と \(T\) から各腕のモードを一意に決めることができる.