Rotate Point

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given n points p_{1}, p_{2}, ..., p_{n} in a plane and n integers a_{1}, a_{2}, ..., a_{n}.
For any index i (1 ≤ i ≤ n), it is possible to perform the following operation (let's call it irotation) on an arbitrary point P: Rotate P by a_{i} degrees counterclockwise around the point p_{i}.
Note that a_{i} will always be a multiple of 90. Also note that such an operation changes the point P.
You should process q queries. Each query is of one of the following types:
 1 x y l r: Initially, you are given P = (x, y). Perform each irotation for i = l, l+1, ..., r (in this order) on the point P. Compute the coordinates of P modulo 10^{9} + 7 after performing all irotations.
 2 u x y b: Change the point p_{u} to (x, y) and the angle a_{u} to b.
Input
 The first line of the input contains a single integer n.
 Then, n lines follow. The ith of these lines contains three spaceseparated integers x_{i}, y_{i} and a_{i}. The ith point is initially p_{i} = (x_{i}, y_{i}).
 The next line contains a single integer q denoting the number of queries.
 Each of the following q lines contains a query in the format described above.
Output
For each query of type 1, print a single line containing two spaceseparated integers denoting the coordinates of the point P after performing all rotations, modulo 10^{9} + 7.
Constraints
 1 ≤ n ≤ 10^{5}
 0 ≤ x_{i}, y_{i}, x, y ≤ 10^{9}
 0 ≤ a_{i}, b < 360
 1 ≤ q ≤ 2 · 10^{5}
 1 ≤ l ≤ r ≤ n
 1 ≤ u ≤ n
Example
Input: 3 0 0 90 1 2 180 3 2 270 3 1 5 5 1 3 2 2 2 2 90 1 5 5 1 3 Output: 0 1000000005 1000000003 6
Author:  chemthan 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/ROTPTS 
Tags  chemthan, chemthan, cook89, likecs, matrixmul, medium, sqrtdecomp 
Date Added:  29112017 
Time Limit:  1.5 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions