합의 합

$N$마리의 소가 $1$번부터 $N$번까지 번호를 달고 있습니다. 각 소 $i$는 처음에 정수 $C_i$를 가지고 있습니다. 소들은 다음 과정을 한 번의 라운드로 하여 모두 동시에 수행합니다.

• 각 소는 자신을 제외한 나머지 $N-1$마리 소가 가진 수의 합을 구합니다.
• 모든 소가 계산을 끝내면, 각 소는 자신의 수를 방금 구한 합으로 바꿉니다.

수가 지나치게 커지지 않도록 모든 수는 항상 98,765,431로 나눈 나머지로 관리합니다. 이 라운드를 정확히 $T$번 반복한 뒤, 각 소가 가진 수를 구하세요.

제약:

• $1 \le N \le 50{,}000$
• $0 \le C_i < 90{,}000{,}000$
• $1 \le T \le 1{,}414{,}213{,}562$

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $T$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 소 $i$의 시작 수 $C_i$가 주어집니다.

• $N$개의 줄을 출력합니다. $i$번째 줄에는 반복이 모두 끝난 뒤 소 $i$가 가진 수를 98,765,431로 나눈 나머지로 출력합니다.

다음은 예시에서 각 라운드가 끝난 뒤 소들이 가진 수를 정리한 표입니다.

          소가 가진 수
라운드   소1   소2   소3
 0        1     0     4
 1        4     5     1
 2        6     5     9
 3       14    15    11
 4       26    25    29