G. Многомерные запросы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a$$$, состоящий из $$$n$$$ точек в $$$k$$$-мерном пространстве. Введем расстояние между двумя точками $$$a_x$$$ и $$$a_y$$$, как $$$\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$$$ (также известное как манхэттенское расстояние).

Необходимо обработать $$$q$$$ запросов двух следующих типов:

  • $$$1$$$ $$$i$$$ $$$b_1$$$ $$$b_2$$$ ... $$$b_k$$$ — выставить $$$i$$$-й элемент $$$a$$$ равным точке $$$(b_1, b_2, \dots, b_k)$$$;
  • $$$2$$$ $$$l$$$ $$$r$$$ — найти максимальное расстояние между двумя точками $$$a_i$$$ и $$$a_j$$$, где $$$l \le i, j \le r$$$.
Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 5$$$) — количество элементов в $$$a$$$ и количество измерений в пространстве, соответственно.

Затем следуют $$$n$$$ строк, в каждой записаны по $$$k$$$ целых чисел $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, k}$$$ ($$$-10^6 \le a_{i, j} \le 10^6$$$) — координаты $$$i$$$-й точки.

В следующей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк, каждая задает запрос. Есть два типа запросов:

  • $$$1$$$ $$$i$$$ $$$b_1$$$ $$$b_2$$$ ... $$$b_k$$$ ($$$1 \le i \le n$$$, $$$-10^6 \le b_j \le 10^6$$$) — выставить $$$i$$$-й элемент $$$a$$$ равным точке $$$(b_1, b_2, \dots, b_k)$$$;
  • $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — найти максимальное расстояние между двумя точками $$$a_i$$$ и $$$a_j$$$, где $$$l \le i, j \le r$$$.

Гарантируется, что во входных данных есть хотя бы один запрос второго типа.

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

Выведите ответ на каждый запрос второго типа.

Пример
Входные данные
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5
Выходные данные
8
4
4
12
10