$N$마리 소 $(1 \le N \le 50,000)$는 편의상 $1..N$ 번호이며 암호화를 배웁니다. 예를 보고 스스로 만들기로 했지만 미숙해서 단순합니다:

소 $i$의 초기값은 $C_i$ $(0 \le C_i < 90,000,000)$이고 모두 병렬로 실행합니다:

• 먼저 각각 다른 $N-1$마리의 수의 합을 구합니다.
• 모두 끝나면 각자 계산한 합으로 자기 수를 바꿉니다. 큰 수를 피하려 $98,765,431$로 나눈 나머지를 저장합니다.

11월 말코손바닥사슴 Canmuu에게 말했고 그는 감탄했습니다.

안개 낀 크리스마스이브에 Canmuu가 말했습니다:

“쉽게 깨져! $T$번 $(1 \le T \le 1,414,213,562)$ 반복해.”

같은 지루한 계산을 많이 반복해 좌절한 소들은 수 시간 논쟁 끝에 Canmuu와 합의했습니다. 네가 암호화 후 수를 계산한다!

*이 문제 첫 10제출에는 추가 피드백이 있습니다.

입력

표준 입력으로 읽습니다.

• 1번 줄: 공백 구분 정수 $N$, $T$.
• $2..N+1$번 줄: $i+1$번 줄 한 정수 $C_i$.

출력

표준 출력에 씁니다.

• $1..N$번 줄: $i$번 줄은 끝의 소 $i$의 수인 한 정수, $98,765,431$로 나눈 나머지입니다.

예제

입력 1

3 4
1
0
4

출력 1

26
25
29

참고

초기값 $1$, $0$, $4$인 세 마리, 네 번 반복합니다.

매 회 소들의 수 표입니다:

문제 감사: Neal Wu, 2007