Задан массив \(a\), состоящий из \(n\) точек в \(k\)-мерном пространстве. Введем расстояние между двумя точками \(a_x\) и \(a_y\), как \(\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|\) (также известное как манхэттенское расстояние).
Необходимо обработать \(q\) запросов двух следующих типов:
В первой строке записаны два целых числа \(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\) строк, каждая задает запрос. Есть два типа запросов:
Гарантируется, что во входных данных есть хотя бы один запрос второго типа.
Выведите ответ на каждый запрос второго типа.
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
6000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач