Multidimensional Queries
Contest: Educational Codeforces Round 56 (Rated for Div. 2)
Difficulty rating: 2300
Tags: bitmasks, data structures

You are given an array $$$a$$$ of $$$n$$$ points in $$$k$$$-dimensional space. Let the distance between two points $$$a_x$$$ and $$$a_y$$$ be $$$\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$$$ (it is also known as Manhattan distance).

You have to process $$$q$$$ queries of the following two types:

- $$$1$$$ $$$i$$$ $$$b_1$$$ $$$b_2$$$ ... $$$b_k$$$ — set $$$i$$$-th element of $$$a$$$ to the point $$$(b_1, b_2, \dots, b_k)$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — find the maximum distance between two points $$$a_i$$$ and $$$a_j$$$, where $$$l \le i, j \le r$$$.

Input format:
The first line contains two numbers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 5$$$) — the number of elements in $$$a$$$ and the number of dimensions of the space, respectively.

Then $$$n$$$ lines follow, each containing $$$k$$$ integers $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, k}$$$ ($$$-10^6 \le a_{i, j} \le 10^6$$$) — the coordinates of $$$i$$$-th point.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each denoting a query. There are two types of queries:

- $$$1$$$ $$$i$$$ $$$b_1$$$ $$$b_2$$$ ... $$$b_k$$$ ($$$1 \le i \le n$$$, $$$-10^6 \le b_j \le 10^6$$$) — set $$$i$$$-th element of $$$a$$$ to the point $$$(b_1, b_2, \dots, b_k)$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — find the maximum distance between two points $$$a_i$$$ and $$$a_j$$$, where $$$l \le i, j \le r$$$.

There is at least one query of the second type.

Output format:
Print the answer for each query of the second type.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
8
4
4
12
10

Editorial:
Let's rewrite the formula of distance between two points as follows:
$$$\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}| = \sum \limits_{i = 1}^{k} c_i (a_{x, i} - a_{y, i}) = \sum \limits_{i = 1}^{k} c_i a_{x, i} - \sum \limits_{i = 1}^{k} c_i a_{y, i}$$$, where $$$c_i = 1$$$ if $$$a_{x, i} \ge a_{y, i}$$$, otherwise $$$c_i = -1$$$.
Consider what will happen if we change some $$$c_i$$$ to the opposite value. The result of this formula obviously won't increase, so we may try all possible values of $$$c_i$$$ and pick maximum result.
This allows us to consider every option to set values of $$$c_i$$$ (there are $$$2^k$$$ such options) separately, and when we fix a set of values of $$$c_i$$$, find two points that maximize the distance if it is expressed with fixed $$$c_i$$$. To do so, we have to find the point having maximum $$$\sum \limits_{i = 1}^{k} c_i a_{x, i}$$$ and having minimum $$$\sum \limits_{i = 1}^{k} c_i a_{x, i}$$$.
So actually our problem is reduced to the following: we have $$$2^k$$$ arrays, we want to process some queries in the form "change an element of some array" and "find maximum and minimum on some segment of some array". This can be done simply by building a segment tree over each array, and then we will get the solution having $$$O((n + q) 2^k \log n)$$$ time complexity.