A holiday tradition in Woburn C.I. is to give each other boxen (boxes). However, these are no ordinary boxen, they contain gifts, such as foxen (foxes) or more boxen. When one receives a fox, they gain a happiness of ~F~, a constant given at the beginning of the input. You have one species of foxen and a number of different species of boxen.

These boxen have strange properties, they contain exactly one fox or box (which may in turn contain more boxen), regardless of size. No box can directly or indirectly contain itself. Each box has a difficulty value ~d_i~, and multiplier value ~b_i~. The happiness given in a box is equal to the following formula:

$$\displaystyle H_i = b_i*pre_i-d_i$$

Where ~pre_i~ is the happiness of the box (or fox) that it contains.

imaxblue has a list of ~N~ boxen. For index ~i~, imaxblue would like to know the maximum happiness that can be created by packing zero or more boxen (and also a single fox), in any order, that are listed before or on that index. Note that if you use zero boxen, the happiness is just ~F~.

Input Specification

~2~ integers, ~N~ ~(N \le 100\,000)~ and ~F~ ~(1 \le F \le 100\,000)~.
~N~ lines, each with ~2~ integers: ~b_i~ and ~d_i~ ~(1 \le b_i, d_i \le 100\,000)~.

Output Specification

~N~ lines, each with an integer: the answer to each of imaxblue's queries. Since the answer can be large, please output the value modulo ~1\,000\,000\,007~ ~(= 10^9 + 7)~.

Sample Input

2 3
2 8
7 12

Sample Output

3
10