「SvR-1」Hack Function!

此时的 J-PSC 终于改成了 CF 赛制，小 C 迅速地 AK 了 Day 1，他发现 T2 function 比较好 Hack，题目的人话翻译如下： > 对于一个数 $A$，定义函数 $f(A)$ 如下： > > 1. 先把 $A$ 变成 $k$ 进制数 $B$。 > 2. 将 $A$ 替换为 $B$ 各位之和。 > 3. 返回执行第 1 步，直到 $B$ 是一位数为止。 > 4. 记 $x$ 表示 $A$ 此时的值（十进制）。 > 此时 $f(A) = x$，$f(A)$ 称作 $A$ 关于 $k$ 的**位和函数**。 > > 给定 $k, l, r, p$，求出 $\sum_{i = l}^r f(i^i) \bmod p$ 的值。 > > **特别地，当 $\sum_{i = l}^r f(i^i) = p$ 时，输出 $\texttt{perfect}$。** 小 C 迅速秒了该题，当他翻看别人的代码时，发现他们用的全是暴力枚举。（因为机子跑得飞快） 好不容易看到一个人，他的代码里竟然没有一个 $\texttt{perfect}$！但由于数据过弱，竟然让他 pp 了。 小 C 突然脑子一热，忘记了怎么构造 Hack 数据，所以他通过 Luogu 6.0 求助于你。 小 C 会告诉你 $k, p$ 的值，你需要构造一组 $l, r$，**使答案输出为 $\texttt{perfect}$**。 **若无法构造，输出两个 $\texttt{-1}$。** ## Input **本题有多组数据。** 第一行一个整数 $T$，表示数据组数。 接下来 $T$ 行，每行两个整数 $k,p$，含义如题所述。 ## Output 共 $T$ 行，对于每组数据，输出你构造的 $l,r$ 的值。 若有多组解，输出任意一组。 [samples] ## Background **Problem Number:** $\textit{63}$ 小 C 坐在 J-PSC2077 的赛场（题目可于下方「**题目附件**」处下载）上，他早已年逾七旬，但作为 Z 队选手还是成功参赛。 ## Note #### 样例 1 说明 - 对于数据 $1$，在 $k = 10$ 下，有 $f(2^2) = f(4) = 4$，$f(3^3) = f(27) = 9$，显然 $l = 2, r = 3$ 时原题应该输出 $\texttt{perfect}$。 - 对于数据 $2$，在 $k = 10$ 下，发现不可能满足要求。 - 对于数据 $3$，在 $k = 2$ 下，显然有 $f(1^1) = 1$，但该样例仅用于理解，根据数据规模与约定，我们保证 $k \geq 10$。 #### 数据规模与约定 $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \textbf{说明} & \textbf{时限} & \textbf{分值} \\\hline \textsf{1} & \text{无解} & 1\text{ s} & 3 \\\hline \textsf{2} & \text{有解且\textbf{\textsf{存在}}一组解使 }1\le l\le r\le 10^5 & 1\text{ s} & 16 \\\hline \textsf{3} & 1\le p\le 10^7 & 1\text{ s} & 34 \\\hline \textsf{4} & \text{无特殊限制} & 1.5\text{ s} & 47 \\\hline\hline \end{array} $$ 对于 $100\%$ 的数据，$10 \leq k \leq 10^3$，$1 \leq p \leq 10^8$，$1 \leq T \leq 10$。 保证时限在 std 用时的 $4$ 倍以上。 #### 评测说明 **本题开启 Special Judge 和捆绑测试。** 你需要保证 $l = r = -1$ 或 $1 \leq l \leq r \leq 10^{18}$ 且 $r - l \leq 10^{15}$，否则 SPJ 会将你的答案判为 $0$ 分。