#agc033b. [agc033_b]LRUD Game

[agc033_b]LRUD Game

問題文

HH 行、横 WW 列の長方形上のマス目があります。上から ii 行目、左から jj 列目のマスを (i,j)(i,j) と表します。 このマス目の上には一つの駒が置いてあり、最初はマス (sr,sc)(s_r,s_c) に置いてあります。

高橋君と青木君はそれぞれ長さ NN の文字列を用意してゲームをすることにしました。 高橋君は文字列 SS を、青木君は文字列 TT を用意し、SSTT はともに L, R, U, D44 種類の文字からなります。

ゲームは NN 回のステップからなります。ii 回目のステップは以下のように進行します。

  • まず高橋君が操作を行う。この操作では、駒を SiS_i の方向に動かす、もしくは、駒を動かさないかのいずれかを行う。
  • 次に青木君が操作を行う。この操作では、駒を TiT_i の方向に動かす、もしくは、駒を動かさないかのいずれかを行う。

ここで、駒を L, R, U, D の方向に動かすとは、駒がマス (r,c)(r,c) にあったとき、 それぞれマス (r,c1)(r,c-1), (r,c+1)(r,c+1), (r1,c)(r-1,c), (r+1,c)(r+1,c) に動かす操作を指します。 ただし、その座標に対応するマスが存在しない場合は、駒をマス目から取り除く操作を指すことにします。 この操作が行われた場合、NN 回のステップが終わっていなくても、その時点でゲームは終了します。

高橋君は NN 回のステップのいずれかのステップで駒をマス目から取り除きたいです。 一方で、青木君は最終的に駒がマス目上に残ったまま、NN 回のステップを終えたいです。 二人が最適に行動したとき、ゲームが終了した時点で駒がマス目上に残っているかどうかを判定してください。

制約

  • 2H,W2times1052 ≦ H,W ≦ 2 \\times 10^5
  • 2N2times1052 ≦ N ≦ 2 \\times 10^5
  • 1srH1 ≦ s_r ≦ H
  • 1scW1 ≦ s_c ≦ W
  • S=T=N|S|=|T|=N
  • SSTTL, R, U, D44 種類の文字からなる。

入力

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

HH WW NN srs_r scs_c SS TT

出力

ゲームが終了した時点で駒がマス目上に残っているならば YES を、 そうでないならば NO と出力せよ。


入力例 1

2 3 3
2 2
RRL
LUD

出力例 1

YES

ゲームは例えば以下のように進行します。

  • 高橋君が駒を右に動かし、駒は (2,3)(2,3) に移動する。
  • 青木君が駒を左に動かし、駒は (2,2)(2,2) に移動する。
  • 高橋君は駒を動かさず、駒の位置は (2,2)(2,2) のままとなる。
  • 青木君は駒を上に動かし、駒は (1,2)(1,2) に移動する。
  • 高橋君は駒を左に動かし、駒は (1,1)(1,1) に移動する。
  • 青木君は駒を動かさず、駒の位置は (1,1)(1,1) のままとなる。

入力例 2

4 3 5
2 2
UDRRR
LLDUD

出力例 2

NO

入力例 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

出力例 3

NO