Description

在模 $p$ 意义下（$p$ 为奇质数），一个正整数 $x(1\le x\lt p)$ 可以是有理数 $\dfrac{a}{b}(a,b\ge 1,b\perp p)$ 的取模结果。

给定 $x$，求所有取模结果为 $x$ 的有理数 $\dfrac{a}{b}$ 中，$ab$（这里非模意义）最小的一个，若多个 $\dfrac{a}{b}$ 满足要求，请全部输出，按照 $a$ 为第一关键字，$b$ 为第二关键字排序。

Constraints and Subtasks

• $p\le 10^9$，且 $p$ 为质数。
• $0\lt x\lt p$。

其中，部分测试点有特殊性质：

Input

输入内容从标准输入给出，格式如下：

$ \boxed{\begin{aligned} & x {\quad} p \end{aligned}} $

Output

设有 $m$ 个 $\dfrac{a}{b}$ 满足要求，则输出 $m$ 行，每行两个正整数 $a,b$，用空格分隔。

Sample

4 5

1 4
4 1

499122177 998244353

1 2