Description

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:

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$.

Input Format

• 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 Format

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

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

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

1 2 2
1 3 3
2 1 1
2 2 2

12

Hint

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