\(S\) の表すパスに含まれるマスの値は全部 \(0\) としてよいです． （マス \((i,j)\) の値が \(v\) だとした場合，\(r+c=i+j\) を満たすすべてのマス \((r,c)\) の値を \(v\) で \(XOR\) すればいいです．）

RD という移動があるたび，そこを DR に変えることで，余計なマスを \(1\) つだけ通れるようになります． DR についても同様です．

\(S\) から RD, DR という部分文字列をできるだけ多く取り出すことを考えます． ただし，取り出した文字列が共通部分を持たないようにします．

これは単に先頭から貪欲に取っていけばよいです． こうして \(A\) 個の文字列が取り出せたとします． すると，\(S\) が表すパスに含まれないある \(A\) 個のマスがあって，それらの部分集合を自由に選んで通ることができることになります．

例えば，\(S=\)RRDRDDRD を考えます．

000..
.#00.
..#0#
...00
....0

\(S=\)R[RD][RD][DR]D とすると \(3\) つの文字列を取り出すことができ，それに対応する余計なマスを # で示しています．

明らかに \(A \leq K\) が必要です． そしてこれは十分です．

取り出した RD,DR に対応する曲がり角に，それぞれ異なる \(2\) 冪を書き込んでみます． 上記に該当しない曲がり角には，直前の曲がり角と同じ値を書くことにします． さらに，曲がり角に書いた値を，対角線上に伸ばしておきます．

\(S=\)RDRDRD に対応する例：

001.
1002
.200
2.40

\(S=\)RRDRDDRD に対応する例：

0001.
.100.
1.204
.2.00
2..40

(.のマスの値も \(0\) ですが，わかりやすさのため . のままにしてあります．)

すると，\(S\) が表すパス以外のパスは，\(A\) 個の \(2\) 冪の数の非空な部分集合を通ることになり，これらの値の総 \(XOR\) は非ゼロとなって条件を満たします．

解答例