Crazy Queries

All submissions for this problem are available.
Problem Statement
Abhishek loves to play with Fibonacci numbers. One day he came up with a problem. Given N pairs of numbers,he had to perform two types of operations. First type of operation was an update operation. In this operation, he was given three integers B ,P and Q. He had to replace the B^{th} pair (1 indexing) in the list with new pair of numbers P and Q. In the second type of operation, two integers L and R were provided. This time the task was to find the pair in the range L to R(both inclusive) with the maximum X value and to print the X value of that pair.
For a pair with values P and Q,
X = gcd(fib(P), fib(Q)) % M
Where fib(i) denotes the (ith Fibonacci) and M=10^{9}+7
Note : Consider 1 indexing and Fibonacci numbers starting with 1 i.e fib(1)=1,fib(2)=1,fib(2)=2,etc
Now, Abhishek has been given a list of operations to be performed.Help him to solve them correctly.
Input
The first line contains a single integer N denoting the number of pairs.
Each of the next N lines contain a pair of integers P and Q .
The next line contains a single integer K denoting the number of operations to be done.
Each of the next K lines denote either update or maximum operation. For an operation to be an update operation, there must be 4 integers such that the first integer is 0 which denotes it is an update operation (type 0) . The next 3 integers B, P and Q as described above denote the B^{th} pair to be replaced with P and Q. For maximum operation, there are 3 integers. The first integer is 1 (type 1 for maximum operation) and the next two integers L and R denote the range for the particular operation.
Output
Output answer of each operation of type 1(Maximum) separated by space.
Constraints
1<=N<=10^{5}
1<=P,Q<=10^{9}
1<=K<=10^{5}
1<=L<=R<=N
1<=B<=N
Example
Input
3
2 3
5 10
12 8
3
0 2 6 8
1 1 3
1 2 3
Output
3 3
Explanation
Pair 1:(2, 3),Pair 2:(5,10),Pair 3:(12,8)
The first operation is an update operation.
Thus Pair 2 changes to(6,8).
The next operation is to find the pair in the range [1,3] with maximum X value.
X value for pair 1:gcd(fib(2),fib(3))%(10^{9}+7)=gcd(1,2)%(10^{9}+7)=1
X value for pair 2:gcd(fib(6),fib(8))%(10^{9}+7)=gcd(8,21)%(10^{9}+7)=1
X value for pair 3:gcd(fib(12),fib(8))%(10^{9}+7)=gcd(144,21)%(10^{9}+7)=3
Thus,the maximum value of X is 3.
The next operation is again a type(1)maximum operation in the range [2,3]
X value for pair 2:1
X value for pair 2:3
Thus, the maximum value of X is 3.
Author:  vedipen 
Tags  vedipen 
Date Added:  18092016 
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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions