Crescita in serra#7778
Stai passando dall'informatica all'agricoltura, e il tuo nuovo lavoro consiste nel coltivare girasoli in una serra sotterranea. La serra contiene piante di girasole disposte in linea retta e numerate con numeri interi da a da sinistra a destra. Due lampade forniscono ai girasoli la luce e il calore necessari per crescere: la lampada si trova all'estremità sinistra della linea, mentre la lampada — all'estremità destra.
Ogni giorno viene accesa esattamente una delle lampade, per cui tutti i girasoli si girano verso la luce, e alcuni di essi iniziano a crescere. Un girasole crescerà se e solo se il girasole che si trova immediatamente davanti a lui (nella direzione della fonte di luce) è più alto di lui. La crescita avviene in modo continuo con velocità costante pari esattamente a centimetro al giorno.
Nota che quando un girasole inizia a crescere, può far crescere istantaneamente il girasole che si trova immediatamente dietro di lui.
Vi vengono date le altezze iniziali dei girasoli e il programma di accensione delle lampade per i successivi giorni. Determinate le altezze finali di tutti i girasoli.
Nella prima riga sono contenuti due numeri interi e m~(1 \le n, m \le 300,000) — il numero di girasoli e il numero di giorni nel periodo considerato.
Nella riga successiva sono contenuti numeri interi h_1, h_2, \ldots, h_n~(1 \le h_k \le 10^9) — le altezze iniziali dei girasoli, indicate da sinistra a destra.
Nella riga successiva è contenuta una stringa composta esattamente da caratteri, ognuno dei quali è oppure . Il -esimo carattere determina quale lampada viene accesa nell'-esimo giorno del periodo.
Stampate una riga contenente numeri interi — le altezze finali dei girasoli, disposti da sinistra a destra.
Esempio 1