Уже несколько месяцев Максим приезжает на работу исключительно на своём любимом велосипеде. И вот недавно он решил, что готов принимать участие в соревнованиях велосипедистов.

Он знает, что в этом году пройдут n соревнований. В ходе i-го соревнования участник должен будет максимально быстро проехать прямой участок от точки s_i до точки f_i (s_i < f_i).

Измерение времени на соревнованиях — сложный процесс, связанный с правильным использованием датчика времени. Представим переднее колесо велосипеда участника как окружность радиуса r. Пренебрежём толщиной шины, размерами датчика, проскальзыванием колеса и другими физическими эффектами. Датчик времени помещается на обод колеса, то есть на какую-то фиксированную точку на окружности радиуса r. После этого датчик движется так же, как и выбранная точка на окружности.

Для старта каждый участник может выбрать любую точку b_i, такую что его велосипед полностью находится за стартовой чертой, то есть b_i < s_i - r. После этого он начинает движение, мгновенно разгоняется до своей максимальной скорости, и в момент ts_i, когда координата датчика совпадает с координатой старта, датчик начинает отсчёт времени. Велосипедист проезжает всю дистанцию со своей максимальной скоростью, и как только координата датчика совпадёт с координатой финиша (момент времени tf_i), датчик сработает ещё раз и зафиксирует итоговое время. Таким образом, датчик зарегистрирует, что участник проехал дистанцию за время tf_i - ts_i.

Максим силён в математике и догадывается, что итоговый результат зависит не только от его максимальной скорости v, но и от выбора начальной точки b_i. Теперь Максим просит вас для каждого из n соревнований определить минимальное время, за которое он сможет проехать дистанцию от s_i до f_i. Радиус колеса велосипеда равен r.