$N$ פרות $(1 \le N \le 50,000)$ ממוספרות בנוחות $1..N$ לומדות הצפנה. למדו דוגמאות ויוצרות משלהן! חסרות ניסיון, האלגוריתם פשוט:
פרה $i$ מקבלת התחלה $C_i$ $(0 \le C_i < 90,000,000)$, וכולן במקביל:
- תחילה כל אחת מסכמת מספרי $N-1$ האחרות.
- כשכולן סיימו, כל אחת מחליפה מספרה בסכום שחישבה. נגד מספרים גדולים שומרות שארית מודולו $98,765,431$.
בנובמבר סיפרו לאייל הקורא 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$, ארבע חזרות.
טבלת המספרים בכל סיבוב:
| סיבוב | פרה $1$ | פרה $2$ | פרה $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
תודות: Neal Wu, 2007