你知道四千很喜歡玩Hollow Knight。遊戲中的小騎士，在深入地底探索這充滿bug的世界的同時，也探索自身存在的意義。

這款遊戲最具特色也最有趣的地方便是boss戰裡的各種攻擊招式了。一隻boss擁有$M$種招式，在血量降為$0$前不斷選出一種招式攻擊小騎士。四千雖然知道每種招式的躲法，常常卻因為無法及時判斷這是哪種招式而讓小騎士受傷。有天四千發現，一隻boss的出招順序是一個$Q$循環。將boss的招式編號為$0, 1, \ldots, M-1$，則第$N (1 \leq N \leq Q)$次的攻擊招式由下方的C函式給出：

long long ChooseAttack(int N){
    long long sum = 0;
    for(int i=0; i<=K; i++){
        long long p = 1;
        for(int j=1; j<=i; j++){
            p = (a[N]*p) % M;
        }
        sum = (sum + c[i]*p) % M;
    }
    return sum;
}

其中$K$是個全域long long變數，而$\{a_i\}_{i=1}^Q$和$\{c_i\}_{i=0}^K$都是全域long long陣列。不幸的是，四千發現他的C compiler又壞了，因為當$K=60000$時，光是計算ChooseAttack(1)就花了他幾十秒，更別提算完ChooseAttack(2), ChooseAttack(3), ..., ChooseAttack(Q)了。現在他給你$M, Q, K, \{a_i\}_{i=1}^Q, \{c_i\}_{i=0}^K$，請你用ZJ的compiler幫他算出ChooseAttack(1), ChooseAttack(2), ..., ChooseAttack(Q)的值。