Thị trường thức uống giải khát là một trong những thị trường cạnh tranh gay gắt nhất. Các công ty ngoài cải thiện chất lượng sản phẩm thì còn phải liên tục thực hiện khảo sát thực tế để điều tra về nhu cầu và thị hiếu của khách hàng. Thành phố NQ vốn là một thành phố phát triển mạnh về du lịch và giải trí, nên đây là một trong những địa điểm quan trọng bậc nhất với các công ty kinh doanh nước uống giải khát. Thành phố có thể được xem là một bảng gồm ~n * m~ khu vực hình vuông với ~n~ hàng ngang đánh số từ ~1~ tới ~n~ và ~m~ hàng dọc đánh số từ ~1~ tới ~m~, khu vực ở hàng ~i~ cột ~j~ được gọi là khu vực ~(i, j)~.Ở mỗi khu vực đều có một và chỉ một máy bán hàng tự động. Mỗi máy này sẽ chỉ bán duy nhất một loại nước uống. Dĩ nhiên một loại nước uống sẽ chỉ thuộc quyền sở hữu của đúng một công ty nào đấy. Hàng tuần, mỗi công ty có thể sẽ cử một nhân viên của mình đi khảo sát thị trường. Nhân viên này sẽ xuất phát ở khu vực ~(1, 1)~, đi qua một số khu vực, và dừng lại ở khu vực ~(n, m)~. Trong một bước, họ có thể di chuyển sang khu vực kề cạnh với khu vực hiện tại họ đang đứng và khu vực này phải nằm trong phạm vi thành phố. Khi đến một khu vực nào đó, nếu như máy bán hàng ở khu vực này bán loại nước uống mà thuộc quyền quản lý của công ty chủ quản của họ thì họ sẽ tiến hành thu thập các dữ liệu kinh doanh của máy bán hàng này. Với giá xăng hiện nay đã lên tới 30000đ/1 lít, các nhân viên sẽ luôn đi theo đường đi ngắn nhất trong các chuyến khảo sát. Cho biết danh sách các công ty sẽ cử nhân viên đi khảo sát trong tuần này và những loại thức uống mà công ty đó sỡ hữu, hãy cho biết số lượng máy bán hàng lớn nhất mà nhân viên của mỗi công ty có thể thu thập dữ liệu.

Dữ liệu vào

• Dòng đầu tiên gồm 3 số nguyên dương ~n, m, k~ lần lượt là số hàng, số cột của thành phố và số công ty sẽ cử nhân viên đi khảo sát tuần này.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương có giá trị không vượt quá ~n*m~. Số ở hàng ~i~ và cột ~j~ là số hiệu loại đồ uống được bán ở khu vực ~(i, j)~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ gồm một số nguyên dương ~p_i~ là số lượng đồ uống mà công ty thứ ~i~ sỡ hữu, sau đó là ~p_i~ số nguyên dương có giá trị không vượt quá ~n*m~ là số hiệu các loại đồ uống này.
• Dữ liệu đảm bảo các công ty là phân biệt.
• Các loại thức uống thuộc sở hữu của các công ty được liệt kê không nhất thiết phải được bán trong phạm vi thành phố và ngược lại các loại thức uống được bán trong phạm vi thành phố không nhất thiết phải thuộc sỡ hữu của bất kỳ công ty nào trong ~k~ công ty được liệt kê.

Dữ liệu ra

• Gồm ~k~ dòng, dòng thứ ~i~ là số lượng máy bán hàng lớn nhất mà nhân viên công ty thứ ~i~ có thể thực hiện thu thập dữ liệu.

Sample input

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

Sample output

3
4

Giải thích

Giới hạn

• 30% số test thỏa ~n, m, k \leq 10~, tổng các ~p_i~ không vượt quá ~100~
• 30% số test thỏa ~n, m, k \leq 100~, tổng các ~p_i~ không vượt quá ~10000~
• 40% số test thỏa ~n, m \leq 1000, k \leq 1000000~, tổng các ~p_i~ không vượt quá ~1000000~