게나디는 머리가 좋습니다

2016년, 사람들은 2차원 배열로 정사각형 격자 세상을 편하게 관리하고 있었다. 이를 지켜보던 꿀벌 게나디는 벌집도 배열로 관리하면 편하겠다고 생각했다. 그런데 벌집은 정육각형 칸으로 이루어져 있어서 사람들이 쓰는 배열을 그대로 쓸 수 없었고, 게나디는 벌집에 맞는 배열을 직접 발명했다.

게나디가 사는 벌집은 정육각형 칸이 변끼리 맞붙어 있는 모양이다. 게나디는 각 칸을 분명하게 가리키려고 다음 방법으로 좌표를 붙였다.

• 자신이 서 있는 칸을 기준으로 삼아 $(0, 0)$이라 한다.
• 나머지 칸의 좌표는 귀납적으로 정한다. 어떤 칸의 좌표가 $(x, y)$이면, 그 칸에 인접한 여섯 칸의 좌표는 [그림 1]과 같이 $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$, $(x+1, y+1)$, $(x-1, y-1)$이다.

[그림 2]는 이 방법으로 벌집의 각 칸에 좌표를 붙인 결과다.

이렇게 정하면 각 칸의 좌표가 하나로 정해진다는 사실을 증명한 게나디는 발상을 모든 꿀벌에게 알리려 했다. 그러다 최소한의 검증은 해 보는 것이 좋겠다고 생각해, 사람들이 배열로 간단히 푸는 문제를 벌집 버전으로 바꿔 풀어 보기로 했다. 게나디가 고른 문제는 다음과 같다.

벌집의 모든 칸에는 처음에 $0$이 적혀 있다. 다음 두 연산을 지원하는 자료구조를 구현하라.

1. 더하기. $(x, y)$와의 거리가 $r$ 이하인 모든 칸에 $1$을 더한다.
2. 찾아보기. $(x, y)$에 적혀 있는 수를 출력한다.

서로 다른 두 칸 $A$, $B$ 사이의 거리는 인접한 칸으로만 이동해서 $A$에서 출발해 $B$에 도착하는 데 필요한 최소 이동 횟수다. 같은 칸 사이의 거리는 $0$으로 정의한다. [그림 3]은 $r$이 $0$, $1$, $2$일 때 더하기 연산이 $1$을 더하는 칸을 노란색으로 칠한 것이다.

게나디를 대신해 이 문제를 푸는 프로그램을 작성하라.

첫째 줄에 게나디가 사는 벌집의 크기 $N$ ($1 \le N \le 2000$)과 연산의 수 $Q$ ($1 \le Q \le 200000$)가 공백을 사이에 두고 주어진다. 게나디는 $(0, 0)$과의 거리가 $N$ 이하인 칸에만 관심을 둔다.

다음 $Q$개 줄에 연산의 정보가 한 줄에 하나씩 주어진다.

• 1번 종류의 연산은 1 x y r 형식으로 주어진다. $r$은 $0$ 이상의 정수이고, $(x, y)$와의 거리가 $r$ 이하인 모든 칸은 $(0, 0)$과의 거리가 $N$ 이하임이 보장된다.
• 2번 종류의 연산은 2 x y 형식으로 주어진다. $(x, y)$와 $(0, 0)$ 사이의 거리는 $N$ 이하임이 보장된다.

2번 종류의 연산이 주어질 때마다 해당 칸에 적힌 수를 한 줄에 하나씩 출력한다. 2번 종류의 연산은 적어도 한 번 주어진다.

[그림 4]는 첫 번째 예제에서 두 번의 더하기 연산이 차례로 적용되는 모습이다. 왼쪽은 처음 상태, 가운데는 첫 번째 더하기 연산 뒤, 오른쪽은 두 번째 더하기 연산 뒤의 벌집이다.