Devamanyu and Sequences

Devamanyu likes sequences, so Shishir decided to give him a problem to solve. Shishir defines a sequence as: f(1) = 1 f(2) = 1 f(n) = A*f(n-1) + B*f(n-2) , for all n>2 Shishir will ask Q queries to Devamanyu, where each query consist of 4 integers l, r, A and B. For each query Shishir wants Devamanyu to find S(l,r). Where S(l,r) = f(l) + f(l+1) + ...... + f(r-1) + f(r) As this sum can be ve