Background

Translated from XXVIII Olimpiada Informatyczna - Stage III Suma liczb pierwszych.

d2t3。

Problem Description

You are given a number $n$. Find $l, r$ such that the sum of all prime numbers in the interval $[l, r]$ equals $n$.

If there are multiple solutions, any one is acceptable. If there is no solution, output NIE.

Input Format

One line containing one positive integer $n$.

Output Format

If there is a solution, output one line with two positive integers $l, r$, your answer.

If there is no solution, output NIE.

15

3 7

9992

4993 4999

100000000

NIE

1000000007

1000000007 1000000007

99999999996

295693 1693067

Hint

For all testdata, $1\leq n\leq 10^{11}$.

Constraints

Translated by ChatGPT 5