시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 54 1 1 2.273%

문제

상근이는 실험용 쥐를 이용해서 실험을 하고 있다. 상근이는 쥐를 N×N개의 정사각형 칸으로 이루어진 우리에 가두었다. 각각의 칸은 빨간색이거나 흰색이다. 행은 위에서부터 1번부터 N번이며, 열은 왼쪽에서부터 1번이다.

쥐는 네 방향(왼쪽, 오른쪽, 위, 아래)으로 이동한다. 하지만, 빨간색을 무서워하기 때문에, 절대로 빨간 칸에는 들어가지 않는다.

이제 쥐를 크기가 K×K인 박스안에 가둔다. 박스의 변은 모두 우리의 변에 평행하다. 박스 안은 매우 어둡지만 쥐는 어디가 빨간색 칸인지 정확하게 알고 있기 때문에 빨간 칸에 들어가지 않는다.

상근이는 박스 안에 있는 쥐의 위치를 볼 수 없고, 박스의 움직임만 밖에서 볼 수 있다. 쥐가 박스의 가장자리를 미는 경우에 박스가 그 방향으로 움직이게 된다.

위의 그림은 예제를 나타낸 것이다. 검정 동그라미는 쥐, 회색 직사각형은 박스를 나타낸다.

박스의 처음 위치와 박스가 움직인 방향이 모두 주어졌을 때, 그러한 움직임을 만드려면 쥐가 최소 몇 번 이동해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 우리의 크기 N과 박스의 크기 K가 주어진다. (2 ≤ K ≤ 10, K < N ≤ 100)

다음 N개 줄에는 우리의 각 칸이 빨간 칸('r')인지 흰 칸('w')인지 주어진다.

다음 줄에는 박스의 처음 위치 R과 C가 주어지며, 이 좌표는 박스의 왼쪽 위 꼭짓점이다. (1 ≤ R, C ≤ N-K+1)

다음 줄에는 박스가 움직인 횟수 M (1 ≤ M ≤ 1,00,000)이 주어진다.

마지막 줄에는 박스가 움직인 방향이 순서대로 주어진다. (L, R, U, D)

출력

첫째 줄에 쥐가 최소 몇 번 움직이면 입력으로 주어진 방향대로 움직이는지 출력한다.

예제 입력 1

