E. Хүүхэд ба хоёртын мод

хугацааны хязгаарлалт 7 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Манай хүүхэд компьютерийн шинжлэх ухаанд маш их дуртай, ялангуяа тэр хоёртын модонд дуртай.

$n$ ялгаатай эерэг бүхэл тоонуудын дарааллыг авч үзье: $c_{1}, c_{2}, ..., c_{n}$. Ямар нэг $v$ оройн жин нь ${c_{1}, c_{2}, ..., c_{n}}$ олонлогийнх бол оройнууд нь жинтэй үндэстэй хоёртын модыг сайн гэж дууддаг. Мөн манай хүүхэд оройнууд нь жинтэй хоёртын модны жинг бүх оройнуудын жингийн нийлбэр гэж боддог.

$m$ бүхэл тоо өгөгдсөн, бүх $s$ $(1 ≤ s ≤ m)$-н хувьд $s$ жинтэй байх оройнууд нь жинтэй үндэстэй сайн хоёртын моднуудыг тооцоолж чадах уу? Ямар моднуудыг өөр өөр гэж үздэгийг ойлгохын тулд жишээг харна уу.

Бид зөвхөн $998244353$ ($7 × 17 × 2^{23} + 1$, анхны тоо) модулиар хариуг мэдэхийг хүсэж байна.

Оролт

Эхний мөр нь $n, m$ $(1 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 10^{5})$ хоёр бүхэл тооноос бүрдэнэ. Хоёр дахь мөр нь зайгаар тусгаарлагдсан $n$ ширхэг ялгаатай бүхэл $c_{1}, c_{2}, ..., c_{n}$. $(1 ≤ c_{i} ≤ 10^{5})$ тоонуудаас бүрдэнэ.

Гаралт

$m$ мөрүүд хэвлэх ба мөр бүр нь нэг бүхэл тооноос бүрдэнэ. $i$-р мөрөнд нийт яг $i$ жинтэй байх оройнууд нь жинтэй үндэстэй сайн хоёртын моднуудын тоог хэвлэх ёстой. Хариуг $998244353$ ($7 × 17 × 2^{23} + 1$, анхны тоо) модулиар хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2 3
1 2
Гаралт
1
3
9
Оролт
3 10
9 4 3
Гаралт
0
0
1
1
0
2
4
2
6
15
Оролт
5 10
13 10 6 4 15
Гаралт
0
0
0
1
0
1
0
2
0
5

Тэмдэглэл

Эхний жишээнд, нийт $3$ жинтэй байх оройнууд нь жинтэй үндэстэй сайн хоёртын моднууд $9$ байна:

Сэтгэгдлүүдийг ачааллаж байна...