AT_abc437_f [ABC437F] Manhattan Christmas Tree 2

二次元平面上に $ N $ 個のクリスマスツリーがあります。 $ i $ 番目 $ (1\le i\le N) $ のクリスマスツリーは座標 $ (X_i,Y_i) $ に存在します。 $ Q $ 個のクエリが与えられるので、順にクエリを処理してください。各クエリは、以下のいずれかです。 - タイプ $ 1 $ : `1 i x y` の形式で与えられる。 $ i $ 番目のクリスマスツリーの座標を $ (x,y) $ に変更する。 - タイプ $ 2 $ : `2 L R x y` の形式で与えられる。 $ L,L+1,\ldots,R $ 番目のクリスマスツリーのうち、座標 $ (x,y) $ からマンハッタン距離で最も遠いクリスマスツリーまでの距離を出力する。 ただし、座標 $ (x_1,y_1) $ と座標 $ (x_2,y_2) $ のマンハッタン距離は $ |x_1-x_2|+|y_1-y_2| $ で定義されます。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ ここで、 $ i $ 番目のクエリ $ \text{query}_i $ は以下のいずれかの形式で与えられる。 > $ 1 $ $ i $ $ x $ $ y $ > $ 2 $ $ L $ $ R $ $ x $ $ y $

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

### Sample Explanation 1 はじめ、 $ 1,2,3 $ 番目のクリスマスツリーはそれぞれ座標 $ (-1,-1),(1,2),(-2,1) $ に存在します。 各クエリは以下のように処理されます。 - $ 1,2 $ 番目のクリスマスツリーと座標 $ (0,0) $ のマンハッタン距離はそれぞれ $ 2,3 $ です。したがって、 $ 2,3 $ の最大値である $ 3 $ を出力します。 - $ 1,2,3 $ 番目のクリスマスツリーと座標 $ (-1,2) $ のマンハッタン距離はそれぞれ $ 3,2,2 $ です。したがって、 $ 3,2,2 $ の最大値である $ 3 $ を出力します。 - $ 1 $ 番目のクリスマスツリーの座標を $ (0,1) $ に変更します。 $ 1,2,3 $ 番目のクリスマスツリーの座標はそれぞれ $ (0,1),(1,2),(-2,1) $ になります。 - $ 1,2,3 $ 番目のクリスマスツリーと座標 $ (-1,2) $ のマンハッタン距離はそれぞれ $ 2,2,2 $ です。したがって、 $ 2,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 $ - 入力される値は全て整数