你最喜欢的歌手即将举办告别演唱会，你绝对不能错过。

演唱会将在一个大厅举行，大厅共有 $n$ 行，行号从 $0$ 到 $n-1$，每行有 $m$ 个座位，座位号从 $0$ 到 $m-1$。

不幸的是，有 $k$ 个座位已经被预订了。这些座位由坐标对 $(r_1, s_1), (r_2, s_2), \dots, (r_k, s_k)$ 给出。对于每个 $i$（$1 \le i \le k$），第 $r_i$ 行的第 $s_i$ 个座位已无法预订。

你一定会去参加演唱会，但你不确定是否有朋友想一起去。你正在考虑购买同一行中若干个（至少一个）连续座位的方案。请问你一共有多少种这样的方案？

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$（$1 \le n, m \le 10^5$；$1 \le k \le n \cdot m$），分别表示音乐厅的维度和已预订座位的数量。

第二行包含三个整数 $r_1, a_r$ 和 $b_r$（$0 \le r_1, a_r, b_r < n$）。

第三行包含三个整数 $s_1, a_s$ 和 $b_s$（$0 \le s_1, a_s, b_s < m$）。

由于输入数据可能非常大，采用以下方式编码：给出 $r_1$ 和 $s_1$ 的值，对于每个 $i$（$2 \le i \le k$），$r_i$ 和 $s_i$ 的值可以通过以下公式计算得出：

$$r_i = (r_{i-1} \cdot a_r + b_r) \pmod n$$ $$s_i = (s_{i-1} \cdot a_s + b_s) \pmod m$$

所有坐标对 $(r_i, s_i)$ 均不相同。

输出格式

输出一个整数，表示购买同一行中若干个连续座位的方案总数。

样例

样例输入 1

3 4 3
1 2 0
2 1 1

样例输出 1

18

样例输入 2

22 13 41
7 12 14
5 8 1

样例输出 2

1195

说明

在第一个样例中，座位 $(1, 2), (2, 0)$ 和 $(1, 1)$ 已被占用。第 $0$ 行有 $10$ 种购买方案，第 $1$ 行有 $2$ 种方案，第 $2$ 行有 $6$ 种方案。总和为 $10 + 2 + 6 = 18$。