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

_{1},d_{1}), F(a_{2},d_{2}), F(a_{3},d_{3}),... F(a_{n},d_{n}). Let G(a_{1},a_{2},... a_{n},d_{1},d_{2},... 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

_{1}, A

_{2}, A

_{m}, and terms of the second sequence be B

_{1}, B

_{2},... B

_{m}. The sequence obtained by multiplying these two sequences is: A

_{1}*B

_{1}, A

_{2}*B

_{2},... A

_{m}*B

_{m}. We also give the definition for the k

^{th}difference of a sequence. If A

_{1}, A

_{2},... A

_{m,...}be the terms of a sequence, then the terms of the 1

^{st}difference of this sequence are given by A

_{2}-A

_{1}, A

_{3}-A

_{2},... A

_{m}-A

_{m-1},... In general, if A

_{1}, A

_{2},... 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

_{2}-A

_{1}, A

_{3}-A

_{2},... 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

_{1},a

_{2},... a

_{n},d

_{1},d

_{2},... d

_{n},p

_{1},p

_{2},... p

_{n}) is defined as => product of F'(a

_{1},d

_{1},p

_{1}), F'(a

_{2},d

_{2},p

_{2}),... 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

2.) 1 i j v => 1 indicates an update (1<=i<=j<=n). For all i<=k<=j, we update p

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.