Devu and Manhattan Distance

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Devu has taken the course of computational geometry in the university of Coderpur. He liked this course very much. Today, he got to know about the Manhattan distance and got an assignment for the same topic. Manhattan distance between two points (x_{1},y_{1}) and (x_{2},y_{2}) can be defined as:
Manhattan Distance = abs(x_{1}x_{2}) + abs(y_{1}y_{2})
Devu has N points in the Coordinate plane. Coordinate of i^{th} point is (x_{i},y_{i}). Points are indexed from 0 to (N1)(both inclusive).
He has Q updates or queries, for each update U[i, x,y], change the coordinate of i^{th} point to (x,y).
For each query [L,R], find pair of points whose indices are between L and R(both inclusive) , such that Manhattan distance between them is maximized. Report the maximum Manhattan distance for each of the query.
Devu has to submit the assignment on the Monday, so help him in solving the problem.
Input
 First line of the input will contain an integer N denoting the number of the points in Cartesian plane.
 Next N lines will be containing the coordinates of the N points.
 Next line will contain an integer Q denoting the number of the queries.
 Next Q lines will be containing character 'Q' followed by pair of indices for each of the query or 'U' followed by value of i,x and y for the update.
Output
For each query, print a single integer representing the answer of that query.
Constraints
 0 ≤ L ≤ R ≤ N1
 10^{9} ≤ x,y ≤ 10^{9}
Subtask #1: 20 points
 1 ≤ N,Q ≤1000.
Subtask #3: 80 points
 1 ≤ N,Q ≤ 10^{5}
Example
Input: 4 10 10 10 20 20 20 20 10 2 U 1 20 20 Q 0 3 Output: 20
Explanation
After first updates points will be:
10 10
20 20
20 20
20 10
So, maximum Manhattan distance will be between points (10,10) and (20,20), which will be 20.
Author:  amitpandeykgp 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/MDIST 
Tags  amitpandeykgp, easy, ltime24, segmenttree 
Date Added:  21042015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 