Arithmetic Progression

Just solved the hard problem Arithmetic Progression at interviewstreet, and i found it interesting so i decided to share its idea with you.

Problem

 

Let F(a,d) denote an arithmetic progression (AP) with first term 'a' and common difference 'd'. i.e  F(a,d) denotes an infinite AP => a, a+d, a+2d, a+3d,... You are given 'n' APs => F(a₁,d₁), F(a₂,d₂), F(a₃,d₃),... F(a_n,d_n). Let G(a₁,a₂,... a_n,d₁,d₂,... d_n) denote the sequence obtained by multiplying the 'n' APs.

Multiplication of 2 sequences is defined as follows: Let the terms of the first sequence be A₁, A₂, A_m, and terms of the second sequence be B₁, B₂,... B_m. The sequence obtained by multiplying these two sequences is: A₁*B₁, A₂*B₂,... A_m*B_m. We also give the definition for the k^th difference of a sequence. If A₁, A₂,... A_m,... be the terms of a sequence, then the terms of the 1^st difference of this sequence are given by A₂-A₁, A₃-A₂,... A_m-A_m-1,... In general, if A₁, A₂,... A_m,... be the terms of the k^th difference of a sequence, then the terms of the k+1^th difference are given by A₂-A₁, A₃-A₂,... A_m-A_m-1,... We say that the k^th difference of a sequence is a constant, if all the terms of the k^th difference are equal.

Let F'(a,d,p) be a sequence defined as => a^p, (a+d)^p, (a+2d)^p,... Similarly, G'(a₁,a₂,... a_n,d₁,d₂,... d_n,p₁,p₂,... p_n) is defined as => product of F'(a₁,d₁,p₁), F'(a₂,d₂,p₂),... F'(a_n,d_n,p_n). Now, your task is to find the smallest 'k' for which the k^th difference of the sequence G' is a constant. You are also required to find this constant value.

You will be given many operations. Each operation is of one of the 2 forms:
1.) 0 i j => 0 indicates a query (1<=i<=j<=n).You are required to find the smallest 'k' for which the  k^th difference of G'(a_i,a_i+1,... a_j,d_i,d_i+1,... d_j,p_i,p_i+1,... p_j) is a constant. You should also output this constant value.
2.) 1 i j v => 1 indicates an update (1<=i<=j<=n). For all i<=k<=j, we update p_k = p_k+v.

Input:

The first line of input contains a single integer 'n', denoting the number of APs. Each of the next 'n' lines consists of 3 integers a_i, d_i, p_i (1<=i<=n). The next line consists of a single integer 'q', denoting the number of operations. Each of the next 'q' lines consist of one of the two operations mentioned above.

Output:

For each query, output a single line containing 2 space separated integers 'K' and 'V'. 'K' is the least value for which the K^th difference of the required sequence is a constant. 'V' is the value of this constant. Since 'V' might be large, output the value of 'V' modulo 1000003.

Note: 'K' will always be such that it fits into a signed 64-bit integer. All indices for query and update are 1-based. Do not take modulo 1000003 for 'K'.

Constraints:

1<=n<=100000
1<=a_i, d_i, p_i<=10000
1<=q<=100000
For updates of the form "1 i j v", 1 <= v <= 10000

Solution

Unfortunately i tried to find anything related to number theory to find an equation to help solving this problem, but i couldn't find anything useful, actually that's why i managed to share it with you. I did some calculations by my own and i got some interesting equations to solve this problem, and here we go:

To get the K and V for an AP F(A, D, P):

K = P, V = D^P*P!

To get the K and V for F(A1, D1, P1)*F(A2, D2, P2)*F(A3, D3, P3):

I found that K will always equal to: P1+P2+P3.

And with the help of my friend Neal Zane, he helped me to find that V = (D1^P1*D2^P2*D3^P3)*(P1+P2+P3)!.

Now by knowing all the equations needed to solve this problem, we will use segment trees to solve this problem.