Chris the Rabbit found the traces of an ancient Martian civilization. The brave astronomer managed to see through a small telescope an architecture masterpiece — "A Road to the Sun". The building stands on cubical stones of the same size. The foundation divides the entire "road" into cells, into which the cubical stones are fit tightly. Thus, to any cell of the foundation a coordinate can be assigned. To become the leader of the tribe, a Martian should build a Road to the Sun, that is to build from those cubical stones on a given foundation a stairway. The stairway should be described by the number of stones in the initial coordinate and the coordinates of the stairway's beginning and end. Each following cell in the coordinate's increasing order should contain one cubical stone more than the previous one. At that if the cell has already got stones, they do not count in this building process, the stairways were simply built on them. In other words, let us assume that a stairway is built with the initial coordinate of l , the final coordinate of r and the number of stones in the initial coordinate x . That means that x stones will be added in the cell l , x + 1 stones will be added in the cell l + 1 , ..., x + r - l stones will be added in the cell r . Chris managed to find an ancient manuscript, containing the descriptions of all the stairways. Now he wants to compare the data to be sure that he has really found "A Road to the Sun". For that he chose some road cells and counted the total number of cubical stones that has been accumulated throughout the Martian history and then asked you to count using the manuscript to what the sum should ideally total. The first line contains three space-separated integers: n , m , k ( 1 ≤ n , m ≤ 10 5 , 1 ≤ k ≤ min ( n , 100) ) which is the number of cells, the number of "Roads to the Sun" and the number of cells in the query correspondingly. Each of the following m roads contain three space-separated integers: a i , b i