By Mateus Carvalho Dantas, Federal University of Campina Grande Brazil
Given an infinity grid full of zeros and 'Q' queries of the following types:
SET x y d: Set position (x,y) of the grid to integer d.
QUERY x y d: Return the gcd (Greatest Common Divisor) of all positions of the grid that are at most 'd' positions away (Manhattan Distance) from position (x,y).
The input contains many test cases and ends with EOF. The first line of the each input contains an integer Q (1 <= Q <= 105) that represents the amount of queries to be done.
Each one of the following Q lines contains one of the queries bellow:
SET x y d
QUERY x y d
0 <= |x|, |y| <= 500
0 <= d <= 106
Print all queries for all test cases, one per line. For each query of the type "QUERY x y d", you have to answer on the standard output the gcd (Greatest Common Divisor) of all positions that are at most 'd' positions away from position (x, y).
|Sample Input||Sample Output|