Вы не поверите, но однажды в древности произошла такая история. На заседании круглого стола король Артур встал и сказал: «Пусть каждый рыцарь, сидящий от меня справа не более чем на b мест и не менее чем на a мест, получит по c золотых монет из моего кармана». Если занумеровать всех рыцарей числами от 1 до N против часовой стрелки, так что, рыцарь, сидящий справа от Артура, получит номер 1, а рыцарь, сидящий слева от Артура, — номер N, то получается, что он раздал по c золотых монет рыцарям с номерами a, a + 1, …, b.

Затем благородные рыцари, посмотрев на щедрый поступок Артура, начали вставать по очереди против часовой стрелки и говорить свою тройку чисел a_i, b_i, c_i (1 ≤ i ≤ N). После каждого такого высказывания рыцари, сидящие справа от короля Артура не более чем на b_i мест и не менее чем на a_i мест, получали по c_i золотых монет от короля.

Поскольку каждый рыцарь был очень благороден, то либо a_i > i, либо b_i < i. Ваша задача — помочь рыцарям выяснить, сколько монет каждый из них получил в дар.

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

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