Gennady is smart

In 2016 people were managing a world of square cells with two-dimensional arrays. Gennady the bee watched this and decided that a honeycomb would also be easier to manage with an array. A honeycomb is made of regular hexagonal cells, so the array people use does not fit it, and Gennady had to invent an array of his own.

The honeycomb Gennady lives in is a sheet of regular hexagonal cells joined edge to edge. To point at every cell without ambiguity, Gennady assigns coordinates like this.

• The cell he stands on is $(0, 0)$.
• Every other cell gets its coordinates inductively. If a cell is $(x, y)$, then the six cells adjacent to it are $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$, $(x+1, y+1)$ and $(x-1, y-1)$, as in Figure 1.

Figure 2 shows the coordinates this rule gives to the cells of the comb.

Gennady proved that the rule assigns exactly one coordinate pair to every cell. He wanted to tell every bee about it, then decided to check the idea first by taking a problem that people solve easily with their array and solving the honeycomb version of it. Here is the problem he picked.

Every cell of the honeycomb has $0$ written on it at the start. Implement a data structure that supports two operations.

1. Add. Add $1$ to every cell whose distance from $(x, y)$ is at most $r$.
2. Look up. Print the number written on $(x, y)$.

The distance between two different cells $A$ and $B$ is the smallest number of moves needed to get from $A$ to $B$ when every move goes to an adjacent cell. The distance between a cell and itself is $0$. Figure 3 paints yellow the cells that the add operation raises by $1$ when $r$ is $0$, $1$ and $2$.

Write a program that solves this problem for Gennady.

The first line contains the size $N$ of Gennady's honeycomb ($1 \le N \le 2000$) and the number of operations $Q$ ($1 \le Q \le 200000$), separated by a space. Gennady cares only about the cells whose distance from $(0, 0)$ is at most $N$.

Each of the next $Q$ lines describes one operation.

• An operation of the first kind is given as 1 x y r. Here $r$ is a non-negative integer, and every cell whose distance from $(x, y)$ is at most $r$ is guaranteed to be at distance at most $N$ from $(0, 0)$.
• An operation of the second kind is given as 2 x y. The distance between $(x, y)$ and $(0, 0)$ is guaranteed to be at most $N$.

For every operation of the second kind, print the number written on that cell, one per line. At least one operation of the second kind is given.

Figure 4 shows the two add operations of the first example taking effect one after another. The left comb is the starting state, the middle one is the comb after the first add operation, and the right one is the comb after the second add operation.