물풍선

크레이지 아케이드 BNB의 캐릭터 ‘다오’는 수시로 놓이는 물풍선과 물풍선의 폭발을 피해 움직여야 한다. 다오가 움직이는 공간은 $H$행 $W$열의 격자로 표현되고, 격자에는 이동을 방해하는 $L$개의 블록이 놓여있다. 우리가 할 일은 다오가 시작 위치에서 도착 위치까지 안전하게 이동할 수 있는 경로를 찾는 것이다.

다오는 $1$턴부터 시작하여 매 턴에 상하좌우로 한 칸 이동할 수 있다. 원하는 만큼 움직이지 않고 제자리에 머물러 있는 것 또한 가능하다.

K개의 물풍선이 각각 정해진 턴이 시작할 때 정해진 위치에 놓인다. 물풍선이 다오가 있는 칸에 놓이는 것은 상관없지만, 다오가 이동하려는 칸에 물풍선이 있는 경우에는 그 칸으로 이동할 수 없다. 다오가 있는 칸에 물풍선이 놓였을 경우에도 제자리에 머물러 있을 수 있다.

매 턴이 끝날 때, 물풍선이 놓인 지 $3$턴 이상 지난 물풍선이 있다면 해당 물풍선이 폭발한다. 예를 들어, $2$턴이 시작할 때 놓인 물풍선은 $4$턴이 끝날 때 터진다. 물풍선이 폭발할 때 물풍선의 세기만큼 상하좌우로 물줄기를 내뿜는다. 물줄기가 나아가는 방향에 블록이 있다면 더 이상 나아가지 못하고 막히게 된다. 물줄기에 다른 물풍선이 닿으면 해당 물풍선 또한 폭발하게 된다. 물줄기가 닿는 공간에 다오가 있으면 다오는 물풍선에 갇히게 되어 이동에 실패하게 된다.

다오가 물줄기에 닿지 않고 도착 위치까지 안전하게 이동할 수 있는 최단경로를 구하는 프로그램을 작성하라. 도착 위치에 도착한 뒤에 물풍선이 폭발해서 물줄기에 닿더라도 성공한 것으로 생각한다.

입력 형식

첫째 줄에 격자의 행 수 $H$와 열 수 $W$가 주어진다. ($1 \le H, W \le 50$)

둘째 줄에 다오의 시작 위치 $R_s$, $C_s$와 도착 위치 $R_e$, $C_e$가 주어진다. 이는 다오의 시작 위치가 $R_s$행 $C_s$열이고 도착 위치가 $R_e$행 $C_e$열임을 의미한다. 시작 위치와 도착 위치는 서로 다르다.

셋째 줄에 이동을 방해하는 블록의 개수 $L$이 주어진다. ($0 \le L \le H \times W$)

다음 $L$개의 줄에는 각 블록의 위치 $R$, $C$가 주어진다. 이는 $R$행 $C$열에 블록이 있음을 의미한다. 모든 블록의 위치는 서로 다르다.

그 다음 줄에는 물풍선의 개수 $K$가 주어진다. ($0 \le K \le 5\,000$)

다음 $K$개의 줄에는 각 물풍선의 위치 $R$, $C$와 물풍선의 세기 $P$, 물풍선이 놓이는 턴 $T$가 주어진다. ($1 \le P \le 50$, $1 \le T \le 5\,000$) 이는 $T$번째 턴이 시작할 때 $R$행 $C$열에 세기가 $P$인 물풍선이 놓임을 의미한다. 물풍선은 $T$ 오름차순으로 주어진다. 물풍선은 블록이 있는 위치에 놓이지 않으며, 두 물풍선이 서로 겹치는 경우는 주어지지 않는다.

가능한 이동 방법이 존재하는 경우만 주어진다.

출력 형식

첫째 줄에 다오가 도착 위치까지 이동할 수 있는 최소 턴 수 $T$를 출력한다.

다음 $T$줄에 다오가 이동한 경로를 출력한다. $T$줄 중 $k$번째 줄에는 $k$번째 턴이 끝날 때 서 있어야 하는 위치의 행 번호와 열 번호를 출력한다.

예제

4 4
1 1 3 4
4
2 1
1 3
2 3
3 3
1
1 2 3 2

9
1 2
2 2
3 2
3 1
3 2
4 2
4 3
4 4
3 4

예제 설명

$2$턴이 시작할 때 $1$행 $2$열에 놓인 물풍선이 $4$턴이 끝날 때 터지면서 $4$행 $2$열까지 물줄기가 닿으므로, $4$턴이 끝날 때 다오는 $4$행 $2$열로 이동할 수 없고 $3$행 $1$열로 이동해야 한다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설