B - vs. DEGwer Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

これはインタラクティブな問題です．ジャッジプログラム（インタラクタ）の実行に最大 1 秒程度を要するため，実行時間制限を長めに設定しています．

10 年にわたる長旅の末，あなたはついに大魔王 DEGwer 城に辿り着きました． 城の入口はダンジョンになっており，これを通り抜けなければ大魔王 DEGwer の下には辿り着けません．

ダンジョンは H 行 W 列のマス目状になっています． 各マスは部屋であり，上下左右に隣接する部屋同士の間には扉が 1 つずつ設置されています． また，最も左の列にある各部屋の左側には入口となる扉が，最も右の列にある各部屋の右側には出口となる扉が，それぞれ 1 つずつ設置されています．

今，すべての扉は未固定の状態です． 以下の魔法を交互に使うことで，あなたは「開いた扉を通行して移動を繰り返すことで，開いた入口から開いた出口に到達可能である」ように，大魔王 DEGwer はそうならないようにしたいです．

  • あなた：「未固定の扉を任意に 1 つ選び，その扉を開いて（通行可能な状態で）固定する」魔法
  • DEGwer：「未固定の扉を任意に 1 つ選び，その扉を閉じて（通行不可能な状態で）固定する」魔法

ダンジョンの大きさ (H, W) と，どちらが先に魔法を使うかが与えられるので，互いに最善を尽くした場合にあなたの目的が達成可能かどうかを判定してください． さらに，あなたの目的が達成可能である場合には，その手順（あなたが使う魔法）をインタラクティブに示してください．

制約

  • 1 \leq H \leq 20
  • 1 \leq W \leq 20
  • \textrm{move} は First または Second のいずれかであり，First はあなたが先に魔法を使うことを，Second は大魔王 DEGwer が先に魔法を使うことを表す．

入力

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

H W \textrm{move}

出力

互いに最善を尽くした場合にあなたの目的が達成可能である場合には Yes を，達成不可能である場合には No を出力せよ．

さらに，Yes の場合には，あなたの目的を達成する手順（あなたが使う魔法）を以下の形式でインタラクティブに出力せよ．（入出力例 2 も参考にせよ．）

t i j
  • t は | または - である．
  • i, j は整数である．
  • t = {}| の場合，1 \leq i \leq H かつ 1 \leq j \leq W + 1 であり，魔法の対象として，横通行（左右に隣接する部屋同士の間，あるいは，入口または出口）の扉のうち，上から i 番目，左から j 番目のものを選ぶことを意味する．
  • t = {}- の場合，1 \leq i \leq H - 1 かつ 1 \leq j \leq W であり，魔法の対象として，縦通行（上下に隣接する部屋同士の間）の扉のうち，上から i 番目，左から j 番目のものを選ぶことを意味する．

あなたの出力に対し，同じ形式の入力が返ってくる． ただし，\textrm{move} = {}First の場合は Yes に続けてあなたが先に出力し，\textrm{move} = {}Second の場合は Yes の出力の直後に先に入力される． いずれの場合も，出力を行うたびに，末尾に改行を入れて標準出力を flush すること．

  • t は |, -, a, w のいずれかである．
  • t が | または - の場合，出力と同じ形式で大魔王 DEGwer が次に選ぶ扉を表す．
  • t = {}a の場合，i = j = 0 であり，あなたのインタラクティブ回答が正答である（ことが確定した）ことを表す．
  • t = {}w の場合，i = j = 0 であり，あなたのインタラクティブ回答が正答でない（ことが確定した）ことを表す．
  • t が a または w の入力を受け取った場合，ただちにプログラムを終了すること．

入力例 1

1 1 First

出力例 1

No

この例では，ダンジョンは 1 つの部屋のみからなり，その部屋の左側に入口の扉が，右側に出口の扉があります． あなたの目的を達成するには両方の扉を開ける必要がありますが，あなたが先に魔法を使えるとしても，あなたが選ばなかった方の扉を大魔王 DEGwer が選ぶことで目的の達成が阻止されます． したがって，あなたの目的は達成不可能です．

入力例 2

2 1 First

出力例 2

Yes
...

この例では，以下のように，ダンジョンは縦に並んだ 2 つの部屋からなり，それらの間に縦通行の扉が 1 つあり，各部屋の左右に入口と出口の扉が計 2 つずつあります．

| |
 -
| |

あなたが先に魔法を使えるので，たとえば唯一の縦通行の扉 - 1 1 を選んだとします． すると，大魔王 DEGwer がどのように扉を選んでも，残った入口と出口の 2 つずつの扉のうち 1 つずつをあなたが選ぶことができ，最初の魔法により 2 つの部屋間は移動可能となっているので，結果としてあなたの目的は達成可能であることがわかります．

以下はインタラクティブ入出力の一例です．

入力　　　 出力　　 説明
2 1 First 入力が与えられます．
Yes あなたの目的は達成可能なので Yes を出力します．
- 1 1 あなたは，縦通行の扉のうち，上から 1 番目，左から 1 番目のものを選び，開いて固定します．
| 1 2 大魔王 DEGwer は，横通行の扉のうち，上から 1 番目，左から 2 番目のもの（右上の出口）を選び，閉じて固定します．
| 2 2 あなたは，横通行の扉のうち，上から 2 番目，左から 2 番目のもの（右下の出口）を選び，開いて固定します．
| 2 1 大魔王 DEGwer は，横通行の扉のうち，上から 2 番目，左から 1 番目のもの（左下の入口）を選び，閉じて固定します．
| 1 1 あなたは，横通行の扉のうち，上から 1 番目，左から 1 番目のもの（左上の入口）を選び，開いて固定します．
a 0 0 この時点で，左上の開いた入口から右下の開いた出口に到達可能であることが確定し，正答であることを表す入力が与えられるので，ただちにプログラムを終了してください．

