P15000 [HackerEarth] Bob is studying in a research institute. He is currently researching on integer sequences. He has already done some research on famous fibonacci sequence. Now he is trying to investigate
提高
题目描述

Bob is studying in a research institute. He is currently researching on integer sequences. He has already done some research on famous fibonacci sequence. Now he is trying to investigate patterns in a general recursive sequence (Ai)
Sequence (Ai) is
Ai = Bi (for i ≤ k)
Ai = C1 * Ai-1 + C2 * Ai-2 +.......+ Ck*Ai-k (for i > k)

But while calculating the sequence he realizes that values are growing very fast. So to keep the values small he calculates values modulo 10^9+7 (1000000007) . So that each term of sequence will be less than 10^9+7.

While he is busy with his work, his girlfriend is disturbing him a lot. He wants to make her busy with some task. He gives her the task of sorting all the terms from Al to Ar of his sequence. She is very quick so he gives her same task Q times (of course with different l and r). Since sorting is very boring task so she asks you to complete the task.
You will be given two numbers l and r and you are expected to output all the terms from Al to Ar in non decreasing order. But to avoid such a large output, if there are more than 100 terms in the output print only first 100.

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 B 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.

Output :
For each test case output Q lines. Each line contains terms from Al to Ar in non decreasing order. If more than 100 terms are there to output,print only first 100
Constraints :
1 ≤ T ≤ 3
1 ≤ Q ≤ 100
1 ≤ k ≤ 5
1 ≤ Bj,Cj ≤ 50
1 ≤ l,r ≤ 10^6
l ≤ r

SAMPLE INPUT
2
4 3
1 2 3
2 1 1
1 5
6 8
8 9
6 9
3 4
4 5 7 9
2 2 1 3
2 7
10 12
100 101

SAMPLE OUTPUT
1 2 3 9 23
58 148 377
377 960
58 148 377 960
5 7 9 49 138 404
9964 29126 85073
483689722 905484679

输入格式

见题面

输出格式

见题面

样例输入
3 5 4 7 14 38 9 28 43 44 34 23 88656 84 81539 65 203215 63 828883 13 792311 76 2 27 31 28 23 43 113924 90 841977 49 676447 24 243579 27 487731 24 226271 66 429998 59 530563 18 94755 17 70946 34 294276 20 19374 76 907996 16 291911 87 514967 65 125410 84 152518 88 208463 52 685530 99 75289 54 617470 94 137859 67 941804 57 341410 72 909926 31 322113 71 676991 18 868139 82 184848 95 406658 25 435005 64 384869 58 382009 46 490367 60 487530 31 997715 51 86848 29 105990 68 30567 73 296459 53 336813 36 68042 83 235022 69 137582 68 826303 89 162192 26 930170 50 264782 88 214997 90 519256 75 640266 50 60474 73 14157 70 380346 79 507447 85 882866 52 43244 64 659483 57 426254 57 365826 81 712083 60 409160 15 785032 32 453500 57 303290 47 850283 96 929474 68 612365 90 926846 22 920583 27 835498 19 388670 68 227021 71 953638 65 892172 80 401185 65 4 1 16 48 2 3 30 48 42 86 261928 40 224531 92 979825 22 402605 97 952437 96 124915 47 546594 80 856065 61 117504 99 833454 83 97035 68 351552 44 932501 62 654837 44 845370 50 660214 78 558060 13 475392 31 42089 56 330395 92 682679 27 256890 78 272104 33 508814 52 114108 90 69167 38 497092 94 602065 51 800508 56 513652 77 709581 29 478012 11 494368 31 503741 100 529929 11 621464 57 350322 45 9654 17 506338 88 833216 57 450177 33 607093 55 588939 21 48799 25 537596 28 307502 40 246173 76 836457 95 538843 66 167074 17 392506 66 267550 85 926645 100 522666 34 531308 53 210585 93 78810 89 654358 20 125243 40 668284 31 685440 46 127167 15 679708 36 495570 14 678984
样例输出
1 2 3 9 23 9 23 58 148 28071110 71492016 261981 667218 1699283 5 7 9 49 138 404 9964 29126 85073 483689722 905484679