В некотором государстве живёт \(n\) граждан. Количество денег у \(i\)-го из них равно \(a_{i}\). Государство внимательно следит за благосостоянием своих граждан. Если гражданин совершил покупку или заработал денег, то он обязан отправить в социальные службы справку об изменении баланса с указанием текущего количества денег. Иногда государство делает выплаты малоимущим гражданам: всем гражданам, у кого текущее количество денег строго меньше \(x\), выплачивают пособие такого размера, чтобы количество денег у них стало ровно \(x\). В таком случае гражданин не должен отправлять справку о изменении баланса.
Вам известно начальное количество денег у каждого гражданина, а также лог всех действий в социальных службах: получение справок и выплаты малоимущим. Восстановите количество денег у каждого гражданина после всех событий.
Выходные данные
Выведите \(n\) чисел, разделённых пробелами, — балансы всех граждан после всех событий.
Примечание
Процесс изменения балансов в первом примере: 1 2 3 4 \(\rightarrow\) 3 3 3 4 \(\rightarrow\) 3 2 3 4 \(\rightarrow\) 3 2 3 4
Процесс изменения балансов во втором примере: 3 50 2 1 10 \(\rightarrow\) 3 0 2 1 10 \(\rightarrow\) 8 8 8 8 10 \(\rightarrow\) 8 8 20 8 10
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 3 4
3
2 3
1 2 2
2 1
|
3 2 3 4
|
|
2
|
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20
|
8 8 20 8 10
|