Background

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 –

(X_i) is 
X_i = Y_i (for i <= k) 
X_i = C₁ * X_i-1 + C₂ * X_i-2 +.......+ C_k*X_i-k (for i > k) 

Here X_i  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 10⁹+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 X_l to X_r 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. 3^rd 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 <= Y_j, C_j <= 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 X_l to X_r in non decreasing order. If more than 100 terms are there you have to print first 100.

Problem Setter: Kazi Sadlil Rhythom