CF633H Fibonacci-ish II

Yash is finally tired of computing the length of the longest Fibonacci-ish sequence. He now plays around with more complex things such as Fibonacci-ish potentials. Fibonacci-ish potential of an array $ a_{i} $ is computed as follows: 1. Remove all elements $ j $ if there exists $ i<j $ such that $ a_{i}=a_{j} $ . 2. Sort the remaining elements in ascending order, i.e. $ a_{1}<a_{2}<...<a_{n} $ . 3. Compute the potential as $ P(a)=a_{1}·F_{1}+a_{2}·F_{2}+...+a_{n}·F_{n} $ , where $ F_{i} $ is the $ i $ -th Fibonacci number (see notes for clarification). You are given an array $ a_{i} $ of length $ n $ and $ q $ ranges from $ l_{j} $ to $ r_{j} $ . For each range $ j $ you have to compute the Fibonacci-ish potential of the array $ b_{i} $ , composed using all elements of $ a_{i} $ from $ l_{j} $ to $ r_{j} $ inclusive. Find these potentials modulo $ m $ .

N/A

N/A

For the purpose of this problem define Fibonacci numbers as follows: 1. $ F_{1}=F_{2}=1 $ . 2. $ F_{n}=F_{n-1}+F_{n-2} $ for each $ n>2 $ . In the first query, the subarray \[1,2,1\] can be formed using the minimal set {1,2}. Thus, the potential of this subarray is 1\*1+2\*1=3.