Ohani was tired of sitting in a mall, watching people hold hands. He hates public displays of affection (PDA). So, he decided to take a walk. He was walking through a magical forest when he came across a porcupine. He noticed that the porcupine's body was completely made of gold. The porcupine said:

Over a period of ~T~ seconds, I will shoot ~N~ quills out in total. The ~i^{th}~ quill exists only between the ~L_i^{th}~ and ~R_i^{th}~ seconds (inclusive).

The height of the ~i^{th}~ can be expressed as ~a_ix^2 + b_ix + c_i~, where ~a_i~, ~b_i~, and ~c_i~ are constants for the ~i^{th}~ quill and ~x~ is the number of seconds the quill has been in the air. For the ~i^{th}~ quill, at time ~L_i~, ~x = 0~.

These quills have magical gravity and pass through anything, so it's perfectly fine for ~a_i~ to be more than ~0~ or the height of a quill to be less than ~0~ at any point in time.

Can you tell me the sum of the heights of all the quills at each second in time between ~1~ and ~T~ inclusive?

Ohani was able to solve the problem and get home just in time to play with legos with his brother. Ohani loves legos, and his brother is a lego lover too.

Input Specification

The first line will contain two integers, ~N, T~ ~(1 \le N \le 10^5, 1 \le T \le 10^5)~.

The next ~N~ lines will each contain five integers, ~L_i, R_i, a_i, b_i, c_i~ ~(1 \le L_i \le R_i \le T, 0 \le |a_i|, |b_i|, |c_i| \le 10^3)~.

Output Specification

Print ~T~ integers on one line, the ~t^{th}~ integer representing the sum of heights of quills at the ~t^{th}~ ~(1 \le t \le T)~ second in time.

Constraints

Subtask 1 [1%]

~T = 1~

Subtask 2 [4%]

~N, T \le 1\,000~

Subtask 3 [5%]

~L_i = 1, R_i = T~

Subtask 4 [20%]

~a_i = 1, b_i = 1~

Subtask 5 [70%]

No additional constraints.

Sample Input

2 6
1 6 1 3 2
3 4 2 2 -200

Sample Output

2 6 -188 -176 30 42

Explanation of Sample Output

The first quill's trajectory is shown as follows:

The second quill's trajectory is shown as follows:

At the ~1^{st}~ second, the sum of the heights is only quill ~1~ at ~x=0~ as quill ~2~ does not exist yet ~(2)~.

At the ~2^{nd}~ second, the sum of the heights is only quill ~1~ at ~x=1~ as quill ~2~ does not exist yet ~(6)~.

At the ~3^{rd}~ second, the sum of the heights is quill ~1~ at ~x=2~ and quill ~2~ at ~x=0~ ~(12 + (-200) = -188)~.

At the ~4^{th}~ second, the sum of the heights is quill ~1~ at ~x=3~ and quill ~2~ at ~x=1~ ~(20 + (-196) = -176)~.

At the ~5^{th}~ second, the sum of the heights is only quill ~1~ at ~x=4~ as quill ~2~ no longer exists ~(30)~.

At the ~6^{th}~ second, the sum of the heights is only quill ~1~ at ~x=5~ as quill ~2~ no longer exists ~(42)~.