P2222 [HNOI2001] Matrix Product

Given matrices: $$A_{m\times n}=\begin{bmatrix}a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots &a_{m,n} \end{bmatrix} ,B_{n\times p}=\begin{bmatrix}b_{1,1} & b_{1,2} & \cdots & b_{1,p}\\ b_{2,1} & b_{2,2} & \cdots & b_{2,p} \\ \vdots & \vdots & \ddots & \vdots\\ b_{n,1} & b_{n,2} & \cdots &b_{n,p} \end{bmatrix}$$ When the number of columns of matrix $A$ equals the number of rows of matrix $B$, then $A$ and $B$ can be multiplied. Their product is an $m\times p$ matrix $D$: $$D_{m\times p}=\begin{bmatrix} d_{1,1} & d_{1,2} & \cdots & d_{1,p}\\ d_{2,1} & d_{2,2} & \cdots & d_{2,p} \\ \vdots & \vdots & \ddots & \vdots\\ d_{m,1} & d_{m,2} & \cdots & d_{m,p}\end{bmatrix}$$ where $d_{i,j}=\sum^n_{k=1} a_{i,k} \times b_{k,j}$, abbreviated as $D=A\times B$. Now three matrices $A, B, C$ are given. Most elements of these matrices are $0$; we call such matrices sparse matrices. Therefore, we use a triple $i, j, a$ to indicate that the value at row $i$ and column $j$ is $a$, and all other unspecified elements are $0$. In the computer, we only give triples of nonzero elements, and we use row-major order: first give the first row in increasing column order, then the second row in increasing column order, and so on. For example, for the matrix $\begin{bmatrix}1&0&0&0\\0&0&2&-1\\0&1&2&3\\0&0&0&0\end{bmatrix}$, its triple representation is: ```plain 1 1 1 2 3 2 2 4 -1 3 2 1 3 3 2 3 4 3 ``` Your task is to compute $D=A\times B\times C$.

- The first line contains two positive integers $x, y$, which are the row and column of the result to output. - The second line contains four integers $m, n, o, p$, meaning $A$ is an $m\times n$ matrix, $B$ is an $n\times o$ matrix, and $C$ is an $o\times p$ matrix. - From the third line onward, each line contains three integers that form one element in the triple representation of a matrix. There is one blank line between matrices. The order is matrices $A$, $B$, $C$.

Output a single integer: the value of the element in row $x$, column $y$ of $D$.

Constraints - For all test points, $1\le m,n,o,p\le 6\times 10^3$, and the total number of triples does not exceed $6\times 10^3$. - Numbers are separated by spaces. Translated by ChatGPT 5