Задача D. Траектория подвижной частицы ≡

Условие

Начинающий программист Вася занимается разработкой системы, отвечающей за анимацию подвижных частиц.

Известно, что каждая такая частица должна двигаться вдоль ломаной линии, которая в моменты времени t_i проходит через установленные точки с координатами: (x_i, y_i), где i = 0, 1, …, (n − 1). При этом полагается, что на каждом интервале [t_i, t_i + 1] скорость частицы остается неизменной. В свою очередь, информация о положениях частицы в моменты времени t_i в дальнейшем может уточняться.

Помимо всего прочего ему также требуется эффективным образом обрабатывать запросы следующих видов:

mov i x y — обновить координаты положения частицы в момент времени t_i;

get a b — вернуть расстояние, пройденное частицей за время [a, b].

Поскольку Вася еще недостаточно опытен в решении подобных задач, он обратился за помощью к Вам.

Формат входного файла

В начале входного файла "input.txt" записано натуральное n, за которым следует ровно 3 × n вещественных чисел (t_i, x_i, y_i), определяющих изначальную траекторию. Далее идет натуральное m, за которым следует ровно m запросов.

Формат выходного файла

Выходной файл "output.txt" должен содержать результаты выполнения каждого из get-запросов, указанные с точностью до 5-го знака после запятой.

Ограничения

t_i < t_i + 1 ≤ 10, 2 ≤ n ≤ 10⁵, 0 < m ≤ 10⁴

Примеры тестов

5
0.00000 -3.87048  3.96100
2.53010 -2.97601  4.97030
4.09607 -2.24526  2.50780
7.12038  1.21090  4.84820
9.99999 -0.17846  4.20190

5
get      0.00000  9.99999
mov   1 -2.58070  4.98030
get      0.00000  4.09607
mov   2 -1.70250  2.67010
get      4.09607  9.99999

9.62361
4.13908
5.16991

5
0.53080 -0.25010 -1.96000
2.76090  3.04709 -0.34010
4.09601 -0.56010  0.05036
7.50430  3.36051  1.24607
8.75041  0.11308  3.70200

5
get      2.76090  4.09601
mov   3  3.75096  1.54670
get      3.81067  8.23060
mov   1  3.65040  0.87090
get      1.92304  2.01345

3.62826
7.80334
0.19539