U velikom distributivnom centru postoji jedan automatizovani transporter koji svakog dana može da prenese ograničen broj paketa. Broj paketa koje transporter može preneti tokom dana i označen je sa m[i]. Kompanija je unapred izračunala vrednosti brojeva m[i] za narednih n dana.

Postoji n klijenata, a klijent j želi da pošalje pošiljku koja sadrži d[j] paketa. Svaki klijent koristi transporter počevši od prvog dana i svakog dana može poslati najviše onoliko paketa koliko transporter tog dana dozvoli. Kada pošalje sve pakete, prestaje da koristi transporter.

Za svakog klijenta odrediti koliko je dana potrebno da pošalje celu pošiljku. Ako nije moguće poslati sve pakete ni nakon svih n dana, ispisati -1.

Vremenska složenost algoritma mora biti O(n log n), a prostorna složenost O(n).

Улаз

Sa standardnog ulaza unosi se:

• pozitivan broj n ∈ [1, 10^6]
• niz m dužine n, gde je m[i] ∈ [1, 100]
• niz d dužine n, gde je d[i] ∈ [10, 1000]

Излаз

Na standardni izlaz ispisati niz od n brojeva, gde i-ti broj predstavlja količinu dana potrebnu da klijent i pošalje celu pošiljku, odnosno -1 ako to nije moguće.

Пример

Улаз

5
3 1 4 2 5
2 6 1 5 9

Излаз

1 3 1 3 4