numere

Se generează un şir de numere naturale ai cărui primi termeni sunt, în această ordine:

$1$, $2$, $3$, $5$, $8$, $3$, $1$, $4$, $5$, $9$, $4$, $3$, $7$, $0$, $7$, $7$, $4$,...

Cerință

Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale $n$, $k$ şi $p$ şi care să determine:

1. suma tuturor numerelor prime aflate printre primii $n$ termeni ai şirului din enunţ;
2. numărul de apariţii ale cifrei $k$ printre primii $n$ termeni ai şirului din enunţ;
3. cel de-al $p$-lea termen al şirului din enunţ.

Date de intrare

Fişierul nr.in conţine o singură linie pe care sunt scrise trei numere naturale $n$, $k$ şi $p$, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire nr.out va conţine $3$ linii:

1. pe prima linie, un număr natural reprezentând suma tuturor numerelor prime aflate printre primii $n$ termeni ai şirului din enunţ
2. pe a doua linie, numărul de apariţii ale cifrei $k$ printre primii $n$ termeni ai şirului din enunţ
3. pe a treia linie se va afişa cel de-al $p$-lea termen al şirului din enunţ

Restricții și precizări

• $3 \leq n \leq 100$;
• $0 \leq k \leq 9$;
• $1 \leq p \leq 2 \cdot 10^9$;
• Pentru rezolvarea cerinţei 1) se acordă 40% din punctaj, pentru cerinţa 2) 20% din punctaj şi pentru cerinţa 3) 40% din punctaj.
• Pentru teste în valoare de $50$ de puncte, $p \leq 10^7$;

Exemplu

nr.in

19 5 26

nr.out

47
3
8

Explicație

Primii $19$ termeni ai şirului sunt: $1$, $2$, $3$, $5$, $8$, $3$, $1$, $4$, $5$, $9$, $4$, $3$, $7$, $0$, $7$, $7$, $4$, $1$, $5$, Numere prime care apar printre aceşti termeni sunt $2$, $3$, $5$, $3$, $5$, $3$, $7$, $7$, $7$, $5$, suma lor fiind $47$. Valoarea $47$ se scrie pe prima linie a fişierului nr.out.

Pe linia a doua a fişierului nr.out se scrie numărul $3$, deoarece sunt $3$ termeni egali cu $k$ printre primii $n = 19$ termeni ai şirului.

Pe ultima linie a fişierului se scrie numărul $8$, deoarece cel de-al $p$-lea termen al şirului este $8$.