G. Unter

Unter

Mama ta te roagă să o suni pe mătuşa ta Valeria, fiindcă are nevoie de ajutorul tău. Mătuşa Valeria îţi spune că vrea să vorbeşti cu fiul ei, Hermecito, fiindcă ar dori să-ţi ceară o favoare. Oamenii ăştia nu au niciun respect pentru timpul tău.

Vărul Hermecito şi-a instalat recent o aplicaţie de tip ride-sharing şi a devenit şofer. După fiecare cursă, el primeşte un rating de la client, un număr natural din intervalul $[1, 5]$. Încercând să asigure securitatea clienţilor, aplicaţia nu îi arată lui Hermecito fiecare rating, ci îi arată media aritmetică a tuturor rating-urilor obţinute până în prezent. Această medie este truncată la $D$ zecimale (mai multe detalii la secţiunea Restricţii). Hermecito a fost suspicios de la început în legătură cu acest sistem de rating-uri, motiv pentru care şi-a notat media afişată după fiecare cursă. Acum îţi dă această listă ţie şi te întreabă dacă e posibil într-adevăr să existe un şir de rating-uri care produce aceste medii sau aplicaţia îl minte, conspirând împotriva sa.

Vărul Hermecito şi-a instalat recent o aplicaţie de tip ride-sharing şi a devenit şofer. După fiecare cursă, el primeşte un rating de la client, un număr natural din intervalul $[1, 5]$. Încercând să asigure securitatea clienţilor, aplicaţia nu îi arată lui Hermecito fiecare rating, ci îi arată media tuturor rating-urilor obţinute până în prezent. Această medie este rotunjită la $D$ zecimale. Hermecito a fost suspicios de la început în legătură cu acest sistem, motiv pentru care şi-a notat media afişată după fiecare cursă. Acum îţi dă această listă ţie şi te întreabă dacă e posibil într-adevăr să existe un şir de rating-uri care produce aceste medii sau aplicaţia îl minte, conspirând împotriva sa, ca toţi angajatorii săi de până acum.

Şi tu de ce ai avea ceva mai bun de făcut?
h2. Date de intrare

Fişierul de intrare $unter.in$ conţine pe prima linie valoarea $T$, reprezentând numărul de teste din fişier. Structura unui test este următoarea: pe prima linie se află valorile $N$ şi $D$, reprezentând numărul de curse efectuate de Hermecito, respectiv numărul de zecimale la care sunt truncate mediile afişate de aplicaţie. Cea de a doua linie conţine $N$ valori, reprezentând şirul de medii: a $i$-a valoare din şir reprezintă media ratingului pentru primele $i$ curse, truncată la $D$ zecimale.

Fişierul de intrare $unter.in$ conţine pe prima linie valoarea $T$, reprezentând numărul de teste din fişier. Structura unui test este următoarea: pe prima linie se află valoareile $N$ şi $D$, reprezentând numărul de curse efectuate de Hermecito, respectiv numărul de zecimale la care sunt rotunjite mediile afişate de aplicaţie. Cea de a doua linie conţine şirul $M$: a i-a valoare din şirul $M$ reprezintă media ratingului pentru primele $i$ curse, rotunjită la $D$ zecimale.

h2. Date de ieşire

În fişierul de ieşire $unter.out$ se vor afla $T$ linii. Fiecare linie va conţine şirul $DA$, în cazul în care şirul corespunzător de medii este posibil in condiţiile date sau $NU$, în caz contrar.

În fişierul de ieşire $unter.out$ se vor afla $T$ linii. Fiecare linie va conţine şirul "DA", în cazul în care şirul corespunzător de medii este posibil in condiţiile date sau $NU$, în caz contrar.

h2. Restricţii

* $1 ≤ T ≤ 30$
* $1 ≤ D ≤ 5$
* Suma valorilor lui $N$ în cadrul aceluiaşi fişier de intrare va fi maxim $300.000$.

* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 100.000$
* $1 ≤ D ≤ 6$

* Fiecare număr din şirul de medii va conţine exact $D + 2$ caractere: O primă cifră în intervalul $[1, 5]$, un punct, respectiv $D$ cifre în intervalul $[0, 9]$.

* Truncarea la $D$ zecimale păstrează doar primele $D$ zecimale ale unui număr. Spre exemplu, dacă $D = 2$, atât $4.337881$ cât şi $4.3301$ sunt rotunjite la $4.33$.

h2. Exemplu
table(example). |_. unter.in |_. unter.out |

| 3
3 1
1.0 3.0 3.3
2 2
4.27 5.00
3 1
1.0 2.0 4.0
| DA
NU
NU

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="unter") ==