You won't believe it, but once, in ancient times, there happened the following story. At a meeting of the Round Table, King Arthur stood up and said: “Let each knight sitting on my right not farther than b places and not nearer than a places receive from me c gold coins.” If we number the knights from 1 to N counter-clockwise so that the knight sitting on Arthur's right is numbered 1 and the knight sitting on Arthur's left is numbered N, then we have that the king gave c gold coins to the knights with numbers a, a + 1, …, b.

Having looked at Arthur's generous deed, the noble knights started to stand up one after another and tell their three numbers a_i, b_i, c_i (1 ≤ i ≤ N). After each of these utterances, the knights with numbers from a_i to b_i received c_i gold coins each from the king.

Since each knight was very noble, either a_i > i or b_i < i. You task is to help the knights to learn how many gold coins each of them received.

The first line contains the number of King Arthur's knights N (2 ≤ N ≤ 100000). In the next line, there are integers a, b, and c, which the king said (1 ≤ a ≤ b ≤ N; 1 ≤ c ≤ 10000). Each of the next N lines contains three integers a_i, b_i, c_i, which the ith knight said (1 ≤ a_i ≤ b_i ≤ N; 1 ≤ c_i ≤ 10000).

Output N numbers separated with a space. The ith number is the number of gold coins received by the ith knight.