YOU: "Sorry, I'm still getting caught up on what everyone's role was here."

GLEB: "Nah, all good! I think I mostly got used as the muscle of the group. Kevin had me running heavy stuff in and out of the hall basically the whole afternoon."

YOU: "And you were okay with that?"

GLEB: "Yeah, it's fine, I mean, I am built for it! But I'm also the events manager of ACPC, you know? Feels like I could've had some real responsibility for once. Still, silver lining, I got to see the whole venue. A lot of the guys I was delivering stuff to, I didn't see them leave all afternoon."

YOU: "You were all over the venue? Did you ever go backstage?"

GLEB: "Oh yeah! Man, cramped place back there. But I had to drop some stuff off for Lukaz. Poor guy looked so stressed, honestly."

YOU: "What time was that?"

GLEB: "Quarter to six? I remember because I checked my phone right after. Thought I'd be done by five."

The event requires a lot of equipment: AV tools, DJ decks, and crates of food and liquor. As the strongest person in ACPC, it's up to Gleb to get this equipment to where it needs to be.

Unfortunately, between Gleb's car and the venue lies a garden swarming with bees! The garden is modelled as an ~r \times c~ grid of tiles. Gleb's car is at tile ~(1, 1)~ and the venue entrance is at tile ~(r, c)~. Gleb moves orthogonally between adjacent tiles: up, down, left, or right. Every tile is passable — the only thing standing between Gleb and the venue is how much he gets stung.

A tile is either empty or holds one of two types of bee: a worker bee or a queen bee.

• Stepping onto a tile with a worker bee stings Gleb once. That worker then flies away, leaving the grid.
• Stepping onto a tile with a queen bee stings Gleb once for every active bee, including the queen he just stepped onto and every other bee still on the grid. Afterwards, all bees fly away, and every tile becomes empty for the rest of Gleb's journey.

Gleb may be strong, but he can only tolerate so much pain. Can he get from his car to the venue while being stung at most ~k~ times in total?

Input

The first line contains three integers ~r~, ~c~, and ~k~ (~1 \leq r, c \leq 1000~, ~0 \leq k \leq r \cdot c - 2~), the number of rows, the number of columns, and the maximum number of times Gleb can tolerate being stung.

The next ~r~ lines each contain a string of ~c~ characters describing the grid, where each character is one of:

• . — an empty tile,
• W — a tile with a worker bee,
• Q — a tile with a queen bee.

Tiles ~(1, 1)~ and ~(r, c)~ are guaranteed to be empty.

Output

Output Yes if Gleb can travel from ~(1, 1)~ to ~(r, c)~ being stung at most ~k~ times, and No otherwise. The output is case-insensitive.

Example

Input 1

3 4 2
..WQ
Q.Q.
.WW.

Output 1

Yes

Gleb can reach the venue while avoiding every queen. One such route passes through exactly two worker bees, getting stung twice, which is within his tolerance of ~k = 2~.

Input 2

3 3 2
..Q
.Q.
Q..

Output 2

No

The three queens sit on the anti-diagonal, so every route from ~(1, 1)~ to ~(3, 3)~ is forced to step onto a queen. At that moment, all three queens are still active, so Gleb is stung ~3~ times, more than his tolerance of ~k = 2~.

Input 3

3 3 7
.QW
QWW
WW.

Output 3

Yes

Both tiles adjacent to the start are queens, so Gleb must step onto a queen immediately. Doing so stings him once for every bee on the grid; there are ~7~ bees in total, so he is stung exactly ~7~ times, and the grid is then cleared for the rest of the walk. Since ~7 \leq k = 7~, Gleb can tolerate this.