# 220 : Heighwayのドラゴン

$$\bm{D_{0}}$$ を2文字の文字列$$\text{``Fa''}$$とする. $$n \geq 1$$ では, $$\bm{D_{n}}$$ は $$\bm{D_{n-1}}$$ から以下の変換ルールに従い作られる.

$$
\begin{aligned}
\text{``a''} &\rightarrow \text{``aRbFR''} \\
\text{``b''} &\rightarrow \text{``LFaLb''}
\end{aligned}
$$

つまり, $$\bm{D_{0}}=\text{``Fa''}, \bm{D_{1}} = \text{``FaRbFR''}, \bm{D_{2}} = \text{``FaRbFRRLFaLbFR''}, \dots$$ となる.

これらの文字列はコンピューターグラフィックスプログラムへの命令と解釈できる: "F"を"1ユニット前へ描け", "L"を"90度左を向け", "R"を"90度右を向け", "a"と"b"は無視する. カーソルの初期位置は(0,0), 向きは(0,1)方向, つまり上とする.

$$\bm{D_{n}}$$ は $$n$$次の"Heighwayのドラゴン"(Heighway Dragon)として知られる奇妙な図となる. 例えば, 下図は $$\bm{D_{10}}$$ である. 各"F"を1ステップとして数えると, 500ステップ目で図中で強調してある(18,16)に到達する.

![](https://projecteuler.net/project/images/p220.gif)

$$\bm{D_{50}}$$ において $$10^{12}$$ ステップ後の座標を求めよ. 回答は $$x,y$$ という形式でスペースを入れずに入力せよ.
