One day Natalia was walking in the woods when she met a little mushroom gnome. The gnome told her the following story: Everybody knows that the mushroom gnomes' power lies in the magic mushrooms that grow in the native woods of the gnomes. There are n trees and m magic mushrooms in the woods: the i -th tree grows at a point on a straight line with coordinates a i and has the height of h i , the j -th mushroom grows at the point with coordinates b j and has magical powers z j . But one day wild mushroommunchers, the sworn enemies of mushroom gnomes unleashed a terrible storm on their home forest. As a result, some of the trees began to fall and crush the magic mushrooms. The supreme oracle of mushroom gnomes calculated in advance the probability for each tree that it will fall to the left, to the right or will stand on. If the tree with the coordinate x and height h falls to the left, then all the mushrooms that belong to the right-open interval x - h , x ) , are destroyed. If a tree falls to the right, then the mushrooms that belong to the left-open interval ( x , x + h are destroyed. Only those mushrooms that are not hit by a single tree survive. Knowing that all the trees fall independently of each other (i.e., all the events are mutually independent, and besides, the trees do not interfere with other trees falling in an arbitrary direction), the supreme oracle was also able to quickly calculate what would be the expectation of the total power of the mushrooms which survived after the storm. His calculations ultimately saved the mushroom gnomes from imminent death. Natalia, as a good Olympiad programmer, got interested in this story, and she decided to come up with a way to quickly calculate the expectation of the sum of the surviving mushrooms' power. The first line contains two integers n and m ( 1 ≤ n ≤ 10 5 , 1 ≤ m ≤ 10 4 ) — the number of trees and mushrooms, respectively. Each of the next n lines contain four integers — a i , h i , l i , r i (