在平面上有一个顶点分别为 $(-1, -1), (-1, 1), (1, 1)$ 和 $(1, -1)$ 的正方形。我们从点 $(-1, 0)$ 出发，以给定的斜率向正方形内部发射一条射线。射线在正方形边上的反射遵循反射角等于入射角的规律。

经过 $n$ 次反弹后，射线再次与正方形的某条边相交于一个具有有理数坐标的点。请以最简分数形式求出该点的坐标。

输入格式

输入包含一行，包含三个整数 $a, b$ 和 $n$ ($1 \le a, b, n \le 10^6, \gcd(a, b) = 1$)，其中射线初始路径的斜率为 $a/b$，且射线共发生 $n$ 次反弹。注意 $a$ 和 $b$ 互质。斜率的选择保证射线永远不会击中正方形的顶点。

输出格式

输出一行，包含四个由空格分隔的整数 $p, q, s$ 和 $t$，其中 $(p/q, s/t)$ 是射线最终击中正方形边的点，$p/q$ 和 $s/t$ 为最简分数，且分母 ($q$ 和 $t$) 为正数。如果坐标值为 $0$，则输出 $0\ 1$。

样例

输入 1

1 1 3

输出 1

-1 1 0 1

输入 2

1 7 4

输出 2

-1 1 6 7

输入 3

355 113 123456

输出 3

1 1 -58 113

说明

下图展示了第一个样例的情况：