AT_abc437_f [ABC437F] Manhattan Christmas Tree 2

There are $ N $ Christmas trees on a two-dimensional plane. The $ i $ -th $ (1\le i\le N) $ Christmas tree is located at coordinates $ (X_i,Y_i) $ . You are given $ Q $ queries. Process the queries in order. Each query is one of the following: - Type $ 1 $ : Given in the form `1 i x y`. Change the coordinates of the $ i $ -th Christmas tree to $ (x,y) $ . - Type $ 2 $ : Given in the form `2 L R x y`. Output the Manhattan distance from the coordinates $ (x,y) $ to the farthest Christmas tree among the $ L,L+1,\ldots,R $ -th Christmas trees. Here, the Manhattan distance between coordinates $ (x_1,y_1) $ and coordinates $ (x_2,y_2) $ is defined as $ |x_1-x_2|+|y_1-y_2| $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ Here, the $ i $ -th query $ \text{query}_i $ is given in one of the following formats: > $ 1 $ $ i $ $ x $ $ y $ > $ 2 $ $ L $ $ R $ $ x $ $ y $

Output the answers to the queries, separated by newlines, according to the instructions in the problem statement.

### Sample Explanation 1 Initially, the $ 1 $ st, $ 2 $ nd, $ 3 $ rd Christmas trees are located at coordinates $ (-1,-1) $ , $ (1,2) $ , $ (-2,1) $ , respectively. Each query is processed as follows: - The Manhattan distances from the $ 1 $ st and $ 2 $ nd Christmas trees to coordinates $ (0,0) $ are $ 2 $ and $ 3 $ , respectively. Thus, output $ 3 $ , which is the maximum value among $ 2,3 $ . - The Manhattan distances from the $ 1 $ st, $ 2 $ nd, $ 3 $ rd Christmas trees to coordinates $ (-1,2) $ are $ 3 $ , $ 2 $ , $ 2 $ , respectively. Thus, output $ 3 $ , which is the maximum value among $ 3,2,2 $ . - Change the coordinates of the $ 1 $ st Christmas tree to $ (0,1) $ . The coordinates of the $ 1 $ st, $ 2 $ nd, $ 3 $ rd Christmas trees become $ (0,1),(1,2),(-2,1) $ , respectively. - The Manhattan distances from the $ 1 $ st, $ 2 $ nd, $ 3 $ rd Christmas trees to coordinates $ (-1,2) $ are $ 2 $ , $ 2 $ , $ 2 $ , respectively. Thus, output $ 2 $ , which is the maximum value among $ 2,2,2 $ . ### Constraints - $ 1\le N,Q\le 2\times 10^5 $ - $ -10^9\le X_i,Y_i\le 10^9 $ - $ 1\le i\le N $ - $ 1\le L\le R\le N $ - $ -10^9\le x,y\le 10^9 $ - All input values are integers.