Joc

Cerință

Micul Gates este din ce în ce mai priceput în ceea ce privește numerele prime, astfel încât domnul profesor de matematică îi propune următorul joc: se consideră un număr construit prin alipirea primelor $k$ numere prime, în ordinea crescătoare a acestora. Ajută-l tu să câștige jocul, rezolvând următoarele cerințe:

1. Câte numere impare au fost alipite șirului?
2. Care este suma numerelor care au fost alipite?
3. Se numerotează pozițiile cifrelor numărului format din alipirea celor prime, începând de la $1$. Pentru $p$ poziții date de profesor, Micul Gates trebuie să determine numărul prim din care provine cifra aflată pe fiecare dintre aceste poziții.

Date de intrare

Pe prima linie a fișierului de intrare joc.in se găsește numărul $c$, care poate fi doar $1$, $2$ sau $3$ și corespunde cerinței care trebuie rezolvată.

Dacă cerința este $1$ sau $2$, pe a doua linie din fișierul joc.in se află un număr natural nenul $k$, reprezentând numărul de numere prime care sunt alipite.

Dacă cerința este $3$, pe a doua linie se află două numere naturale nenule, $k$ – numărul de numere prime care vor fi alipite și $p$ – numărul de poziții date de profesor, separate prin câte un spațiu. Pe a treia linie se află $p$ numere naturale reprezentând câte o poziție $poz$ în numărul format prin alipirea celor $k$ numere prime.

Date de ieșire

Dacă cerința este $c=1$, pe prima linie din fișierul joc.out se găsește un număr corespunzător răspunsului la cerința $1$.
Dacă cerința este $c=2$, pe prima linie din fișierul joc.out se găsește un număr corespunzător răspunsului la cerința $2$.
Dacă cerința este $c=3$, fișierul joc.out va conține pe prima linie $p$ numere separate prin câte un spațiu, fiecare număr reprezentând numărul prim din care provine cifra aflată la poziția poz, conform cerinței.

Restricții și precizări

• $1 \leq k \lt 50 \ 000$;
• $1 \leq p \leq 100 \ 000$;
• $1 \leq$ poz $\leq$ lungimea numărului format;
• Pentru $15$ puncte, cerința este $c=1$;
• Pentru alte $25$ de puncte, cerința este $c=2$;
• Pentru alte $60$ de puncte, cerința este $c=3$. Dintre acestea, pentru $30$ de puncte $k \leq 1 \ 000$;
• Se garantează că există mereu o soluție

Exemplul 1

joc.in

1
3

joc.out

2

Explicație

Cerința este $1$, $k=3$, deci se alipesc primele $3$ numere prime ($2$, $3$ și $5$). Dintre acestea, două sunt impare.

Exemplul 2

joc.in

2
3

joc.out

10

Explicație

Cerința este $2$, $k=3$, deci se alipesc primele $3$ numere prime ($2$, $3$ și $5$). Suma lor este: $2+3+5=10$

Exemplul 3

joc.in

3
5 3
1 5 6

joc.out

2 11 11

Explicație

Cerința este $3$, $k=5$, $p=3$.
Primele $5$ numere prime sunt: $2$, $3$, $5$, $7$, $11$.
Numărul construit este: 235711.

• Cifra de pe poziția $1$ este $2$, care provine din $2$.
• Cifra de pe poziția $5$ este $1$, care provine din $11$.
• Cifra de pe poziția $6$ este $1$ și provine din $11$.

Exemplul 4

joc.in

3
6 2 
8 3

joc.out

13 5

Explicație

Cerința este $3$, $k=6$, $p=2$.
Primele $6$ numere prime sunt: $2$, $3$, $5$, $7$, $11$ și $13$.
Numărul construit este: 23571113.

• Cifra de pe poziția $8$ este $3$, care provine din $13$.
• Cifra de pe poziția $3$ este $5$, care provine din $5$.