Tuenti Challenge 9

Challenge 19 - Go fix the gophers

Gofix is one of the leading companies in gopher game maintenance and you've been working there for two weeks. The best circus in the world has hired the services of your company. And your friend, Naomi Tomita or N.TT., thinks it might be a good opportunity for you to improve.

You get there and, as one would expect from the best circus in the world, its attractions are not common. The gopher game to be repaired consists of a circle of burrows and a single gopher. The movement of the gopher is clearly defined. The first gopher comes out of the first burrow and then it does T jumps. The possible jump lengths are defined in a list of integers (J). The jumps are always made in the same direction.

Since it's such hard work, N.TT. tells you to always start repairing the burrows that are most likely to be used.

With the help of N.TT., can you calculate how many times the gopher might come out of each burrow?

Input

The first line has an integer C, which is the number of cases for the problem. Each case starts with a line with four integers J, B, T and M, which are the possible jump lengths, the number of burrows (in log2), the time or number of jumps the gopher does and the modulo to use in the problem's output. The next line has J integers with the possible jump lengths.

Output

Each line should have the output "Case #x: ", followed by B integers with the number of times a gopher came out of the burrow counting every possibility, modulo M

Limits

  • 1 ≤ C ≤ 100
  • 1 ≤ T, J ≤ 1000
  • 1 ≤ B ≤ 12
  • 1 ≤ M ≤ 216

Examples


3
3 4 0 17
1 3 7
3 4 1 17
1 3 7
3 4 2 17
1 3 7

Gothers example

Sample Input

4
3 4 0 17
1 3 7
3 4 1 17
1 3 7
3 4 2 17
1 3 7
3 4 3 17
1 3 7

Sample Output

Case #1: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Case #2: 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
Case #3: 1 1 1 1 2 0 1 1 2 0 2 0 0 0 1 0
Case #4: 1 4 1 2 2 4 1 4 2 4 2 6 0 3 1 3

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.