탈옥

'+'와 '*'로 표시된 격자에서 같은 기호의 이웃한 칸으로만 이동할 수 있을 때, 입구 칸에서 출구 칸에 도달할 수 있는지 판정한다.

쉬움3그래프BFS행렬아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

교도소가 미로 모양으로 지어졌다. 미로는 + 또는 *가 적힌 오두막으로 이루어진다. 두 오두막이 변 하나를 공유하면 서로 이웃한다. + 오두막에 있으면 이웃한 + 오두막으로만 이동할 수 있고, * 오두막에 있으면 이웃한 * 오두막으로만 이동할 수 있다.

미로는 가로 길이가 LL, 세로 길이가 WW인 직사각형이다. 오두막의 위치는 가로 좌표와 세로 좌표로 나타낸다. 가로 좌표는 왼쪽에서부터 11부터 LL까지, 세로 좌표는 아래쪽에서부터 11부터 WW까지 센다.

미로의 오두막은 모두 입구지만 출구는 하나뿐이다. 미로의 모양과 죄수가 있는 입구 오두막, 출구 오두막이 주어진다. 죄수가 출구 오두막까지 갈 수 있는지 판정하라.

입력

첫 줄에 테스트 케이스의 개수 PP가 주어진다.

각 테스트 케이스의 첫 줄에는 자연수 여섯 개 LL, WW, AA, BB, CC, DD가 공백으로 구분되어 주어진다.

  • LL은 미로의 가로 길이, WW는 미로의 세로 길이이다.
  • AABB는 죄수가 있는 입구 오두막의 가로 좌표와 세로 좌표이다.
  • CCDD는 출구 오두막의 가로 좌표와 세로 좌표이다.

이어서 WW개의 줄에 각각 문자 LL개가 주어진다. 각 문자는 + 또는 *이다. 이 줄들은 미로의 위쪽부터 차례대로 주어지므로, ii번째 줄은 세로 좌표가 W+1iW+1-i인 오두막을 나타낸다.

1P201 \le P \le 20, 1L5001 \le L \le 500, 1W5001 \le W \le 500, 1A,CL1 \le A, C \le L, 1B,DW1 \le B, D \le W이고, 모든 테스트 케이스의 L×WL \times W 합은 250000250000 이하이다.

출력

각 교도소마다 죄수가 탈출할 수 있으면 YES, 그렇지 않으면 NO를 한 줄에 하나씩 출력한다.