The kingdom of Quadradonia is divided into provinces forming a grid-like pattern of R rows and C columns. Legend has it many wonderful things await discovery in some of the provinces, although it’s unclear if you can actually find the elusive solid form of water stories call “ice”, or if it’s just dragons. You are planning a trip through the kingdom to find out, but the roads are dangerous so you have to be very careful. To go from one province to another you would like to use the convenient escorted carriage system managed by the Interprovincial Communication & Peregrination Company (ICPC). In each province, the ICPC provides a heavily guarded carriage for you to travel to any other province in a rectangle containing it, at the same flat rate (which may however vary from one province to another). More formally, at the province in the i-th row and the j-th column you can rent an escorted carriage for a cost of Vij, allowing you to safely travel to any province at most Rij rows away from row i, and at most Cij columns away from column j (that is, having row number i′ and column number j′ with |i−i′|≤Rij and|j−j′|≤Cij). In your journey you want to visit N provinces p1, p2, ..., pN, in that order. Wandering around looking for adventures is an expensive business and your budget is limited, so you would like to spend as little as possible in transportation. Therefore, you would like to calculate the minimum cost of each leg of your trip, that is, the minimum cost of the carriages you have to rent to go from province pk to province pk+1, for k = 1, 2, . . . , N − 1. Input The input contains several test cases; each test case is formatted as follows. The first line contains three integers R, C and N, representing respectively the number of rows, the number of columns and the number of provinces you want to visit (1 ≤ R, C ≤ 500 and 2 ≤ N ≤ 5). Rows are numbered from 1 to R and columns are numbered from 1 to C. The next 3×R lines describe ICPC’s escorted carriage system by means of three groups of R lines each, with each line containing C integers. In the i-th line of the first group, the j-th number represents the cost Vij of renting a carriage in the province in row i and column j, while the corresponding numbers in the second and third group represent respectively Rij andCij (1≤Vij ≤1000,0≤Rij ≤Rand0≤Cij ≤C,fori=1,2,...,Randj=1,2,...,C). The next N lines describe the provinces p1, p2, ..., pN you want to visit, in the same order you want to visit them. The k-th of these lines describes the province pk with two integers Ik and Jk, indicating that pk is in row Ik and column Jk (1 ≤ Ik ≤ R and 1 ≤ Jk ≤ C for k = 1,2,...,N). Output For each test case in the input, output a line with N − 1 integers representing the minimum cost of each leg of your trip, or the value ‘-1’ if it is impossible to travel using ICPC’s escorted carriage system for that leg. More precisely, for k = 1, 2, . . . , N − 1, the k-th number must be the minimum cost of the carriages you have to rent to go from province pk to province pk+1 using ICPC’s escorted carriage system, or the value ‘-1’ if it is impossible to travel from province pk to province pk+1 with this system. Sample Input 345 1211 1534 1163
2/2 1233 3312 0001 1401 2301 4131 11 34 11 22 22 Sample Output 3 -1 1 0