In some country live wizards. They love to build cities and roads. The country used to have k cities, the j -th city ( 1 ≤ j ≤ k ) was located at a point ( x j , y j ). It was decided to create another n - k cities. And the i -th one ( k < i ≤ n ) was created at a point with coordinates ( x i , y i ): x i = ( a · x i - 1 + b ) mod (10 9 + 9) y i = ( c · y i - 1 + d ) mod (10 9 + 9) Here a , b , c , d are primes. Also, a ≠ c , b ≠ d . After the construction of all n cities, the wizards have noticed something surprising. It turned out that for every two different cities i and j , x i ≠ x j and y i ≠ y j holds. The cities are built, it's time to build roads! It was decided to use the most difficult (and, of course, the most powerful) spell for the construction of roads. Using this spell creates a road between the towns of u , v ( y u > y v ) if and only if for any city w which lies strictly inside the corner at the point u , v (see below), there is a city s that does not lie in the corner, which is located along the x -coordinate strictly between w and u and simultaneously y s > y v . A corner on the points p 2 ( x 2 , y 2 ), p 1 ( x 1 , y 1 ) ( y 1 < y 2 ) is the set of points ( x , y ), for which at least one of the two conditions is fulfilled: min ( x 1 , x 2 ) ≤ x ≤ max ( x 1 , x 2 ) and y ≥ y 1 y 1 ≤ y ≤ y 2 and ( x - x 2 )·( x 1 - x 2 ) ≥ 0 In order to test the spell, the wizards will apply it to all the cities that lie on the x -coordinate in the interval L , R . After the construction of roads the national government wants to choose the maximum number of pairs of cities connected by the road, so that no city occurs in two or more pairs. Your task is for each m offered variants of values L , R to calculate the maximum number of such pairs after the construction of the roads. Please note that the cities that do not lie in the interval L , R on the x -coordinate, do not affect the construction of roads in any way. The first line contains two spac