题目描述

由于 BZOJ 的水题已经被 Lcomyn 大爷刷完了，所以机房的蒟蒻们决定再出一道水题给 lcomyn 刷。

正巧蒟蒻们最近做了 AHOI2007 密码箱，觉得这题实在太水了。稍微加强一下下依然还是很水的，所以决定把数据范围开大一点送给 Lcomyn 切。

求方程 $x ^ 2 \equiv 1 \pmod n$ 的解，$x$ 为小于 $n$ 的非负整数。

输入格式

一行一个数 $n$。

输出格式

如果方程无解输出 None，否则就按从小到大的顺序输出所有解，两个数之间用空格隔开，行末无多余空格。

样例输入

5

样例输出

1 4

提示

对于 $100\%$ 的数据，$1 \le n \le 10^{18}$。

题目来源

By TA