B - LRUD Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

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

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

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

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

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

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

制約

  • 2 ≦ H,W ≦ 2 \times 10^5
  • 2 ≦ N ≦ 2 \times 10^5
  • 1 ≦ s_r ≦ H
  • 1 ≦ s_c ≦ W
  • |S|=|T|=N
  • S と T は L, R, U, D の 4 種類の文字からなる。

入力

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

H W N
s_r s_c
S
T

出力

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

入力例 1

2 3 3
2 2
RRL
LUD

出力例 1

YES

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

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

入力例 2

4 3 5
2 2
UDRRR
LLDUD

出力例 2

NO

入力例 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

出力例 3

NO

Score : 600 points

Problem Statement

We have a rectangular grid of squares with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left. On this grid, there is a piece, which is initially placed at square (s_r,s_c).

Takahashi and Aoki will play a game, where each player has a string of length N. Takahashi's string is S, and Aoki's string is T. S and T both consist of four kinds of letters: L, R, U and D.

The game consists of N steps. The i-th step proceeds as follows:

  • First, Takahashi performs a move. He either moves the piece in the direction of S_i, or does not move the piece.
  • Second, Aoki performs a move. He either moves the piece in the direction of T_i, or does not move the piece.

Here, to move the piece in the direction of L, R, U and D, is to move the piece from square (r,c) to square (r,c-1), (r,c+1), (r-1,c) and (r+1,c), respectively. If the destination square does not exist, the piece is removed from the grid, and the game ends, even if less than N steps are done.

Takahashi wants to remove the piece from the grid in one of the N steps. Aoki, on the other hand, wants to finish the N steps with the piece remaining on the grid. Determine if the piece will remain on the grid at the end of the game when both players play optimally.

Constraints

  • 2 \leq H,W \leq 2 \times 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq s_r \leq H
  • 1 \leq s_c \leq W
  • |S|=|T|=N
  • S and T consists of the four kinds of letters L, R, U and D.

Input

Input is given from Standard Input in the following format:

H W N
s_r s_c
S
T

Output

If the piece will remain on the grid at the end of the game, print YES; otherwise, print NO.

Sample Input 1

2 3 3
2 2
RRL
LUD

Sample Output 1

YES

Here is one possible progress of the game:

  • Takahashi moves the piece right. The piece is now at (2,3).
  • Aoki moves the piece left. The piece is now at (2,2).
  • Takahashi does not move the piece. The piece remains at (2,2).
  • Aoki moves the piece up. The piece is now at (1,2).
  • Takahashi moves the piece left. The piece is now at (1,1).
  • Aoki does not move the piece. The piece remains at (1,1).

Sample Input 2

4 3 5
2 2
UDRRR
LLDUD

Sample Output 2

NO

Sample Input 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

Sample Output 3

NO