Повороты магических меток
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На плоскости расставлены $$$n$$$ магических меток, $$$i$$$-я метка изначально имеет координаты ($$$x_i; y_i$$$). Затем Джесси делает с ними $$$q$$$ трюков. Каждый трюк описывается пятью числами $$$l$$$, $$$r$$$, $$$x$$$, $$$y$$$, $$$a$$$ ($$$a \in [90, 180, 270]$$$). Джесси поворачивает все метки на позициях с $$$l$$$-й по $$$r$$$-ю относительно точки ($$$x; y$$$) на $$$a$$$ градусов по часовой стрелке.

После каждого фокуса Джесси нужно накрывать все метки специальным прямоугольным полотном для следующего фокуса. При чём стороны прямоугольника должны быть параллельны осям координат. Вам нужно определить, чему равна минимальная площадь подходящего полотна после каждого фокуса. Гарантируется, что после каждого фокуса абсолютное значение координат меток не превышает $$$10^9$$$.

Входные данные

В первой строке вводится два числа $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$).

В следующих $$$n$$$ строках вводится по два числа $$$x_i$$$, $$$y_i$$$ ($$$0 \le |x_i|, |y_i| \le 10^8$$$).

В следующих $$$q$$$ строках вводится по пять чисел $$$l$$$, $$$r$$$, $$$x$$$, $$$y$$$, $$$a$$$ ($$$1 \le l \le r \le n$$$; $$$0 \le |x|, |y| \le 10^8$$$; $$$a \in [90, 180, 270]$$$).

Выходные данные

Выведите $$$q$$$ ответов на каждый фокус в отдельной строке.

Примеры

Входные данные

    5 31 2-2 43 3-1 -15 -31 3 0 0 902 3 5 5 1804 5 -4 -3 180

Выходные данные

    30
    128
    360

Входные данные

    8 41 22 12 -11 -2-1 -2-2 -1-2 1-1 27 8 0 0 2705 8 0 0 2703 8 0 0 2701 8 0 0 270

Выходные данные

    16
    4
    1
    1

Входные данные

    1 30 01 1 0 0 901 1 0 0 1801 1 0 0 270

Выходные данные

    0
    0
    0

Входные данные

    3 20 0-1 01 01 1 -1 -1 1801 1 -1 -1 180

Выходные данные

    6
    0