vs. DEGwer

AtCoder

ID1202Contest_b

Time5000ms

Memory256MB

Difficulty—

**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}$ [samples]

Samples

Input #1

1 1 First

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.

Input #2

2 1 First

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 $1$st from the top and $1$st from the left among the vertically passable door.

`| 1 2`

DEGwer fixes as closed one that is $1$st from the top and $2$nd from the left among the horizontally passable doors, i.e., the upper-right exit door.

`| 2 2`

You fix as open one that is $2$nd from the top and $2$nd from the left among the horizontally passable doors, i.e., the lower-right exit door.

`| 2 1`

DEGwer fixes as closed one that is $2$nd from the top and $1$st from the left among the horizontally passable doors, i.e., the lower-left entrance door.

`| 1 1`

You fix as open one that is $1$st from the top and $1$st 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.

Input #3

2 1 Second

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.

API Response (JSON)

{
  "problem": {
    "name": "vs. DEGwer",
    "description": {
      "content": "**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 Gre",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "1202Contest_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**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.**\nYou have eventually reached the castle of Gre...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments