ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1491. Unreal Story

Time limit: 1.0 second
Memory limit: 64 MB
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 ai, bi, ci (1 ≤ i ≤ N). After each of these utterances, the knights with numbers from ai to bi received ci gold coins each from the king.
Since each knight was very noble, either ai > i or bi < i. You task is to help the knights to learn how many gold coins each of them received.

Input

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 ai, bi, ci, which the ith knight said (1 ≤ ai ≤ bi ≤ N; 1 ≤ ci ≤ 10000).

Output

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

Samples

inputoutput
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
Problem Author: Alexander Toropov
Problem Source: XIII-th USU Junior Contest, October 2006