AtCoder Regular Contest 039

C - 幼稚園児高橋君


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 256MB

問題文

無限に広がる二次元格子があります。原点 (0,0) から右に x、上に y 進んだ格子点の座標を (x,y) と表します。

幼稚園児の高橋君はこの格子上で好き放題に動くのが好きです。しかし、あまりにも好き勝手に動くせいで行方不明になってしまいました。 高橋君は以下の行動をしたことが調査により分かっています。

  • 最初、高橋君は (0,0) にいました。
  • 高橋君は好きな方向(上下左右)を決めて、その方向に直進します。そして、今までに訪問していない格子点を踏むまで直進し続けます。訪問していない格子点を踏むといったん止まります。
  • そして、高橋君は疲れるまで上記の操作を繰り返し、疲れると、その格子点で寝てしまいました。

保護者であるあなたは、高橋君がちょうど K 回方向を決めて直進したこと、そして各時点でどの方向に直進したかを知ることができました。 あなたは、プログラムを書いて高橋君が寝ている場所を突き止めることにしました。


入力

入力は以下の形式で標準入力から与えられる。

K
S_1S_2S_3…S_K
  • 1 行目には、高橋君が移動した回数を表す整数 K (1≦K≦200,000) が与えられる。
  • 2 行目には、高橋君の移動の情報を表す K 文字の情報が与えられる。そのうち i(1≦i≦K) 番目の文字 S_ii 回目の移動でどの方向に直進したかを表している。S_iL,R,U,D のときそれぞれ i 回目の移動で左、右、上、下方向に直進したことを表す。

出力

出力は以下の形式で標準出力に行うこと。

1 行目に、2 つの整数 x,y を出力せよ。これは高橋君の寝ている場所の座標が (x,y) であることを表す。

末尾の改行を忘れないこと。


入力例1

3
RLU

出力例1

-1 1

高橋君がいったん止まった格子点を開始地点も含めて順番に列挙すると、(0,0)→(1,0)→(-1,0)→(-1,1) となります。


入力例2

7
RURDRUL

出力例2

0 1

入力例3

25
RLRLRLRLRLRLURLRLRLRLRLRL

出力例3

-12 1

Submit提出する