No‐Carry Addition Subsequence Sum

You are given two integers \(m\) and \(k\), and a sequence \(S\) of \(n\) natural numbers such that \(S \subseteq \{0,1,\dots,k^m-1\}\). Each number is represented in base \(k\) with at most \(m\) digits (leading zeros are allowed).

The no‐carry addition in base \(k\) is defined as follows. For any two numbers \(x\) and \(y\) having their base \(k\) representations as \(x = \sum_{i=0}^{m-1} x_i k^i\) and \(y = \sum_{i=0}^{m-1} y_i k^i\) (where \(0 \le x_i,y_i < k\)), their no‐carry sum is the number \(z\) whose base \(k\) digits satisfy \[ z_i = (x_i+y_i) \mod k, \quad \text{for } i=0,1,\ldots,m-1. \] Thus, the no‐carry sum is computed by adding the corresponding digits modulo \(k\) without carrying over.

For any subsequence \(R\) of \(S\) (possibly empty), define its weight \(W(R)\) as the no‐carry sum (in base \(k\)) of all its elements. Equivalently, if we write each number \(a \in R\) in base \(k\) as \(a = \sum_{i=0}^{m-1} a_i k^i\), then \[ W(R) = \sum_{i=0}^{m-1} \Bigl(\sum_{a\in R}a_i \mod k\Bigr) k^i. \]

Your task is to compute, for every \(t=0,1,2,\dots,k^m-1\), the value \[ Ans[t] = \sum_{R \subseteq S}\bigl[ W(R)=t \bigr], \] where \([P]\) is 1 if the predicate \(P\) is true and 0 otherwise. Note that, since every subsequence is counted, we have \[ \sum_{t=0}^{k^m-1}{Ans}[t] = 2^n. \]

Help our beleaguered problemsetter compute all these counts!

inputFormat

The first line of the input contains three integers \(m\), \(k\), and \(n\).

The second line contains \(n\) space‐separated integers representing the sequence \(S\). It is guaranteed that \(0 \leq S_i < k^m\) for all \(i\).

outputFormat

Output \(k^m\) integers in one line separated by spaces. The \(t\)th integer (starting from \(t=0\)) should be equal to \(Ans[t]\), the number of subsequences of \(S\) whose no‐carry sum is \(t\).

sample

1 10 2
1 9

2 1 0 0 0 0 0 0 0 1