I. Защита роботов
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компания "Robots industries" производит роботов для защиты территорий. Роботы защищают треугольные участки — прямоугольные равнобедренные треугольники с катетами, параллельными направлениям север-юг и запад-восток.

Владелец некоторого участка покупает и устанавливает роботов на своей территории для защиты. Время от времени бизнесмены хотят строить офисы в некоторых точках и им хочется узнавать, сколько роботов будут охранять его. Вам надо отвечать на эти запросы.

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

В первой строке записано целое число N — ширина и высота участка, а также целое число Q — количество запросов для обработки.

В следующих Q строках записаны запросы, которые надо обработать.

Два типа запросов:

  1. 1 dir x y len — добавить робота для защиты треугольника. В зависимости от значения dir, значения x, y и len представляют различный треугольник:
    • dir = 1: Треугольник обозначается точками (x, y), (x + len, y), (x, y + len)
    • dir = 2: Треугольник обозначается точками (x, y), (x + len, y), (x, y - len)
    • dir = 3: Треугольник обозначается точками (x, y), (x - len, y), (x, y + len)
    • dir = 4: Треугольник обозначается точками (x, y), (x - len, y), (x, y - len)
  2. 2 x y — выведите, сколько роботов охраняют эту точку (робот охраняет точку, если точка расположена внутри или на границе его треугольника)
  • 1 ≤ N ≤ 5000
  • 1 ≤ Q ≤ 105
  • 1 ≤ dir ≤ 4
  • Все точки треугольников находятся в диапазоне [1, N]
  • Все числа — положительные целые числа
Выходные данные

Для каждого запроса второго типа выведите количество роботов, охраняющих эту точку. Каждый ответ должен быть на отдельной строке.

Примеры
Входные данные
17 10
1 1 3 2 4
1 3 10 3 7
1 2 6 8 2
1 3 9 4 2
2 4 4
1 4 15 10 6
2 7 7
2 9 4
2 12 2
2 13 8
Выходные данные
2
2
2
0
1