Ciel and Communications System

All submissions for this problem are available.
Ciel has N restaurants on a long straight road.
The coordinate of the ith restaurant is X_{i}, and X_{1} ≤ X_{2} ≤ ... ≤ X_{N}.
Note that more than one restaurant can have the same coordinate. (They may be in the same building.)
When the ith restaurant communicates with the jth restaurant (i < j), a bit strange method is used.
In the method, some towers are used.
Each tower t has four parameters Y[t], R[t], C[t] and T[t].
Here Y[t] denotes the coordinate of the tower, R[t] denotes the range of the tower, C[t] denotes the cost for using the tower if the distance between the tower and the restaurant is 1, and T[t] denotes the type of the tower.
The ith restaurant can use the tower t if and only if X_{i}  Y[t] ≤ R[t].
Here T[t] is represented as an integer 1 ≤ T[t] ≤ M, where M is the number of types.
For some security reasons, the kth restaurant can communicate with only the (k±1)th restaurant directly.
So, it is necessary that the kth restaurant communicates with the (k+1)th restaurant for all i ≤ k < j.
For each communication between the kth and (k+1)th restaurants, each restaurant chooses the newest available tower.
Let TOWER_{k} be the newest available tower for the kth restaurant, and let TYPE[k] be the type of TOWER_{k}.
The cost for the communication is C[TOWER_{k}] * Y[TOWER_{k}]  X_{k} + C[TOWER_{k+1}] * Y[TOWER_{k+1}]  X_{k+1}.
If TOWER_{k} ≠ TOWER_{k+1}, then additionally the cost U_{TYPE[k], TYPE[k+1]} is needed.
The total cost of the communication between the ith and jth restaurants is the sum of the cost of the communication between the kth and (k+1)th restaurants over all i ≤ k < j.
If there should exist some i ≤ k ≤ j such that the kth restaurant has no available towers, the communication is impossible.
Now Ciel has the history of communications and constructions of towers.
Your task is to calculate the cost for each communication in the history.
In the beginning of the history, you should assume that there are no towers.
Input
The first line contains an integer N, M and Q, where Q denotes the number of the lines of the history.
Then next line contains N integers, where the ith integer denotes X_{i}.
Then next M lines contain M integers, where the jth integer of the ith line denotes U_{i,j}
Then next Q lines denote the history of communications and constructions.
The history is composed of the two types of lines.
The line "1 A B" (without quotes) means that the Ath restaurant communicates with the Bth restaurant.
The line "2 Y R C T" (without quotes) means that the tower whose parameters are Y, R, C and T is built.
Output
For each communication, print the cost.
If it is impossible, print "impossible" without quotes.
Constraints
2 ≤ N ≤ 100000 (10^{5})
1 ≤ M ≤ 50
1 ≤ Q ≤ 50000 (5 * 10^{4})
0 ≤ X_{1} ≤ X_{2} ≤ ... ≤ X_{N} ≤ 1000000000 (10^{9})
0 ≤ U_{i,j} ≤ 1000000000 (10^{9})
1 ≤ A < B ≤ N
0 ≤ Y ≤ 1000000000 (10^{9})
1 ≤ R ≤ 1000000000 (10^{9})
1 ≤ C ≤ 10000 (10^{4})
1 ≤ T ≤ M
U_{i,j} = U_{j,i}
Sample Input
5 2 6 1 3 5 7 10 1 3 3 1 1 1 2 2 5 5 1 1 1 1 2 1 1 4 2 4 1 2 1 1 1 4
Sample Output
impossible 6 10 16
Author:  laycurse 
Tester:  rajivka 
Editorial  http://discuss.codechef.com/problems/CIELWEB 
Tags  cook20, hard, laycurse 
Date Added:  27022012 
Time Limit:  0.432806 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions