В некоторой стране живут волшебники. Они любят строить города и дороги.
Раньше в стране было k городов, j-ый (1 ≤ j ≤ k) был расположен в точке (xj, yj). Было решено наколдовать еще n - k городов. Причем i-ый (k < i ≤ n) город колдовался в точку с координатами (xi, yi):
- xi = (a·xi - 1 + b) mod (109 + 9)
- yi = (c·yi - 1 + d) mod (109 + 9)
Здесь a, b, c, d — простые числа. Причем a ≠ c, b ≠ d.
После постройки всех n городов, волшебники заметили удивительное свойство. Для любых двух различных городов с номерами i и j: xi ≠ xj и yi ≠ yj.
Города построены, пора строить дороги! Было решено использовать самое сложное (и, конечно же, самое мощное) заклинание для постройки дорог. C использованием этого заклинания, между городами u, v (yu > yv) проводится дорога тогда и только тогда, когда для любого города w, лежащего строго внутри уголка на точках u, v (см. ниже), есть город s, не лежащий в уголке, который находится по x-координате строго между w и u и при этом ys > yv.
Уголком на точках p2(x2, y2), p1(x1, y1) (y2 > y1) называется множество точек (x, y), для которых выполнено хотя бы одно из двух условий:
- min(x1, x2) ≤ x ≤ max(x1, x2) и y ≥ y1
- y1 ≤ y ≤ y2 и (x - x2)·(x1 - x2) ≥ 0
На рисунке изображены примеры уголков Для того, чтобы опробовать заклинание, оно будет применено ко всем городам, лежащим по x-координате в отрезке [L, R]. После постройки дорог руководство страны хочет выбрать как можно больше пар городов, соединенных дорогой, так, что никакой город не лежит в двух или более парах. Вам предлагается для каждого из m предложенных вариантов выбора значений L, R посчитать максимальное количество таких пар после постройки дорог. Обратите внимание, что города, не лежащие в отрезке [L, R] по x-координате, никак не влияют на постройку дорог.
Примечание
В первом примере дороги соединяют города в цепочку в порядке возрастания x.
Во втором примере оставшиеся 5 городов будут построены в точках (5, 11); (20, 263098); (65, 292514823); (200, 76958738); (605, 622120197).