Walk in the Park

The last week was rainy. Mr. Bean stayed at home for days, and on this sunny day he went for a walk in the central park. Walking along an alley, he saw a bright sign that read "2015: Year of Light!" The sign lifted his mood, and full of inspiration he set off for his destination to do good deeds.

At the park he found a sculpture made of a set of vases of different sizes. The $i$-th vase has size $a_i$, so over the week it collected $a_i$ units of water. Mr. Bean decided there should be no water in the vases, and as an honest man he set out to fix the situation. He made one hole in each vase. The hole in the $i$-th vase has diameter $b_i$, so $b_i$ units of water flow out of it per second. The holes were all made at the same moment. Mr. Bean wants to know the total amount of water left in all vases at each moment after the holes were made. Help him answer all of his questions.

The first line contains two integers $n$ and $t$ ($1 \le n \le 10^5$, $1 \le t \le 10^6$), the number of vases and the time during which Mr. Bean is interested in the water in the vases.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i \le 10^9$, $0 \le b_i \le 10^9$), describing the $i$-th vase.

Print $t+1$ integers. The first line contains the total amount of water at the initial moment. Each following line contains the total amount of water at the next moment.