Bob's math is really poor. He even doesn't know how does `carry' works in plus operation. In his world, the `plus' operation performed like this : , , , , , . Oh how poor his math is and he could even be the problem setter. Tragedy.

In his world, there is a `Wish' data structure. Let's see how it works:

•  [*.] Initially, there will be a list of numbers to initialize the data structure. After initialization, game begins:
• [1.] You may add a number to his data structure.

    

• [2.] You may divide all the numbers in the data structure by . (Note: it is integer division, for example, , , )

    

• [3.] You may query the largest result by given `plus' any number from his data structure.

    

• [4.] You may query `sum' ( by his poor math ) of numbers between and inclusive. It means, you need to find all numbers in his data structure that can meet , and conduct the `plus' one by one to get the `sum'.

    

Can you help naive Bob to implement data struct `Wish'?

输入描述:

At very beginning, there would be a number  indicates the number of tests. (  )
For each test case:
The first line contains two integers  and  indicates the number of initial numbers and number of operstions. ( and )
The second line contains  integers for the initial numbers .  
The following  lines would follow the operation format  to .
For the operations,  , 

输出描述:

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1).
For each operation  and , output the answer

1
4 5
1 2 88 29
Add 44
Query 71
Shift
Sum 0 10
Query 91

Case #1:
90
4
99

For Sample Case #1:
Initially: 
Add 44: 
Query 71: ; ; 
Shift:
Sum 0 10: 
Query 91: