İstixanada Böyümə#7778
Siz informatika sahəsindən kənd təsərrüfatına keçirsiniz və yeni işiniz yeraltı istixanada günəbaxan yetişdirməkdən ibarətdir. İstixanada bir düz xətt üzərində yerləşdirilmiş və soldan sağa -dən -ə qədər tam ədədlərlə nömrələnmiş ədəd günəbaxan bitkisi var. İki lampa günəbaxanlara böyümək üçün lazım olan işıq və istiliyi təmin edir: lampası xəttin sol ucunda, lampası isə sağ ucunda yerləşir.
Hər gün lampalardan yalnız biri yandırılır, bunun nəticəsində bütün günəbaxanlar işığa tərəf dönür və bəziləri böyüməyə başlayır. Bir günəbaxan yalnız və yalnız o zaman böyüyəcək ki, ondan dərhal əvvəl (işıq mənbəyi istiqamətində) yerləşən günəbaxan ondan hündür olsun. Böyümə fasiləsiz olaraq, dəqiq santimetr/gün sabit sürətlə baş verir.
Diqqət edin ki, bir günəbaxan böyüməyə başladıqda, o, dərhal arxasında yerləşən günəbaxanın da böyüməsinə səbəb ola bilər.
Sizə günəbaxanların başlanğıc hündürlükləri və növbəti gün üçün lampaların yandırılma cədvəli verilmişdir. Bütün günəbaxanların son hündürlüklərini müəyyən edin.
Birinci sətirdə iki tam ədəd və m~(1 \le n, m \le 300,000) verilmişdir — günəbaxanların sayı və nəzərdən keçirilən dövrdəki günlərin sayı.
Növbəti sətirdə soldan sağa verilmiş günəbaxanların başlanğıc hündürlükləri olan tam ədəd h_1, h_2, \ldots, h_n~(1 \le h_k \le 10^9) verilmişdir.
Növbəti sətirdə dəqiq simvoldan ibarət olan, hər biri ya , ya da olan bir sətir verilmişdir. -ci simvol dövrün -ci günündə hansı lampanın yandırıldığını müəyyən edir.
Soldan sağa yerləşdirilmiş günəbaxanların son hündürlüklərini göstərən tam ədəddən ibarət bir sətir çap edin.
Nümunə 1