URI Online Judge | 1511

GCD Grid

By Mateus Carvalho Dantas, Federal University of Campina Grande BR Brazil

Timelimit: 5

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).

Input

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

Output

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

10
QUERY 0 0 10
SET 0 0 25
QUERY 0 0 10
SET 0 5 15
QUERY 0 0 6
SET 0 -7 5
QUERY 0 0 7
SET 0 -8 4
QUERY 0 0 8
QUERY 0 -9 1

0
25
5
5
1
4