Računi - Državno

Đurica voli da obilazi restorane. Tokom godine je obišao puno restorana, i sad je baš ogladneo i zanima ga u koji sledeći da ode. U svim restoranima koje je Đurica posetio ukupno je naručio k različitih stavki, te se svaki račun može opisati kao id s₁ s₂ ... s_k.

Vrednost id je oznaka restorana. Svaka oznaka jedinstveno određuje jedan restoran, i svaki restoran je jedinstveno određen jednom oznakom. Vrednost si je 0 ako na tom računu ne postoji i-ta stavka, inače je prirodan broj koji predstavlja koliko je plaćena i-ta stavka. Đurica je sakupio tačno n računa, i njega zanima zbirni račun za svaki restoran. Imajući sve račune za restorane, zbirni račun za restoran id se definiše kao račun sa k stavki gde vrednost za i-tu stavku predstavlja sumu cena i-te stavke na svim računima restorana id.

Jednom kad Đurica ima sve zbirne račune, on smatra da je najbolji restoran u koji sledeći treba otići onaj koji ima leksikografski najmanji zbirni račun stavki. Đurica je gladan i ne može da razmišlja, te pomozite Đurici i za dati spisak računa ispišite leksikografski najmanji račun.

Tokom određivanja i ispisivanja leksikografski najmanjeg zbirnog računa ne treba uzimati u obzir id restorana. Za dva zbirna računa a₁ a₂ ... a_k i b₁ b₂ ... b_k kažemo da je prvi račun leksikografski manji od drugog ako postoji j takvo da a_i = b_i, i < j, i a_j < b_j.