Cho một lưới gồm \(m\) hàng, \(n\) cột. Bạn Hiếu có \(k\) lọ sơn, và với mỗi ô, bạn sẽ chọn một trong số \(k\) màu để tô lên.

Từ một ô có thể đi sang các ô kề cạnh. Cụ thể hơn, từ ô \((x, y)\), chúng ta có thể đi sang ô \((x-1, y), (x, y-1), (x, y+1), (x+1, y)\).

Để đi từ ô có màu \(x\) sang ô có màu \(y\), chi phí dịch chuyển là \(c_{xy}\). Lưu ý, \(c_{xy}\) có thể khác \(c_{yx}\).

Hãy trả lời \(q\) câu hỏi, mỗi câu có dạng "Chi phí thấp nhất để đi từ ô \((u, v)\) tới ô \((x, y)\) là bao nhiêu?".

Input

• Dòng đầu chứa 3 số \(m, n, k\)
• \(m\) dòng sau, dòng thứ \(i\) chứa n số: \(a_{i1}, a_{i2}, \dots, a_{in}\) biểu thị màu của từng ô.
• k dòng sau, dòng thứ i chứa k số: \(c_{i1}, c_{i2}, \dots, c_{ik}\). \(c_{ij}\) là chi phí chuyển từ ô màu i sang ô màu j.
• Dòng tiếp theo chứa số \(q\)
• \(q\) dòng cuối, dòng thứ \(i\) chứa 4 số \(u_i, v_i, x_i, y_i\) biểu thị cho câu hỏi thứ \(i\).

Output

• In ra \(q\) dòng, mỗi dòng in ra đáp án của câu hỏi thứ \(i\).

Constants

• \(m, n \le 2000, k \le 4, q \le 10\)
• \(\forall 1 \le i \le m, 1 \le j \le n: a_{ij} \le 4\)
• \(\forall 1 \le i,j \le k: c_{ij} \le 10. \forall 1 \le i \le k: c_{ii} = 1\)

Example

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

2
5
2