In a soccer game, n players are standing in a line, each player having a number from 1 to n. The coach decided that the team will make exactly m passes. The ball is initially with player number c. Also the coach instructs to pass only to players within a distance of Ak-1 towards either side holding the ball(between consecutive players distance is 1 unit) before the kth pass(for each k from 1 to m). You have to output the number of times each player had the ball in all possibilities of such games.

Soccer Line

Constraints:

0 < t <= 10

0 < n <= 10

0 < m <= 9

0 < c <=n

A[i] <= 4 for all i

Input Format:

first line contains the number of test cases t

for each test case you have two lines

line1 consists of n and m and c

line2 consists of array A of size m which represents the distance to which players can pass during each pass

Output Format:

result for each test case separated by newline

number of passes each player got separated by space

Sample Input:

1

4 2 3

1 2

Sample Output:

1 2 3 2

Explaination:

```
lets represent the player without ball by 0 and the player with a ball using 1
the the initial positioning looks like
No Pass Position : 0010
/ \
Pass 1 possible positions 0100 0001
/ | \ / \
Pass 2 possible positions 1000 0010 0001 0100 0010
During the 1st pass the player can only pass to distance one on either side (since A[0] is 1)
During the 2nd pass the player can only pass to distance two on either side (since A[1] is 2)
For player one there is only 1 case where he has the ball 1000 so output for player 1 is 1
For player two the cases where he has the ball are left scenario in pass 1 and left scenario in pass 2 (all 0100 cases) so his total is 2
similarly for player 3 it is 3 and for player 4 it is 2. Note that sum of all these numbers is equal to the nodes shown in the above tree.
```

Time Limit(s):

10

Memory Limit(MBs):

500