Start: Jul, 07, 2018 08:30:00
2018年国服院程序设计基本技能达标考核(正式)
End: Jul, 07, 2018 11:00:00
Time elapsed:
Time remaining:

一起跳湖吧! 2271

Time Limit:  1 s      Memory Limit:   128 MB
Submission:117     AC:14     Score:3

Description

最近,一个名为「 冬天掉进北大未名湖是何种体验的知乎提问火遍了朋友圈。截至出题时,该问题下已有135个回答。受此问题影响,yybird也很想趁这个冬天,在未名湖结冰时,飞过去溜个冰,也体验下冬天落湖的快感!

于是yybird通过某种特殊的手段测量出了未名湖每块区域冰的承重量,他想知道当他从一个点沿着某个方向滑冰时,会不会落入湖中。

Input

先输入一个正整数T,表示测试数据的组数。

对于每组测试数据:

第一行是两个正整数mn(m和n均小于100)

2m+1行是一个由0~9的数字或#号构成的m*n矩阵a,代表未名湖的平面图。其中‘#’表示陆地,数字则表示该位置冰块的承重量(当承重量<yybird的体重时,yybird会落入湖中);

下一行是三个正整数xyw,表示yybird所站的起始位置a[x][y]以及yybird的体重w,系统保证起始点的承重量一定大于等于yybird的体重。

再下一行是一个字符串,表示yybird的滑行方向(不同字符串所代表的方向如下:“L”:向左;”R”:向右;“U”:向上;“D”:向下;“LU”:向左上;“LD”:向左下;“RU”:向右上;“RD”:向右下)。

Output

输出010表示yybird在滑行过程中不会掉入湖中,1表示会掉入湖中。

Samples

input
2 10 10 32######## 222222222# #21116141# #21212121# #311##121# #311##121# #41112111# #21121211# #11211151# ########## 0 0 2 RD 10 10 32######## 222222222# #21116141# #21212121# #311##121# #311##121# #41112111# #21121211# #11211151# ########## 1 5 2 D
output
1 0

Hint

第一个测试数据,yybird从最左上角的点a[0][0]向右下方滑,滑过两格后到达a[2][2],此处承重量为1,小于yybird的体重2,因此yybird会掉入湖中。

第二个测试数据,yybird从点a[1][5]向下滑行,沿途的经过的冰块的承重量为6和2,均不小于yybird的体重,而当滑行到a[4][5]时,撞到陆地,yybird不会再继续滑行,因此整个过程yybird不会掉入湖中。