Захар решает геометрический контест имени Вадима Баринова, где ему попалась довольно интересная задача. В ней был дан выпуклый многоугольник на N вершинах в декартовых координатах. Задача была связана с разрезами многоугольника по диагоналям. Захару нужно было провести несколько отрезов, однако он немного сомневался в своих силах, поэтому, помимо отрезов, он произвёл замеры. Формально говоря, Захар совершил Q действий двух типов:

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

В первой строке даны два целых числа N и Q — количество вершин выпуклого многоугольника и количество действий Захара (4 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

В следующих N строках описаны координаты вершин многоугольника в порядке обхода против часовой стрелки двумя целыми числами x_i и y_i. Гарантируется, что многоугольник выпуклый. Все координаты по модулю не превосходят 10⁹.

В следующих Q строках описаны действия Захара в формате «t_i l_i r_i», где t_i — тип действия: ‘m’ для замера, ‘c’ для отреза; 1 ≤ l_i, r_i ≤ N. Гарантируется, что отрезок от вершины l_i до вершины r_i всегда является диагональю, то есть обе эти вершины есть в текущем многоугольнике, а также не описывают одну из сторон этого многоугольника.

Выведите Q строк с записанной в листочке площадью после каждого действия Захара.

Ответ будет засчитан, если абсолютная или относительная погрешность каждого числа не превосходит 10⁻⁹.