#2156 진격의 Knight

1 s   128 MB  

Description

체스에는  Pawn, Rook, Bishop, Knight, Queen, King과 같은 기물들이 있다. DY는 특히 여러 기물 중에서 특이하게 움직이는 Knight를 제일 좋아한다.

Knight는 네 방향 중 아무 곳으로 두 칸 전진하고 전진한 방향을 기준으로 오른쪽이나 왼쪽으로 한 칸 더 이동한다. 하지만 특이한 걸 좋아하는 DY는 멋대로 Knight의 이동방식을 바꾸기로 했다.

처음 움직이는 칸수가 매번 달라진다. 1칸부터 시작해서 K칸까지 증가한 후 다시 1칸으로 돌아간다.

다음은 예시이다.

 

처음에는 1칸 이동하고 오른쪽이나 왼쪽으로 1칸 더 이동한다.  

다음에는 2칸 이동하고 오른쪽이나 왼쪽으로 1칸 더 이동한다.

K 번에서는 K 칸 이동하고 오른쪽이나 왼쪽으로 1칸 더 이동한다.

K+1 번에서는 1칸 이동하고 오른쪽이나 왼쪽으로 1칸 더 이동한다. 

 

 

Knight의 움직임 그림

(knight의 움직임 그림)

 

 

DY에게 두 체스판이 주어진다. 이 체스판 위에는 Knight가 하나씩 있다.

DY는 왼쪽의 체스판 위에 있는 Knight를 움직여서 오른쪽의 체스판에 있는 Knight의 위치로 옮길 수 있는지 궁금하다. DY를 도와주자.

Input

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

각 테스트케이스의 첫 번째 줄에는 Knight를 움직일 횟수 $N$($1 \leq N \leq 100$)과 최대 바뀌는 칸 $K$($1 \leq K \leq 7$)가 주어진다.  

두 번째 줄에는 왼쪽(l)과 오른쪽(r) 체스판에 Knight들의 위치가 다음과 같은 방식으로 주어진다.

 

RlDl RrDr

 

R은 가로축을 나타내는 알파벳으로 왼쪽부터 a부터 h까지 주어진다.  

D는 세로축을 나타내는 숫자로 아래쪽부터 1부터 8까지 주어진다.  

(R은 소문자, D는 숫자, 두 Knight 위치는 공백으로 구분한다.)

 

T  

N1 K1

RlDl RrDr

N2 K2

RlDl RrDr

NT  KT

RlDl RrDr

Output

각 테스트 케이스마다 왼쪽의 Knight를 n번 움직여서 오른쪽의 Knight 위치로 옮길 수 있다면 Yes, 없다면 No를 출력한다.

Sample Input

Sample Output

2
1  1
a1 b1
1  1
a1 b2
No
Yes

Source

2013 Ajou Programming Contest