색깔 타일 4

2018년에 일본에서 국제정보올림피아드(IOI)가 열립니다. 이를 기념하기 위해 IOI 위원회는 "약간 이상한 디자인"의 예술 작품을 만들어 대회장을 꾸미기로 했습니다. 위원회는 디자인을 JOI(Just Odd Inventions) 사에 맡겼고, JOI는 다음과 같이 제안했습니다.

• 작품은 $H \times W$ 칸의 직사각형 보드 위에 만든다. 보드는 $N$개의 타일로 채우며, 타일끼리는 겹치지 않는다.
• 타일 $i$ ($1 \le i \le N$)의 크기는 $1 \times 1$ 또는 $1 \times 2$이고, 색은 $C_i$이다.
• $1 \times 2$ 타일은 회전해서 $2 \times 1$ 타일로도 쓸 수 있다.

JOI는 타일의 종류까지만 제안했고, 타일을 어떻게 까는지는 정하지 않았습니다. 위원회는 타일 종류에 대한 JOI의 제안을 그대로 따르면서, 디자인의 아름다움이 최대가 되도록 타일을 까는 방법을 찾아야 합니다.

보드에서 두 타일이 칸의 변을 맞대고 있고 색이 각각 $j$, $k$이면, 그 변의 점수는 $A_{j,k}$입니다. 디자인의 아름다움은 이런 변 점수의 합입니다. 두 $1 \times 2$ 타일이 두 칸의 변을 공유하면 두 변의 점수를 각각 따로 더합니다. 아름다움이 최대가 되는 배치를 구하세요.

첫 줄에 네 정수 $H$, $W$, $K$, $N$이 빈칸으로 구분되어 주어진다. 보드는 $H \times W$ 칸이고, 색은 $K$가지이며, 타일은 $N$개이다.

$i$번째 줄($1 \le i \le N$)에는 두 정수 $S_i$, $C_i$가 주어진다. 타일 $i$의 크기는 $1 \times S_i$이고, 색은 $C_i$이다.

$j$번째 줄($1 \le j \le K$)에는 $K$개의 정수 $A_{j,1}, A_{j,2}, \ldots, A_{j,K}$가 주어진다. 색 $j$ 타일과 색 $k$ 타일이 변을 공유하면 그 점수는 $A_{j,k}$이다.

$N$줄을 출력한다. $i$번째 줄에는 타일 $i$를 놓는 방법을 적는다.

• $S_i = 1$이면 두 정수 $A_i$, $B_i$를 출력한다. 타일은 위에서 $A_i$번째 행, 왼쪽에서 $B_i$번째 열의 칸에 놓인다.
• $S_i = 2$이면 네 정수 $A_i$, $B_i$, $C_i$, $D_i$를 출력한다. 타일은 위에서 $A_i$번째 행, 왼쪽에서 $B_i$번째 열의 칸과, 위에서 $C_i$번째 행, 왼쪽에서 $D_i$번째 열의 칸을 덮는다.

모든 입력은 다음 조건을 만족한다.

• $1 \le H \le 100$
• $1 \le W \le 100$
• $1 \le K \le 100$
• $1 \le N \le 10000$
• $1 \le S_i \le 2$ ($1 \le i \le N$)
• $1 \le C_i \le K$ ($1 \le i \le N$)
• $H \times W = S_1 + S_2 + \cdots + S_N$
• $0 \le A_{j,k} \le 1000$ ($1 \le j \le K$, $1 \le k \le K$)
• $A_{j,k} = A_{k,j}$ ($1 \le j \le K$, $1 \le k \le K$)

이 입력 예시에서 보드 크기는 $3 \times 2$이고, 타일 4개를 사용합니다. 타일의 색과 크기는 다음과 같습니다.

아래 그림은 타일을 놓은 모습이며, 그림의 숫자는 타일 번호입니다.

이 배치의 아름다움은 26입니다.

• 타일 2(색 2)와 타일 4(색 1)가 변을 공유하므로 점수 7을 얻습니다.
• 타일 2(색 2)와 타일 1(색 1)이 변을 공유하므로 점수 7을 얻습니다.
• 타일 4(색 1)와 타일 1(색 1)이 변을 공유하므로 점수 2를 얻습니다.
• 타일 4(색 1)와 타일 3(색 3)이 변을 공유하므로 점수 5를 얻습니다.
• 타일 1(색 1)과 타일 3(색 3)이 변을 공유하므로 점수 5를 얻습니다.