아이가 설계하는 아이

세 개의 격자 그림이 주어질 때, 처음 두 그림의 XOR이 세 번째 그림과 평행 이동으로 일치하도록 두 번째 그림의 이동을 찾는다.

어려움8구현문자열 매칭완전 탐색해시맵아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

케빈과 킴벌리는 이마에 주근깨가 있다.

둘은 각자 종이에 자기 주근깨 그림을 그렸다. 그림은 칸으로 나뉜 직사각형이고, 각 칸에는 주근깨가 있거나 없다.

둘은 나중에 결혼해서 아이를 낳으면 그 아이의 주근깨 그림이 다음 과정으로 정해진다고 농담한다. 두 그림을 평행이동해서 겹친 다음, 각 칸마다 두 사람 중 정확히 한 명만 그 자리에 주근깨가 있을 때 아이에게 그 칸의 주근깨가 생긴다.

두 사람의 그림과 아이에게 원하는 그림이 주어진다. 원하는 그림을 만드는 평행이동이 있는지 판정하고, 있다면 그 평행이동을 구하라.

한쪽을 평행이동해서 주근깨 위치가 서로 정확히 포개지면 두 그림은 같은 그림이다. 주근깨 둘레의 빈 행과 빈 열은 따지지 않는다.

입력

첫 줄에 케빈의 그림의 높이와 너비를 나타내는 정수 h1h_1, w1w_1 (1h1,w110001 \le h_1, w_1 \le 1000)이 주어진다. 다음 h1h_1개 줄에는 각각 *.로 이루어진 w1w_1개의 문자가 주어진다. *는 주근깨가 있는 칸, .는 주근깨가 없는 칸이다.

이어서 킴벌리의 그림이 같은 형식으로 주어진다. 높이 h2h_2와 너비 w2w_2의 범위는 위와 같다.

마지막으로 아이에게 원하는 그림이 같은 형식으로 주어진다. 높이 h3h_3과 너비 w3w_3의 범위도 위와 같다.

세 그림에는 각각 주근깨가 적어도 하나 있다.

출력

원하는 그림을 만들 수 있으면 첫 줄에 YES를, 만들 수 없으면 NO를 출력한다.

만들 수 있으면 둘째 줄에 정수 xxyy를 출력한다. 두 그림의 왼쪽 위 모서리를 맞춰 겹친 뒤 킴벌리의 그림을 오른쪽으로 xx칸 (xx가 음수면 왼쪽으로), 아래로 yy칸 (yy가 음수면 위로) 옮기고 위 과정을 적용하면, 그 결과를 평행이동해서 원하는 그림과 정확히 포갤 수 있어야 한다.

조건을 만족하는 (x,y)(x, y)가 여럿이면 xx가 가장 작은 것을 출력하고, 그런 것이 여럿이면 그중 yy가 가장 작은 것을 출력한다.