当前没有测试数据。

题目描述

Here is another simple problem: Given n points in the 2-dimensional plane, please calculate the area of the convex hull.

However, as you might already have guessed, the value of n is very large! So you'll use the following generator to generate all those points:

You are given nine integers $x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n$. There are two recursive equations: $x_i= (a_x * x_{i-1} + b_x) \mod p_x$ and $y_i= (a_y * y_{i-1} + b_y) \mod p_y$​ for all 0 < i < n. The given n points are $(x_i, y_i)$ for $0 \le i < n$.

输入格式

The input consists of only one line. This line contains nine integers in the following order: $x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n$.

• $0 \le x_0, a_x, b_x < p_x < 2 \times 10^5$

• $0 \le y_0, a_y, b_y < p_y < 2 \times 10^5$

• $3 \le n \le 10^{18}$

• There may be multiple points in the same position

输出格式

Please output one integer denoting the area of the convex hull (of the generated n points) multiplied by 2.

It can be proved that two times such area is always an integer.

样例

样例输入 1

2 3 4 5 6 7 8 9 10

样例输出 1

28

样例输入 2

123 193 37 59 31 128 195777 193241 12345678

样例输出 2

75659192744