Pell方程

给定 Pell 方程

$$X^2-DY^2=1$$

求该方程最小的正整数解 $(x,y)$。

输入保证 $D$ 不是完全平方数，因此方程一定存在正整数解。

输入格式

输入仅一行，包含一个整数 $D$。

输出格式

输出两个正整数 $x,y$，表示方程的最小正整数解，两个整数之间以一个空格分隔。

样例输入

3

样例输出

2 1

数据范围

• $1\le D\le 100001$；
• $D$ 不是完全平方数。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3

输出

2 1