B. Target Practice
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tyger is practicing on an archery target, which is an $$$n \times n$$$ grid of unit squares on the coordinate plane, where $$$n$$$ is odd. The target is arranged into concentric square rings around a single center square.

Each unit square is labeled by a pair of integers $$$(x, y)$$$. The target's bottom-left square is labeled $$$(x_0, y_0)$$$, and the square $$$i$$$ columns right and $$$j$$$ rows up $$$(0 \leq i, j \leq n - 1)$$$ is labeled $$$(x_0 + i, y_0 + j)$$$.

The outermost ring is worth $$$1$$$ point, and the score increases by $$$1$$$ for each ring toward the center. The single center square is worth $$$\frac{n + 1}{2}$$$ points. The squares outside of the target are worth $$$0$$$ points.

Tyger wants you to answer $$$q$$$ queries:

  • 1 x y: Given that an arrow lands at the square labeled $$$(x, y)$$$, output its point value.
  • 2 p: Given that an arrow scored $$$p$$$ points, find $$$\sum (x + y)$$$ over all squares labeled $$$(x, y)$$$ that are worth $$$p$$$ points.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n \leq 10^8, 1 \leq q \leq 2 \cdot 10^5)$$$, representing the size of the target and the number of arrows fired respectively.

The second line contains two integers $$$x_0$$$ and $$$y_0$$$ $$$(-10^8 \leq x_0, y_0 \leq 10^8)$$$, representing the label of the bottom-left unit square in the target.

The next $$$q$$$ lines represent the queries.

A query of type $$$1$$$ will have a line in the format 1 x y $$$(-10^8 \leq x, y \leq 10^8)$$$, where $$$(x, y)$$$ represents the position the arrow hits the plane.

A query of type $$$2$$$ will have a line in the format 2 p $$$(1 \leq p \leq \frac{n + 1}{2})$$$, where $$$p$$$ represents the number of points the arrow scored.

Output

Output $$$q$$$ lines, where line $$$i$$$ contains the answer to query $$$i$$$.

Example
Input
5 3
1 1
1 3 3
2 3
2 1
Output
3
6
96
Note

For the first query, the arrow hits the center of the target, scoring $$$3$$$ points. For the second query, the only way an arrow could score $$$3$$$ points is if it hit the center unit square of the target, which has label $$$(3, 3)$$$, and $$$3 + 3 = 6$$$.