自然数的阶乘是所有小于或等于该数的正整数的乘积。例如，4 的阶乘是 $1 \cdot 2 \cdot 3 \cdot 4 = 24$。长度为 $n$ 的“错误阶乘”与 $n$ 的阶乘类似，但它包含一个错误：其中一个整数比它本应有的值严格更小（但仍至少为 1）。例如，$1 \cdot 2 \cdot 2 \cdot 4 = 16$ 就是一个长度为 4 的错误阶乘。

给定长度 $n$、一个素数模数 $p$ 和一个目标余数 $r$，求出一个长度为 $n$ 的错误阶乘，使其除以 $p$ 的余数为 $r$。

输入格式

第一行包含三个整数 $n$、$p$ 和 $r$ ($2 \le n \le 10^{18}$，$2 \le p < 10^7$，$0 \le r < p$)，分别表示错误阶乘的长度、素数模数以及题目描述中的目标余数。

输出格式

如果不存在满足要求的错误阶乘，输出 “-1 -1”。否则，输出两个整数——错误的索引 $k$ ($2 \le k \le n$) 以及该索引处的值 $v$ ($1 \le v < k$)。如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

4 5 1

样例输出 1

3 2

样例输入 2

4 127 24

样例输出 2

-1 -1