这个问题在某些国家可能广为人知，但如果没人提出，其他国家又如何了解这类问题呢？

平面上有 $n$ 个点，其中第 $i$ 个点 $(x_i, y_i)$ 具有值 $\mathbf{d}_i \in D$。给定两个集合 $D$ 和 $O$，具有以下性质：

• $D$ 中存在一个特殊元素 $\varepsilon_D$。
• $O$ 中存在一个特殊元素 $\varepsilon_O$。
• 给定一个二元运算 $+ : D \times D \to D$，具有以下性质：
  • $\forall a, b \in D, a + b = b + a$
  • $\forall a, b, c \in D, (a + b) + c = a + (b + c)$
  • $\forall x \in D, x + \varepsilon_D = \varepsilon_D + x = x$
• 给定一个二元运算 $\cdot : O \times D \to D$，具有以下性质：
  • $\forall a, b \in O, x \in D, (a \cdot b) \cdot x = a \cdot (b \cdot x)$
  • $\forall a \in O, x, y \in D, a \cdot (x + y) = a \cdot x + a \cdot y$
• 给定一个二元运算 $\cdot : O \times O \to O$，具有以下性质：
  • $\forall a, b, c \in O, (a \cdot b) \cdot c = a \cdot (b \cdot c)$
  • $\forall x \in O, x \cdot \varepsilon_O = \varepsilon_O \cdot x = x$

在本题中，我们将 $D$ 视为 $\mathbb{F}_p$ 上的所有 $3 \times 1$ 矩阵集合，$O$ 视为 $\mathbb{F}_p$ 上的所有 $3 \times 3$ 矩阵集合，其中 $p = 10^9 + 7$。也就是说，你可以将上述运算视为模 $10^9 + 7$ 下的常规矩阵加法和矩阵乘法。

现在给出 $m$ 个查询，形式为 $a \ b \ c \ o$：

• 令 $\mathbf{s} = \varepsilon_D$。
• 对于所有满足 $ax_i + by_i < c$ 的点 $i$，将 $\mathbf{s}$ 修改为 $\mathbf{s} + \mathbf{d}_i$，然后将 $\mathbf{d}_i$ 修改为 $o \cdot \mathbf{d}_i$。
• 返回 $\mathbf{s}$ 作为查询的答案。

作为数据结构大师，你需要执行所有查询并找到答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)，表示点的数量。 接下来的 $n$ 行，每行包含五个整数 $x_i, y_i, d_{i0}, d_{i1}, d_{i2}$，表示第 $i$ 个点的坐标及其值 $\mathbf{d}_i = \begin{bmatrix} d_{i0} \\ d_{i1} \\ d_{i2} \end{bmatrix}$。 下一行包含一个整数 $m$ ($1 \le m \le 1.5 \cdot 10^4$)，表示查询的数量。

接下来的 $m$ 行，每行包含十二个整数 $a, b, c, o_{00}, o_{01}, o_{02}, o_{10}, \dots, o_{22}$。注意实际的 $o = \begin{bmatrix} o_{00} & o_{01} & o_{02} \\ o_{10} & o_{11} & o_{12} \\ o_{20} & o_{21} & o_{22} \end{bmatrix}$。

保证： $|x_i| \le 10^6, |y_i| \le 10^6$。 $|a_i| \le 10^3, |b_i| \le 10^3, b_i \neq 0, |c_i| \le 10^6$。 所有矩阵元素均在 $0$ 到 $10^9 + 6$ 之间（含边界）。 对于所有 $1 \le i \le m$ 和 $1 \le j \le n$，$a_ix_j + b_iy_j \neq c_i$。 * 对于所有 $1 \le i \le m$ 和 $1 \le j \le m$，$\left( \frac{a_i}{b_i}, \frac{c_i}{b_i} \right) \neq \left( \frac{a_j}{b_j}, \frac{c_j}{b_j} \right)$。

输出格式

对于每个查询，输出一行，包含三个整数 $s_0, s_1, s_2$，表示 $\mathbf{s} = \begin{bmatrix} s_0 \\ s_1 \\ s_2 \end{bmatrix}$。

样例

输入 1

5
1 1 2 3 4
12 12 4 6 1
1 12 5 1 2
12 1 1 5 5
6 6 2 0 3
3
1 1 4 1 1 2 3 4 5 2 3 4
1 1 400 1 3 4 2 1 2 3 4 5
-1 -1 -10 3 2 1 4 6 5 4 3 2

输出 1

2 3 4
25 50 40
92 58 139

说明

注意，该解法不依赖于题目中提到的矩阵加法/乘法之外的其他性质。将 $D$ 和 $O$ 定义为矩阵集合仅是为了测试方便（因为我们无法使用交互库）。