5 3
wwwww
wrwrw
wwwww
wrrrw
wwwww
3 3
2
LU

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMxMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWQ1NTlcdWM3OTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMyZTRcdWQ1ZDhcdWM2YTkgXHVjOTUwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzk1MFx1Yjk3YyBOJnRpbWVzO05cdWFjMWNcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNmIwXHViOWFjXHVjNWQwIFx1YWMwMFx1YjQ1MFx1YzVjOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3NzRcdWFjNzBcdWIwOTggXHVkNzcwXHVjMGM5XHVjNzc0XHViMmU0LiBcdWQ1ODlcdWM3NDAgXHVjNzA0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc3NFx1YmE3MCwgXHVjNWY0XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCAxXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5NTBcdWIyOTQgXHViMTI0IFx1YmMyOVx1ZDVhNShcdWM2N2NcdWNhYmQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNzA0LCBcdWM1NDRcdWI3OTgpXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3NDQgXHViYjM0XHVjMTFjXHVjNmNjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjODA4XHViMzAwXHViODVjIFx1YmU2OFx1YWMwNCBcdWNlNzhcdWM1ZDBcdWIyOTQgXHViNGU0XHVjNWI0XHVhYzAwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1Yzk1MFx1Yjk3YyBcdWQwNmNcdWFlMzBcdWFjMDAgSyZ0aW1lcztLXHVjNzc4IFx1YmMxNVx1YzJhNFx1YzU0OFx1YzVkMCBcdWFjMDBcdWI0NTRcdWIyZTQuIFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWJjYzBcdWM3NDAgXHViYWE4XHViNDUwIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWJjYzBcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHViMmU0LiBcdWJjMTVcdWMyYTQgXHVjNTQ4XHVjNzQwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI0NjFcdWM5YzBcdWI5Y2MgXHVjOTUwXHViMjk0IFx1YzViNFx1YjUxNFx1YWMwMCBcdWJlNjhcdWFjMDRcdWMwYzkgXHVjZTc4XHVjNzc4XHVjOWMwIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJlNjhcdWFjMDQgXHVjZTc4XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjMTVcdWMyYTQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM5NTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmNmYyBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHViOWNjIFx1YmMxNlx1YzVkMFx1YzExYyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTUwXHVhYzAwIFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWFjMDBcdWM3YTVcdWM3OTBcdWI5YWNcdWI5N2MgXHViYmY4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVhZGY4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3JhdC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzNweDsgd2lkdGg6NTI0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhYzgwXHVjODE1IFx1YjNkOVx1YWRmOFx1Yjc3Y1x1YmJmOFx1YjI5NCBcdWM5NTAsIFx1ZDY4Y1x1YzBjOSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViYzE1XHVjMmE0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE1XHVjMmE0XHVjNzU4IFx1Y2M5OFx1Yzc0YyBcdWM3MDRcdWNlNThcdWM2NDAgXHViYzE1XHVjMmE0XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHViYWE4XHViNDUwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM2YzBcdWM5YzFcdWM3ODRcdWM3NDQgXHViOWNjXHViNGRjXHViODI0XHViYTc0IFx1Yzk1MFx1YWMwMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2YjBcdWI5YWNcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWFjZmMgXHViYzE1XHVjMmE0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBLICZsZTsgMTAsIEsgJmx0OyBOICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNmIwXHViOWFjXHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM3NzQgXHViZTY4XHVhYzA0IFx1Y2U3OCgmIzM5O3ImIzM5OylcdWM3NzhcdWM5YzAgXHVkNzcwIFx1Y2U3OCgmIzM5O3cmIzM5OylcdWM3NzhcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWNjOThcdWM3NGMgXHVjNzA0XHVjZTU4IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViYzE1XHVjMmE0XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0XHViMmU0LiAoMSAmbGU7IFIsIEMgJmxlOyBOLUsrMSk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNmMwXHVjOWMxXHVjNzc4IFx1ZDY5Zlx1YzIxOCBNICgxICZsZTsgTSAmbGU7IDEsMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE1XHVjMmE0XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKEwsIFIsIFUsIEQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5NTBcdWFjMDAgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzI5XHVkNWE1XHViMzAwXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzExOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNUQUtPUiIsImRlc2NyaXB0aW9uIjoiPHA+TWFkIHNjaWVudGlzdCBNYXRpamEgaXMgZXhwZXJpbWVudGluZyB3aXRoIGxhYiByYXRzLiBIZSBwdXQgb25lIGxhYiByYXQgaW50byBhIGNhZ2UsIHRoZSBib3R0b20gb2Ygd2hpY2ggaXMgYSBncmlkIG9mIE4mdGltZXM7TiBzcXVhcmUgY2VsbHMuIEVhY2ggc3F1YXJlIGlzIGNvbG91cmVkIHdoaXRlIG9yIHJlZC4gVGhlIHJvd3MgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBOIGZyb20gdG9wIHRvIGJvdHRvbTsgY29sdW1ucyBhcmUgbnVtYmVyZWQgbGVmdCB0byByaWdodC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHJhdCBjYW4gbW92ZSBpbiB0aGUgZm91ciBiYXNpYyBkaXJlY3Rpb25zIChsZWZ0LCByaWdodCwgdXAgYW5kIGRvd24pLCBidXQgaXMgYWZyYWlkIG9mIHJlZCwgc28gaXQgd2lsbCBuZXZlciBzdGVwIGludG8gYSByZWQgY2VsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgaGF2aW5nIHNwZW50IHNvbWUgdGltZSBpbiB0aGUgY2FnZSBhbmQgbGVhcm5lZCB3aGVyZSBpdCBjYW4gbW92ZSwgTWF0aWphIGNvdmVyZWQgdGhlIHJhdCBpbiBhIGJveCBvZiBzaXplIEsmdGltZXM7Sywgd2l0aCBzaWRlcyBvZiB0aGUgYm94IHBhcmFsbGVsIHRvIHRoZSBzaWRlcyBvZiB0aGUgY2FnZS4gRXZlbiB0aG91Z2ggaXQgaXMgbm93IHdhbGtpbmcgaW4gdGhlIGRhcmssIHRoYW5rcyB0byBpdHMgYXN0b3VuZGluZyBtZW1vcnksIHRoZSByYXQgc3RpbGwgb25seSBlbnRlcnMgd2hpdGUgY2VsbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoaWxlIHRoZSByYXQgbW92ZXMgdW5kZXIgdGhlIGJveCwgaXQgaXMgbm90IHBvc3NpYmxlIHRvIHNlZSBpdC4gRnJvbSBvdXRzaWRlIHlvdSBjYW4gb25seSBzZWUgd2hlbiB0aGUgYm94IG1vdmVzLCB3aGljaCBoYXBwZW5zIHdoZW4gdGhlIHJhdCBwdXNoZXMgYWdhaW5zdCBhbiBlZGdlIG9mIHRoZSBib3guIFdoZW4gdGhhdCBoYXBwZW5zLCB0aGUgYm94IG1vdmVzIGluIHRoZSBkaXJlY3Rpb24gaW4gd2hpY2ggdGhlIHJhdCBwdXNoZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcmF0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDo1MjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgc29sdXRpb24gdG8gdGhlIGV4YW1wbGUuIFRoZSBibGFjayBjaXJjbGUgaXMgdGhlIHJhdCwgd2hpbGUgdGhlIGdyZXkgcmVjdGFuZ2xlIHJlcHJlc2VudHMgdGhlIGJveC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWF0aWphIG1hZGUgbm90ZSBvZiB0aGUgaW5pdGlhbCBwb3NpdGlvbiBvZiB0aGUgYm94IGFuZCB0aGUgZGlyZWN0aW9ucyBpbiB3aGljaCBpdCBtb3ZlZC4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHRpbWVzIHRoZSByYXQgbWlnaHQgaGF2ZSBtb3ZlZCB0byBjYXVzZSB0aGUgYm94IHRvIG1vdmUgbGlrZSBpdCBkaWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBLICZsZTsgMTAsIEsgJmx0OyBOICZsZTsgMTAwKSAmbmRhc2g7IHRoZSBkaW1lbnNpb25zIG9mIHRoZSBjYWdlIGFuZCBvZiB0aGUgYm94LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHN0cmluZyBvZiBOIGNoYXJhY3RlcnMsIGVhY2ggb2YgdGhlbSBlaXRoZXIgJiMzOTt3JiMzOTsgb3IgJiMzOTtyJiMzOTssIHRoZSBjb2xvdXIgb2Ygb25lIGNlbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDEgJmxlOyBSLCBDICZsZTsgTiZtaW51cztLKzEpLCB0aGUgcm93IGFuZCBjb2x1bW4gb2YgdGhlIHVwcGVyLWxlZnQgY29ybmVyIG9mIHRoZSBib3ggaW4gaXRzIGluaXRpYWwgcG9zaXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBNICgxICZsZTsgTSAmbGU7IDEgMDAwIDAwMCksIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIGJveCBtb3Zlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhIHN0cmluZyBvZiBQIGxldHRlcnMsIHRoZSBkaXJlY3Rpb25zIGluIHdoaWNoIHRoZSBib3ggbW92ZWQuIEVhY2ggbGV0dGVyIGlzIG9uZSBvZiAmIzM5O0wmIzM5OywgJiMzOTtSJiMzOTssICYjMzk7VSYjMzk7IGFuZCAmIzM5O0QmIzM5Oy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiB0aW1lcyB0aGUgcmF0IG1pZ2h0IGhhdmUgbW92ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==