Bobo 在 ICPCCamp 制作了一个非常长的数字序列 $(a_1, a_2, \dots, a_n)$，其中 $a_i = f(i)$，且 $$ f(i) = \left\{\begin{array}{ll} 1 & i \leq 0 \\ A \cdot f(i - 1) + B \cdot f(i - m) & i > 0 \end{array}\right..$$

现在他想提出 $q$ 个问题，第 $i$ 个问题是计算 $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$ 的和。 不幸的是，Bobo 唯一能使用的工具是一个老旧且损坏的 $4$ 位计数器。 在回答第 $i$ 个问题时，Bobo 会将计数器置为 $0$，并按 $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$ 的顺序将数字加到计数器中。

由于计数器损坏，将数字 $a$ 加到当前值为 $x$ 的计数器中，结果为 $[(x \oplus w_i) + a]\ \mathrm{mod}\ 16$。 注意，“$\oplus$”表示按位异或（XOR）。

Bobo 想知道最终的结果。

特别说明：时间限制非常紧，因此可能需要进行一些优化。尽量在最后时刻解决该问题。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含五个整数 $n, m, A, B, q$。 接下来的 $q$ 行中，第 $i$ 行包含三个整数 $l_i, r_i$ 和 $w_i$。

• $1 \leq n \leq 10^8$
• $2 \leq m \leq 10^5$
• $0 \leq A, B, w_i < 16$
• $1 \leq q \leq 13$
• $1 \leq l_i \leq r_i \leq n$
• 测试用例数量不超过 $10$。

输出格式

对于每个问题，输出一个整数，表示最终结果。

样例

样例输入 1

5 2 1 1 2
1 4 0
2 5 1

样例输出 1

2
15