ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1491. Нереальная история

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вы не поверите, но однажды в древности произошла такая история. На заседании круглого стола король Артур встал и сказал: «Пусть каждый рыцарь, сидящий от меня справа не более чем на b мест и не менее чем на a мест, получит по c золотых монет из моего кармана». Если занумеровать всех рыцарей числами от 1 до N против часовой стрелки, так что, рыцарь, сидящий справа от Артура, получит номер 1, а рыцарь, сидящий слева от Артура, — номер N, то получается, что он раздал по c золотых монет рыцарям с номерами a, a + 1, …, b.
Затем благородные рыцари, посмотрев на щедрый поступок Артура, начали вставать по очереди против часовой стрелки и говорить свою тройку чисел ai, bi, ci (1 ≤ i ≤ N). После каждого такого высказывания рыцари, сидящие справа от короля Артура не более чем на bi мест и не менее чем на ai мест, получали по ci золотых монет от короля.
Поскольку каждый рыцарь был очень благороден, то либо ai > i, либо bi < i. Ваша задача — помочь рыцарям выяснить, сколько монет каждый из них получил в дар.

Исходные данные

В первой строке записано количество рыцарей короля Артура N (2 ≤ N ≤ 100000). В следующей строке записаны целые числа a, b и c, названные Артуром (1 ≤ a ≤ b ≤ N; 1 ≤ c ≤ 10000). В следующих N строках перечислены тройки целых чисел ai, bi, ci, названные рыцарями (1 ≤ ai ≤ bi ≤ N; 1 ≤ ci ≤ 10000).

Результат

Выведите N чисел через пробел. i-е число должно равняться количеству монет, которое получил в дар i-й рыцарь.

Примеры

исходные данныерезультат
4
2 3 2
2 4 1
3 4 1
1 2 1
1 1 1
2 4 4 2
7
1 7 1
2 3 4
3 5 3
1 2 1
5 7 4
2 4 10
3 4 2
1 6 3
5 19 23 19 11 8 5
Автор задачи: Александр Торопов
Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)