Ограничение времени: 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 (1 ≤ 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 года)
Исправлю решение