众所周知，对于一个三维物体，我们可以画出它的三视图——主视图、俯视图和左视图。我们可以将这些视图看作物体在不同平面上的投影。

例如，考虑如下的一些积木：

三视图可以画成这样：

但小兔子觉得这些视图太无聊了。他想以一种非常特殊的视角观察这些积木——左前视图。仍然考虑上面给出的积木。左前视图可以画成这样：

左前视图也可以看作是一个投影，该投影平面与左视图平面和主视图平面成 $45^\circ$ 角。下图展示了它在俯视图中的投影方式。

因此，如果我们把俯视图看作一个 $n$ 行 $m$ 列的网格，那么左前视图应该有 $n + m$ 列。

现在，小兔子想要搭建一些积木以满足以下条件：

• 俯视图是一个 $n$ 行 $m$ 列的网格。每个方格至少要放置一块积木。
• 左前视图的每一列从左到右的高度分别为 $a_1, a_2, \dots, a_{n+m}$。
• 俯视图中第 $x_i$ 行第 $y_i$ 列的方格恰好有 $h_i$ 块积木。共有 $k$ 个这样的条件。

小兔子想知道有多少种不同的方法可以满足所有条件。由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n, m, k \le 10^5$)，分别表示俯视图的行数、列数以及条件的数量。$n$ 的总和、$m$ 的总和以及 $k$ 的总和均不超过 $10^5$。

第二行包含 $n + m$ 个整数 $a_1, a_2, \dots, a_{n+m}$ ($1 \le a_1, a_2, \dots, a_{n+m} \le 10^9$)，表示从左到右左前视图的高度。

接下来的 $k$ 行中，第 $i$ 行包含三个整数 $x_i, y_i, h_i$ ($1 \le x_i \le n, 1 \le y_i \le m, 1 \le h_i \le 10^9$)，表示俯视图中第 $x_i$ 行第 $y_i$ 列的方格恰好有 $h_i$ 块积木。保证所有的 $(x_i, y_i)$ 互不相同。

输出格式

对于第 $x$ 个测试用例，如果答案对 $10^9 + 7$ 取模的结果为 $y$，则输出 Case #x: y，每个结果占一行。

样例

样例输入 1

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

样例输出 1

Case #1: 72
Case #2: 2