この例ではあなたが先に魔法を使いますが，そうでない（ \mathrm{move} = {}Second である）場合には，Yes の出力の直後に大魔王 DEGwer が魔法の対象として選ぶ扉が同じ形式で入力されます．

入力例 3

2 1 Second

出力例 3

No

上の例と同じダンジョンですが，大魔王 DEGwer が先に魔法を使うので，あなたの目的は達成不可能となります． たとえば，上の例であなたが最初に選んだ縦通行の扉を選ばれると，入出力例 1 と同じ状況が縦に 2 つ並んだような状態となり，（いずれにおいても）あなたが先に魔法を使えるとしても目的は達成不可能です．

Score : 100 points

Problem Statement

This is an interactive problem. Because the judge program (interactor) requires around 1 second in the worst case, the time limit is set to be longer.

You have eventually reached the castle of Great Satan DEGwer after 10-year journey. The entrance of the castle is a dungeon, which cannot avoid for arriving at DEGwer.

The dungeon is of form a grid with H rows and W columns. Each of H \times W squares is a room, and there is a door between any pair of adjacent rooms. In addition, there is an entrance door on the left side of each room located in the left-most column, and there is an exit door on the right side of each room located in the right-most column.

Now, all the door are unfixed. You want to let the dungeon such that some open exit door can be reached from some open entrance door by repeatedly passing through open doors, and DEGwer wants to prevent your objective. For their own objectives, you and DEGwer alternately use the following magics.

  • Your magic: Choose any unfixed door, fix it as open (passable).
  • DEGwer's magic: Choose any unfixed door, fix it as closed (impassable).

You are given the size (H, W) of the dungeon and who uses the magic first. Determine whether your objective is achievable or not when you and DEGwer do their best. In addition, if your objective is achievable, indicate interactively one possible way (your magics) to do so.

Constraints

  • 1 \leq H \leq 20
  • 1 \leq W \leq 20
  • \textrm{move} is either First or Second, where First means that you use the magic first, and Second means that DEGwer uses the magic first.

Input

The input is given from Standard Input in the following format:

H W \textrm{move}

Output

Print Yes if your objective is achievable and No otherwise, under the assumption that you and DEGwer do their best.

In addition, if the answer is Yes, print interactively in the following format for which doors you use magic. (See also Sample 2.)

t i j
  • t is either | or -.
  • i and j are integers.
  • If t = {}|, then 1 \leq i \leq H and 1 \leq j \leq W + 1, which represents that the door chosen as a target of the magic is the i-th from the top and the j-th from the left among those which are passed horizontally (i.e., the doors between two horizontally adjacent rooms and all the entrance and exit doors).
  • If t = {}-, then 1 \leq i \leq H - 1 and 1 \leq j \leq W, which represents that the door chosen as a target of the magic is the i-th from the top and the j-th from the left among those which are passed vertically (i.e., the doors between two vertically adjacent rooms).

Against your output, an input in the same format will be returned. Note that if \textrm{move} = {}First, then you should print your output followed by printing Yes, and if \textrm{move} = {}Second, then you should receive an input just after printing Yes. In either case, each time you print something, end it with a newline and flush Standard Output.

  • t is one of |, -, a, and w.
  • If t is either | or -, then it represents the door chosen by DEGwer in the same manner.
  • If t = {}a, then i = j = 0, and it means that your interactive answer has been confirmed as a correct answer.
  • If t = {}w, then i = j = 0, and it means that your interactive answer has been confirmed as a wrong answer.
  • If you receive an input with t = {}a or t = {}w, your program must halt immediately.

Sample Input 1

1 1 First

Sample Output 1

No

In this case, the dungeon consists of only one room, whose left side has a unique entrance door and right side has a unique exit door. For your objective, you have to fix both doors as open, but it cannot be done even if you use the magic first. Thus, your objective is not achievable.

Sample Input 2

2 1 First

Sample Output 2

Yes
...

In this case, as shown in below, the dungeon consists of two vertically adjacent rooms, there is a unique vertically passable door between them, and the left and right sides of both rooms have two entrance and exit doors, respectively, in total.

| |
 -
| |

You use the magic first, and suppose that you choose the unique vertically passable door - 1 1. Then, no matter how DEGwer will choose doors, you can choose one from the remaining two entrance doors and one from the remaining two exit doors, which achieve your objective because the two rooms became connected by your first magic.

The following is an example of interactive inputs and outputs.

Input    Output  Explanation
2 1 First An input is given.
Yes As your objective is achievable, you print Yes.
- 1 1 You fix as open one that is 1st from the top and 1st from the left among the vertically passable door.
| 1 2 DEGwer fixes as closed one that is 1st from the top and 2nd from the left among the horizontally passable doors, i.e., the upper-right exit door.
| 2 2 You fix as open one that is 2nd from the top and 2nd from the left among the horizontally passable doors, i.e., the lower-right exit door.
| 2 1 DEGwer fixes as closed one that is 2nd from the top and 1st from the left among the horizontally passable doors, i.e., the lower-left entrance door.
| 1 1 You fix as open one that is 1st from the top and 1st from the left among the horizontally passable doors, i.e., the upper-left entrance door.
a 0 0 At this point, it is confirmed that the open lower-right exit door can be reached from the open upper-left entrance door, and your program must halt immediately after receiving the input indicating it.

Sample Input 3

2 1 Second

Sample Output 3

No

The dungeon is the same as above, but your objective is not achievable as DEGwer uses the magic first. For example, if DEGwer fixes the unique vertically passable door (that you choose first in Sample 2) as closed, then the situation is just like two parallel copies of Sample 1, in which your objective is not achievable even if you use the magic first.