Restricționare

Am fost luat în râs de două ori...

După multe zile de încercări și convingere, Maria a acceptat, în sfârșit, să se joace cu Buzdi. Fiind destul de inteligenți, aceștia au reușit să inventeze un nou joc numit restricționare. Buzdi a adus un șir $A$ de $N$ numere întregi, iar Maria a adus un șir $B$ de $N$ numere naturale. După aceasta, cei doi au definit operația de restricționare a unui număr $A_i \ (1 \leq i \leq N)$ astfel:

1. Se descompune $A_i$ în factori primi. Fie $f_1^{e_1} \cdot f_2^{e_2} \cdot ... \cdot f_K^{e_K}$ aceasta.
2. Fiecare exponent își schimbă valoarea dacă valoarea curentă a acestuia este mai mică decât $B_i$. Formal, $e_j = \min(e_j, B_i)$, pentru fiecare $1 \leq j \leq K$.

De exemplu, dacă $A_i = 360 = 2^3 \cdot 3^2 \cdot 5^1$ și $B_i = 1$, atunci, după aplicarea operației de restricționare, $A_i = 30 = 2^1 \cdot 3^1 \cdot 5^1$.
De asemenea, dacă $A_i = -360 = -2^3 \cdot 3^2 \cdot 5^1$ și $B_i = 1$, atunci, după aplicarea operației de restricționare, $A_i = -30 = -2^1 \cdot 3^1 \cdot 5^1$.
Prin convenție, după aplicarea operației de restricționare numerelor $1$, $-1$ sau $0$, acestea nu își vor schimba valoarea.

Cerință

1. Buzdi o provoacă pe Maria să rezolve următoarea cerință: Care este valoarea maximă din șirul $A$ înainte și după aplicarea operației de restricționare tuturor numerelor din șirul $A$?
2. Maria îl provoacă pe Buzdi să rezolve următoarea cerință: Care este numărul minim de numere cărora trebuie să le aplicăm operația de restricționare astfel încât suma oricărei subsecvențe din șirul $A$ nou obținut să fie mai mică sau egală decât $S$?

Cei doi trebuie să rezolve cerința primită de la celălalt pentru a nu fi luați in râs de abilitățile acestora de rezolvat probleme. Scopul vostru este să le rezolvați pentru a îi ajuta pe amândoi.

Date de intrare

Pe prima linie se află un număr natural $G$, reprezentând grupa de teste din care face parte testul respectiv. Pe următoarea linie se găsesc două numere naturale, $C$ și $N$, unde $C$ reprezintă cerința ce trebuie rezolvată. Pe următoarea linie se află $N$ numere întregi, separate printr-un spațiu, reprezentând numerele șirului $A$. Pe următoarea linie se află $N$ numere naturale, separate printr-un spațiu, reprezentând numerele șirului $B$. Dacă $C = 2$, atunci pe următoarea linie se află numărul întreg $S$.

Date de ieșire

Dacă $C = 1$, atunci pe prima linie se vor afla două numere întregi, separate printr-un spațiu, reprezentând soluția cerinței $1$.
Dacă $C = 2$, atunci pe prima linie se va afla un număr întreg, reprezentând soluția cerinței $2$.

Restricții și precizări

• Atenție! Această problemă a avut unele teste greșite în timpul concursului oficial. Suma punctajelor testelor greșite a fost redistribuită în mod egal pe toate celelalte teste, iar clasamentul a fost recalculat. Din fericire, acesta nu a fost afectat. Aceste teste au fost, ulterior, modificate, pentru ca soluțiile corecte să obțină punctajul corespunzător. Ne cerem scuze!
• $1 \leq N \leq 2 \cdot 10^5$.
• $-10^6 \leq A_i \leq 10^6$, pentru fiecare $1 \leq i \leq N$.
• $0 \leq B_i \leq 20$, pentru fiecare $1 \leq i \leq N$.
• $-10^{18} \leq S \leq 10^{18}$.
• O subsecvență a unui șir $A$ reprezintă o succesiune de numere aflate pe poziții consecutive în șirul $A$.
• Se garantează că pentru $C = 2$ există soluție.

• Pentru citirea și afișarea rapidă, se recomandă folosirea acestor linii de cod la începutul funcției main:

ios::sync_with_stdio(false);  
cin.tie(NULL);  
cout.tie(NULL);  

• Grupurile de teste sunt următoarele:

  G	Punctaj	Restricții
  0	0	Exemplele
  1	8	$C = 1$ și $A_i$ este număr prim, pentru fiecare $1 \leq i \leq N$
  2	30	$C = 1$ și $1 \leq N \leq 2000$
  3	10	$C = 1$
  4	3	$C = 2$ și $B_i = 20$, pentru fiecare $1 \leq i \leq N$
  5	22	$C = 2$ și $1 \leq N \leq 2000$
  6	27	$C = 2$

Exemplul 1

stdin

0
1
6
12 8 36 100 -1 60
1 1 2 1 0 1

stdout

100 36

Explicație

Fie $R$ șirul obținut după aplicarea operației de restricționare tuturor numerelor din șirul $A$. Atunci, $R$ = $[6, 2, 36, 10, -1, 30]$.
Observăm că cea mai mare valoare din șirul $A$ este $100$, iar cea mai mare valoare din șirul $R$ este $36$.

Exemplul 2

stdin

0
2                
6
12 8 36 100 -1000 60
1 1 2 1 0 1
60

stdout

2

Explicație

Este suficient să aplicăm operația de restricționare numerelor $8$ și $100$. Astfel, se poate demonstra că suma oricărei subsecvențe din șirul nou obținut este mai mică sau egală decât $60$.