UNTITLE - Untitled

no tags 


Just passed a very important month of my life. Gained some things but also lost many more.

One of the many things, we gained is 50K+ people who at least know about computer programming. They will inform many others also. Many of us here have very bad luck to hear about programming in their CS course. Before that I also did not know that we can do many more things with computer except hearing music, watching movie and playing video games. Hope One day we will have 500K+. So Happy Coding.


The Problem

The Problem statement is Completely imagined. It have no relation to reality. If it matches any event It is just a coincidence.


In Our Programming Problem in Bangla group the members have been increased so fast. Seeing that the everyone was happy. Our Admin Hasan Vai had a tour in  “Noakhali” – one of the most important district in Bangladesh. On the way to noakhali he discovered something strange. He discovered that the members of the group are growing following a series.  After a lot more brainstorming he found the series like that –


(Xi) is 
Xi = Yi (for i <= k
Xi = C1 * Xi-1 + C2 * Xi-2 +.......+ Ck*Xi-k (for i > k


Here Xi  is the total members in ith time. Now he wants to find the members between time l to r. The results can be very large so he is calculating values modulo 109+7 (1000000007). As he is going to be very busy with teaching (really don’t know, infect he can be very busy with cutting cakes), he wants you to help him.  He will give you l and r, Q times and he wants you to find maximum 100 terms from Xl to Xr in non decreasing order.



Input :
First line contains T, the number of test cases. First line of each test case contains two space separated integers Q and k. Next line contains array Y of length k. 3rd line contains array C of length k. Each of next Q lines contains two space separated integers l and r.  Here,

1 <= T <= 10
1 <= Q <= 100 
1 <= k <= 5 
1 <= Yj, Cj <= 50 
1 <= l, r <= 10^6 
l <= r 

Output : 
For each test case output Case Number starting from 1 followed by Q lines. Each line contains terms from Xl to Xr in non decreasing order. If more than 100 terms are there you have to print first 100.


Sample Input


Sample Output


3 3
1 2 3
4 5 6
1 3
1 1
1 2

2 5
11 12 13 14 15
3 4 5 6 7
1 3
2 5

Case 1:
1 2 3
1 2
Case 2:
11 12 13
12 13 14 15



Problem Setter: Kazi Sadlil Rhythom

Added by:Najmuzzaman
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY