题目描述

如你所知，复数通常表示为实部和虚部之和。$3 + 2i$ 就是一个例子，其中 $3$ 是实部，$2$ 是虚部，$i$ 是虚数单位。

给定一个素数 $p$ 和一个正整数 $n$，你的程序需要输出满足以下条件的所有复数的乘积：

• 实部和虚部都是小于等于 $n$ 的非负整数。
• 实部和虚部中至少有一个不是 $p$ 的倍数。

例如，当 $p = 3$ 且 $n = 1$ 时，满足条件的复数有 $1$（即 $1 + 0i$）、$i$（即 $0 + 1i$）和 $1 + i$（即 $1 + 1i$），这些数的乘积，即 $1 \times i \times (1 + i)$，等于 $-1 + i$。

输入

输入包含一个测试用例，格式如下：

其中，$p$ 是小于 $5 \times 10^5$ 的素数。$n$ 是小于等于 $10^{18}$ 的正整数。

输出

在一行中输出两个用空格分隔的整数。当所有满足条件的复数的乘积为 $a + bi$ 时，第一个整数是 $a$ 模 $p$ 的结果，第二个整数是 $b$ 模 $p$ 的结果。这里，$x$ 模 $y$ 的含义是介于 $0$ 和 $y - 1$（包括两端）之间的整数 $z$，使得 $x - z$ 能被 $y$ 整除。

正如题目描述中所示，当 $p = 3$ 且 $n = 1$ 时，需要计算的乘积是 $-1 + i$。然而，由于 $-1$ 模 $3$ 等于 $2$，所以示例输出中显示的是 $2$ 和 $1$。

3 1

2 1

5 5

0 0 

499979 1000000000000000000

486292 0