Zakhar is participating in a geometry contest named after Vadim Barinov, where he encountered a rather interesting problem. He was given a convex polygon with N vertices in Cartesian coordinates. The problem involved cutting the polygon along its diagonals. Zakhar needed to make several cuts, but he was a bit unsure of his abilities, so in addition to the cuts, he also took some measurements. Formally, Zakhar performed Q actions of two types:

Zakhar performed all these actions at the very beginning of the contest, and now the contest is coming to an end, but the piece of paper with his notes has somehow gone missing. Fortunately, Zakhar remembers all his actions by type and the numbers of the vertices he chose. Help him restore the contents of the piece of paper.

The first line contains two integers N and Q — the number of vertices of the convex polygon and the number of Zakhar’s actions (4 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

The next N lines describe the coordinates of the polygon’s vertices in counter-clockwise order with two integers x_i and y_i. It is guaranteed that the polygon is convex. All coordinates do not exceed 10⁹ in absolute value.

The following Q lines describe Zakhar’s actions in the format “t_i l_i r_i”, where t_i — the type of action: ‘m’ for measurement, ‘c’ for cut; 1 ≤ l_i, r_i ≤ N. It is guaranteed that the segment from vertex l_i to vertex r_i is always a diagonal, meaning both of these vertices are in the current polygon and do not form one of the sides of this polygon.

Output Q lines with the area recorded on the piece of paper after each of Zakhar’s actions.

The answer will be accepted if the absolute or relative error of each number does not exceed 10⁻⁹.