{"code":"codeforces1093g","name":"MULDIM","description":"Cho $n$ điểm trên không gian $k$ chiều, điểm thứ $i$ có tọa độ là $(a_{i,1}, a_{i,2}, \\dots, a_{i,k})$. Khoảng cách manhattan giữa $2$ điểm $x$ và $y$ là: $\\sum_{i=1}^{k} |a_{x,i}-a_{y,i}|$.\r\n\r\nBạn phải xử lý $q$ truy vấn thuộc $1$ trong $2$ loại:\r\n\r\n- $1 \\; i \\; b_1 \\; b_2 \\dots \\; b_k$: Gán tọa độ điểm thứ $i$ là $(b_1,b_2,\\dots,b_k)$.\r\n\r\n- $2 \\; l \\; r$: Tìm khoảng cách manhattan lớn nhất giữa $2$ điểm $i$ và $j$ với $l \\le i,j \\le r$.\r\n\r\n#### Input\r\n- Dòng $1$: Gồm $2$ số nguyên $n$ và $k$ ($1 \\le n \\le 10^5$; $1 \\le k \\le 5$) - số lượng phần tử trong $a$ và số chiều của không gian.\r\n- $n$ dòng tiếp theo, mỗi dòng chứa $k$ số $a_{i,1},a_{i,2},\\dots,a_{i,k}$ $(-10^6 \\le a_{i,j} \\le 10^6)$ - tọa độ điểm $i$.\r\n- Dòng tiếp theo gồm $1$ số nguyên $q$ $(1 \\le q \\le 10^5)$- số lượng truy vấn.\r\n- $q$ dòng tiếp theo, mỗi dòng gồm $1$ trong $2$ loại:\r\n    - $1 \\; i \\; b_1 \\; b_2 \\dots \\; b_k$ $(1 \\le i \\le n;$$-10^6 \\le b_j \\le 10^6)$ - Gán tọa độ điểm thứ $i$ là $(b_1,b_2,\\dots,b_k)$.\r\n    - $2 \\; l \\; r$ $(1 \\le l \\le r \\le n)$ - Tìm khoảng cách manhattan lớn nhất giữa $2$ đểm $i,j$ với $l \\le i,j \\le r$.\r\n\r\n#### Output\r\n- Với mỗi truy vấn loại $2$, đưa ra $1$ dòng gồm $1$ số duy nhất là kết quả tìm được.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($30\\%$ số điểm$)$: $n,q \\le 3000$\r\n- Subtask $2$ ($20\\%$ số điểm$)$: $k = 1$.\r\n- Subtask $3$ ($20\\%$ số điểm$)$: $k = 2$.\r\n- Subtask $4$ ($30\\%$ số điểm$)$: Không có điều kiện gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 2\r\n        1 2\r\n        2 3\r\n        3 4\r\n        4 5\r\n        5 6\r\n        7\r\n        2 1 5\r\n        2 1 3\r\n        2 3 5\r\n        1 5 -1 -2\r\n        2 1 5\r\n        1 4 -1 -2\r\n        2 1 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        8\r\n        4\r\n        4\r\n        12\r\n        10\r\n        ```","points":2300.0,"partial":false,"time_limit":3.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}