You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

这确实只是一道简单的矩阵乘法……

Description

稀疏矩阵乘法在实际应用中十分重要，在本题中你将被要求实现关于它的一个简单算法。

给定一个$n\times m$的整系数稀疏矩阵$A\in M_{n\times m}(\mathbb{Z})$，以及一个$m\times n$的稀疏矩阵$B\in M_{m\times n}(\mathbb{Z})$，我们可以得到它们的乘积$C=AB\in M_{n\times n}(\mathbb{Z})$。

为了简单起见，稀疏矩阵利用COO形式（坐标形式）给出：对于矩阵$A$，我们给定一个$p$，表示矩阵$A$只有$p$个元素非零，然后我们将给出这$p$个非零元的具体信息；对于矩阵$B$，$q$个非零元也类似地给出。

由于$C$的尺寸可能很大，所以在本题中我们只关心它的迹，即$\text{tr }C=\sum\limits_{i=1}^nC_{ii}$。

Format

Input

第一行依次给出四个正整数$n,m,p,q$，其中$n,m$为矩阵的尺寸，其意义如题意所示。

接下来$p$行，每行三个整数$x_i,y_i,z_i$，每行表示$A$矩阵的一个非零元$A_{x_i,y_i}=z_i$，数据保证$1\le x_i\le n,1\le y_i\le m$，并且点对$(x_i,y_i)$两两不同。

接下来$q$行，每行三个整数$x_i,y_i,z_i$，每行表示$B$矩阵的一个非零元$B_{x_i,y_i}=z_i$，数据保证$1\le x_i\le m,1\le y_i\le n$，并且点对$(x_i,y_i)$两两不同。

Output

输出一行一个整数，表示乘积矩阵$C$的迹，即$\text{tr }AB$的值。

Samples

5 5 3 4
1 2 3
4 5 6
5 3 -6
2 4 9
5 3 8
3 5 -2
2 1 4

24

Limitation

$1\le n,m,p,q\le 10^5$

$|z_i|\le 10^6$

Explanation

$$A=\begin{pmatrix} 0 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 6\\ 0 & 0 & -6 & 0 & 0 \end{pmatrix}$$

$$B=\begin{pmatrix} 0 & 0 & 0 & 0 & 0\\ 4 & 0 & 0 & 9 & 0\\ 0 & 0 & 0 & 0 & -2\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 8 & 0 & 0 \end{pmatrix}$$

$$C=\begin{pmatrix} 12 & 0 & 0 & 27 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 48 & 0 & 0 \\ 0 & 0 & 0 & 0 & 12 \end{pmatrix}$$