It’s a glorious day in the video game meta-world of MountainCraft! True to its name, MountainCraft boasts an expansive open world full of mountains to explore. Your avatar in the game wakes up on a remote island, and stares at the mountains on the horizon.
The view of the horizon can be modeled as a Cartesian plane, with the -axis () separating land from sea. Each mountain peak is represented by a point , and the mountain’s sides have slope and , forming a triangle with that peak at the top.
Your avatar can only see the parts of the mountains which are in a viewport. The visible edges of the mountains, where they do not overlap other mountains, are rendered in bold. If mountains overlap, the overlapping parts are not rendered in bold. Edges do not have to intersect for mountains to overlap.
:::align{center}
Figure H.1: The first sample input after all mountains appear.
:::
Unfortunately, due to graphical glitches, mountains can appear and disappear. After each change, you want to know the total length of all the bold lines currently visible in the viewport.
输入格式
The first line of input contains two integers () and (), where is the number of queries and is the width of the viewport. The viewport stretches from to .
Each of the next lines contains two integers () and (), the peak of some mountain. If is the peak of a mountain that is visible, that mountain will disappear. Otherwise, that mountain will become visible.
输出格式
Output lines. For each query in order, output a single line with a single number, which is the total length of the bold lines rendered. Your answer will be accepted if the absolute or relative error is within of the judge’s answer.
