CF117D Not Quick Transformation

Let $ a $ be an array consisting of $ n $ numbers. The array's elements are numbered from $ 1 $ to $ n $ , $ even $ is an array consisting of the numerals whose numbers are even in $ a $ ( $ even_{i}=a_{2i} $ , $ 1

The first line contains three integers $ n $ , $ m $ , $ mod $ ( $ 1

Print $ m $ lines each containing an integer — remainder modulo $ mod $ of the query result.

Let's consider the first example. First let's construct an array $ b=F(a)=F([1,2,3,4]) $ . - Step 1. $ F([1,2,3,4])=F([1,3])+F([2,4]) $ - Step 2. $ F([1,3])=F([1])+F([3])=[1]+[3]=[1,3] $ - Step 3. $ F([2,4])=F([2])+F([4])=[2]+[4]=[2,4] $ - Step 4. $ b=F([1,2,3,4])=F([1,3])+F([2,4])=[1,3]+[2,4]=[1,3,2,4] $ Thus $ b=[1,3,2,4] $ . Let's consider the first query $ l=2,r=3,u=4,v=5 $ . The second and third positions in the array $ b $ do not have numbers in the range $ [4,5] $ , so the sum obviously equals zero. Let's consider the second query $ l=2,r=4,u=1,v=3 $ . The second and third positions have two numbers that belong to the range $ [1,3] $ , their sum equals 5.