У Димы есть лесенка, которая состоит из n ступенек. Первая ступенька имеет высоту a1, вторая — a2, последняя — an (1 ≤ a1 ≤ a2 ≤ ... ≤ an).
Дима решил поиграться с лесенкой, поэтому он бросает сверху на лесенку прямоугольные коробки: i-тая коробка имеет ширину wi и высоту hi. Каждую коробку Дима бросает вертикально вниз на первые wi ступенек лесенки, то есть коробка покрывает ступеньки с номерами 1, 2, ..., wi. Каждая брошенная коробка летит вертикально вниз, до тех пор пока не случится хотя бы одно их двух следующих событий:
- низ коробки коснется верха одной из ступенек;
- низ коробки коснется верха одной из уже брошенных коробок.
Учитывается только касание горизонтальных сторон ступенек и коробок, при этом касание углами не учитывается. В частности из этого следует, что коробка шириной wi не может коснуться ступеньки с номером wi + 1.
Вам задано описание лесенки и последовательность, в которой Дима кидал коробки на нее. Для каждой коробки определите, на какой высоте окажется низ этой коробки после приземления. Считайте, что очередная коробка бросается уже после приземления предыдущей.
Выходные данные
Выведите m целых чисел — для каждой коробки высоту, на которой окажется низ этой коробки после приземления. Ответы для коробок выводите в порядке, в котором коробки заданы во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.