Alice 在线性代数课上感到很无聊。她问老师为什么要学这些东西。线性代数在现实世界中真的有任何用处吗？

老师思考了几分钟，最终想出了这样一个场景。

假设一个精灵出现在你面前，并说如果你能计算出两个稀疏方阵 $A$ 和 $B$（矩阵元素为整数，模 $1006903069$）乘积的迹，他就会满足你三个愿望。

首先，你会说：“我希望我记得矩阵符号是怎么回事！”精灵会告诉你，$A$ 和 $B$ 是 $n \times n$ 的数字网格。在 $A$ 中，我们用 $a_{i,j}$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的元素。$B$ 的元素索引方式相同。这些矩阵是稀疏的，意味着（非正式地）相对于它们的大小，它们只有少数非零元素。

接下来，你会说：“那太好了，但我现在希望我记得怎么进行矩阵乘法！”精灵会提醒你，乘积 $AB$ 是另一个 $n \times n$ 矩阵 $C$，其元素 $c_{i,j}$ 使用以下公式计算：

$$c_{i,j} = \sum_{k=1}^{n} a_{i,k}b_{k,j}.$$

最后，你会说：“好吧，但我现在真的很希望我记得什么是迹！”精灵会提醒你，矩阵 $C$ 的迹等于其主对角线上元素的总和，即：

$$\text{tr}(C) = \sum_{t=1}^{n} c_{t,t}.$$

注意，如果 $A$ 和 $B$ 的所有元素都是整数，那么 $\text{tr}(AB)$ 也是一个整数。

精灵指出，他现在欠你 3 个愿望，因为他答应了你三个尚未兑现的愿望。每个愿望在授予时的价值为 6,264,067.84 比索，并且对于每一天未支付的愿望，需额外支付 30% 的利息。

你这个笨蛋！你因为在代数课上没专心听讲而欠了精灵一笔债！你摆脱困境的唯一方法是计算 $\text{tr}(AB) \pmod{1006903069}$ 并收回精灵承诺的最初三个愿望。

Alice 的老师道歉说他真的很努力了，但这确实是他能想到的线性代数在现实世界中唯一的应用。

但这对于 Alice 来说已经足够了，她现在非常渴望解决这个问题！

输入格式

矩阵是稀疏的，因此它们通过指定非零元素的位置和值来编码。形式上，矩阵 $A$ 的编码方式如下：

• 给定 $k_a$ 个三元组 $(i, j, x)$，表示 $a_{i,j} := x$。
• 所有给定的 $(i, j)$ 索引对都是不同的，输入中未明确提及的所有其他 $A$ 的元素隐式等于 0。

矩阵 $B$ 的编码方式类似，其 $k_b$ 个非零元素被显式列出。

输入的第一行包含一个整数 $n$，即矩阵的大小。

接下来是一行包含整数 $k_a$。然后是 $k_a$ 行，每行描述 $A$ 中的一个非零元素。每行包含三个空格分隔的整数 $i$、$j$ 和 $x$，表示 $a_{i,j} := x$。如果输入中未提及某个 $(i, j)$，则 $a_{i,j} := 0$。

接下来是一行包含整数 $k_b$。然后是 $k_b$ 行，每行描述 $B$ 中的一个非零元素。每行包含三个空格分隔的整数 $i$、$j$ 和 $x$，表示 $b_{i,j} := x$。如果输入中未提及某个 $(i, j)$，则 $b_{i,j} := 0$。

输出格式

输出一行，包含 $\text{tr}(AB) \pmod{1006903069}$ 的值。

数据范围

样例

输入 1

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

输出 1

27

说明 1

你可以根据定义验证： $$\text{tr}\left( \begin{bmatrix} 0 & 0 & 0 \\ 6 & 0 & 6 \\ 4 & 3 & 0 \end{bmatrix} \begin{bmatrix} 2 & 0 & 3 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix} \right) = \text{tr}\left( \begin{bmatrix} 0 & 0 & 0 \\ 12 & 6 & 18 \\ 8 & 0 & 21 \end{bmatrix} \right) = 0 + 6 + 21 = 27.$$