KOZE - Sheep


Mirko has a herd of sheep, surrounded by fences backyard. While he was asleep, wolves have sneaked into the fenced area and attacked the sheep.

Backyard is of a rectangular shape, and consists of fields arranged in rows and columns.

Character '.' (fullstop) represents a blank field.

Character '#' represents a fance.

Character 'k' represents a sheep.

Character 'v' represents a wolf.

 

Two fields belong to the same sector if we can move from the field A to the field B without going over the fence, by making only horizontal and vertical steps (we cannot move diagonally).

If we can escape from field A from the backyard, that field does not belong to any sector.

Luckily, Mirko taught his sheep Kung-Fu skills, and they can defend themselves against wolves only if they outnumber the wolves in that sector. When there are more sheep in the sector than wolves, all wolves die without sheep casualties. Otherwise all sheep perish and wolves are unharmed. If a field doesn't belong in any sector, sheep will flee and wolfs will be left without a prey, so every animal survives.

 

Write a program that will determine how many sheep and wolves will survive this bloody night.

 

Input

Integers N and M, number of rows and columns which represent Mirko's backyard.

In every of the N lines, there are M characters representing the appearence of Mirko's backyard - positions of the fences, wolves and sheep.

 

Constraints

3 <= N, M <= 250

 

Output

In the first and the only line, print the number of sheep and wolves that will survive.

 

Example

Input:
8 8  
.######.  
#..k...#  
#.####.#  
#.#v.#.#  
#.#.k#k#  
#k.##..#  
#.v..v.#  
.######. Output: 3 1

hide comments
aditya prakash: 2014-01-02 13:57:54

@problem setter
there are wrong answers being accepted.
kindly make strong test cases ,...u dont have test cases checking if sheep can escape from backyard or not.

Martijn Muijsers: 2013-12-08 16:54:35

Fun question :P

Rishikesh Jha: 2013-06-01 05:13:42

0.00 sec :D

RISHABH JAIN: 2013-04-10 15:12:40

easy question

PubLic_AvenGeR: 2012-12-28 20:12:16

Warning : Dont use gets. Use scanf("%s",....); .

Buda IM (retired): 2012-12-05 20:13:39

Please read the notes below, no hints, we have a forum for that.

Last edit: 2012-12-08 16:56:58
Erik Lonèarek: 2012-12-05 12:32:41

Input:
9 12
.###.#####..
#.kk#...#v#.
#..k#.#.#.#.
#..##k#...#.
#.#v#k###.#.
#..#v#....#.
#...v#v####.
.####.#vv.k#
.......####.

Output: 3 5

Aman Gupta: 2012-12-03 10:14:36

1. Yes
2. Yes

Last edit: 2012-12-03 10:15:03
Xsquare: 2012-12-03 10:11:42

I have some questions!
1. If there is a way to escape somehow out of the field!.. then both will survive?
2. if number of sheeps = number of wolves.. all sheeps die and allwolves survive in that sector?


Added by:Erik Lončarek
Date:2012-12-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Croatian Regionals 2005