题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Suma liczb pierwszych

如果一个自然数 $n$ 恰好只有两个不同的因数 $1$ 和 $n$，我们就称它为质数。例如，$6$ 不是质数（因为它能被 $2$ 整除），$1$ 也不是质数（因为它只有一个因数 $1$），但 $2$ 和 $7$ 是质数。

Bajtazar 特别喜欢质数。他在一张纸上写下了连续的质数序列：

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$$

他想从这个序列中挑选出一个连续的片段，使其和恰好等于他喜欢的数字 $N$。请你帮助他，编写一个程序，对于给定的数字 $N$，找出质数序列中一个连续的区间，使其和恰好等于 $N$。

输入格式

输入只有一行，包含一个自然数 $N$ $(1 \leq N \leq 10^{11})$，表示 Bajtazar 期望的和。

输出格式

输出只有一行，包含两个质数 $L$ 和 $R$ $(1 \leq L \leq R \leq N)$，表示质数序列中闭区间 $[L, R]$ 内的数字之和恰好等于 $N$。

如果存在多种解法，你的程序可以输出任意一种。如果解不存在，则应输出 NIE。

15

3 7

样例 2

见附加文件下 [sum1.in](file:sum1.in) 和 [sum1.out](file:sum1.out)。

该样例满足 $N=9992$，答案是 $[4993, 4999]$；

样例 3

见附加文件下 [sum2.in](file:sum2.in) 和 [sum2.out](file:sum2.out)。

该样例满足 $N=10^{8}$，答案是 NIE；

样例 4

见附加文件下 [sum3.in](file:sum3.in) 和 [sum3.out](file:sum3.out)。

该样例满足 $N=10^{9}+7$，答案是 $\left[10^{9}+7, 10^{9}+7\right]$；

样例 5

见附加文件下 [sum4.in](file:sum4.in) 和 [sum4.out](file:sum4.out)。

该样例满足 $N=10^{11}-4$，答案是 $[295693, 1693067]$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N \leq 10000$	$15$
$2$	$N \leq 10^{8}$	$20$
$3$	$N \leq 2 \cdot 10^{9}$	$40$
$4$	无附加限制	$25$