LaLa 即将施展一个魔法兽召唤术。

LaLa 首先要创建一个召唤场，它关联着 3 个常量：零度 $M$、弹性 $E$ 和粘度 $V$。这样的召唤场记作 $F(M, E, V)$。

魔法兽召唤术是在召唤场内的一个召唤单元上进行的，该单元呈正方形，并关联着 3 个变量：边长 $L$、敏捷 $A$ 和智力 $I$。这样的召唤单元记作 $C(L, A, I)$。

如果 $L = 0$，则 $C(L, A, I)$ 处于零状态。否则，它处于正状态。 处于正状态的 $C(L, A, I)$ 的密度定义为 $(A \times I)/L^2$。

确定魔法兽召唤术是否会成功的难题需要进行极其繁重的计算，涉及求解一个关于 $9999999999$ 个变量的 $9999999999$ 阶偏微分方程组。幸运的是，LaLa 已经为你完成了所有的数学计算！

在召唤场 $F(M, E, V)$ 内，针对 $C(L, A, I)$ 的魔法兽召唤术成功，当且仅当 Note 部分伪代码定义的函数 valid(M, E, V, L, A, I) 返回 true。我们称这样的召唤单元为有效的。

有时，LaLa 对她拥有的召唤单元集合不满意，想要通过组合它们来生成新的单元。确定在 $F = F(M, E, V)$ 内组合两个有效召唤单元 $C_0 = C(L_0, A_0, I_0)$ 和 $C_1 = C(L_1, A_1, I_1)$ 的结果需要进行另一次繁重的计算，但谢天谢地，LaLa 又一次为你完成了所有的数学计算！

在 $F$ 内组合两个此类单元 $C_0$ 和 $C_1$ 的结果，记作 $\text{Combine}_F(C_0, C_1)$，由 Note 部分伪代码定义的函数 combine(M, E, V, L_0, A_0, I_0, L_1, A_1, I_1) 给出，该函数返回一个满足 $C(L_2, A_2, I_2) = \text{Combine}_F(C_0, C_1)$ 的三元组 $L_2, A_2, I_2$。在此处可以证明 $\text{Combine}_F(C_0, C_1)$ 也是有效的。注意，交换 $C_0$ 和 $C_1$ 的顺序会影响结果。

在 $F$ 内组合 $K \ge 3$ 个单元 $C_0, \dots, C_{K-1}$ 的结果通过递归给出： $$\text{Combine}_F(C_0, \dots, C_{K-1}) = \text{Combine}_F(\text{Combine}_F(C_0, \dots, C_{K-2}), C_{K-1})$$ 为了完整起见，我们定义 $\text{Combine}_F(C) = C$。

LaLa 意识到关于组合操作的一个非常特殊的性质，这使她能够高效地解决下面的区间密度查询问题。你能发现它吗？

给定一个召唤场 $F = F(M, E, V)$ 和一个包含 $N$ 个有效召唤单元的数组 $$C_0 = C(L_0, A_0, I_0), \dots, C_{N-1} = C(L_{N-1}, A_{N-1}, I_{N-1})$$ 编写一个程序来处理以下两类 $Q$ 次查询：

• 1 i L A I
  • 设置 $C_i \leftarrow C(L, A, I)$。
• 2 l r
  • 令 $R = \text{Combine}_F(C_l, \dots, C_{r-1})$。如果 $R$ 处于零状态，输出单个整数 $-1$。否则，输出 $R$ 的密度对 $M$ 取模的结果。此处，不可约分数 $p/q$（其中 $p$ 是非负整数，$q$ 是不能被 $M$ 整除的正整数）对 $M$ 取模定义为唯一的整数 $p \times q^{-1} \pmod M$，其中 $q^{-1}$ 是 $q$ 对 $M$ 的乘法逆元。可以证明，如果 $R$ 处于正状态，则在题目约束下，$R$ 的密度作为不可约分数的分母不能被 $M$ 整除。

输入格式

$M \ E \ V$ $N$ $L_0 \ A_0 \ I_0$ $\vdots$ $L_{N-1} \ A_{N-1} \ I_{N-1}$ $Q$ $q_0$ $\vdots$ $q_{Q-1}$

其中 $q_i$ 表示第 $i$ 次查询，格式如题目描述中所述。

输入满足以下约束： 所有输入数字均为整数。 $M$ 是一个满足 $900\,000\,000 \le M \le 1\,000\,000\,000$ 的质数。 $1 \le E, V \le 100$ $1 \le N, Q \le 100\,000$ 对于所有 $0 \le i < N$，有 $0 \le L_i, A_i, I_i < M$。 对于所有 $0 \le i < N$，$C(L_i, A_i, I_i)$ 在 $F(M, E, V)$ 内是有效的。 对于每次查询 1 i L A I，$0 \le i < N$，$0 \le L, A, I < M$，且 $C(L, A, I)$ 在 $F(M, E, V)$ 内是有效的。 对于每次查询 2 l r，$0 \le l < r \le N$。

输出格式

对于每类查询的第二种情况，在一行中输出答案。

样例

输入格式 1

998244353 1 2
3
2 998244352 3
4 998244351 6
4 929561374 68682991
7
2 0 2
2 0 3
2 1 3
1 1 6 9 998244350
2 0 2
2 0 3
2 1 3

输出格式 1

-1
748683259
156877648
748683265
499122176
342244251

说明

以下伪代码定义了召唤单元的有效性以及 Combine 操作。 两个函数均不修改其参数。

function VALID(M, E, V, L, A, I)
    if min(L, A, I) < 0 or M <= max(L, A, I) then
        return False
    end if
    /* 所有运算和比较均在模 M 下进行 */
    if L = 0 and (A + I != 0 or A = I) then
        return False
    end if
    return A^3 - A^2*L + 3*A^2*I + E*A*L^2 + 2*A*L*I + E*L^2*I + 3*A*I^2 - L*I^2 + I^3 != 0
end function

function COMBINE(M, E, V, L0, A0, I0, L1, A1, I1)
    Ensure VALID(M, E, V, L0, A0, I0)
    Ensure VALID(M, E, V, L1, A1, I1)
    /* 所有运算和比较均在模 M 下进行 */
    if L1 = 0 then
        return L0, A0, I0
    end if
    if L0 = 0 then
        return L1, A1, I1
    end if
    B0 <- (A0 + I0), B1 <- (I1 + A1) * L0
    C0 <- (A0 - I0) * L1, C1 <- (I1 - A1) * L0
    if B0 = B1 then
        return 0, 3, -3
    else
        Sum <- A0 + I0, Dif <- A0 - I0
        B <- 3 * Sum^2 + E * L0^2
        C <- 2 * Dif * L0
        D <- 2 * C * Sum * Dif
        E_val <- B^2 - 2 * D
        X <- C * E_val, Y <- B * (D - E_val) - 2 * C^2 * Dif^2
        return 2 * C^3, X + Y, X - Y
    end if
end function

作者附带了一个 C++ 实现，该实现提交后会得到“Time Limit Exceeded”判决，但它总能在有限时间内打印出正确答案。你可以在你的提交中重用该实现的部分内容。（如果你阅读的是打印版本，你可以在 eolymp 网站上的题目底部找到附件。）