Gefnar eru jákvæðar heiltölur $N$ og $M$.
Fyrir hvert $k = 1, 2, \dots, N + M - 1$, látum $\text{ans}_k$ tákna svarið við eftirfarandi verkefni.
Par af runum $(a, b)$, þar sem $a = (a_1, a_2, \dots, a_{N+M-1})$ og $b = (b_1, b_2, \dots, b_{N+M-1})$, hvor um sig af lengd $N + M - 1$, kallast gott par af runum ef öll eftirfarandi skilyrði eru uppfyllt:
- $(a_1, b_1) = (1, N + 1)$
- Fyrir $i = 2, 3, \dots, N + M - 1$ gildir annað af eftirfarandi:
- $(a_i, b_i) = (a_{i-1} + 1, b_{i-1})$
- $(a_i, b_i) = (a_{i-1}, b_{i-1} + 1)$
- $(a_{N+M-1}, b_{N+M-1}) = (N, N + M)$
Fyrir gott par af runum $(a, b)$ skilgreinum við tré $T(a, b)$ á eftirfarandi hátt:
- Það er tré með $N + M$ hnútum sem eru merktir frá $1$ til $N + M$.
- Fyrir hvert $i = 1, 2, \dots, N + M - 1$ er leggur sem tengir hnút $a_i$ og hnút $b_i$.
Fyrir tré, látum $\text{dist}(i, j)$ vera fjölda leggja á einfalda veginum milli hnúta $i$ og $j$. Stigafjöldi trésins er skilgreindur sem fjöldi heiltalnapara $(i, j)$ þannig að $1 \le i < j \le N + M$ og $\text{dist}(i, j) = k$.
Reiknið summu stigafjölda $T(a, b)$ yfir öll góð pör af runum $(a, b)$, modulo $998244353$.
Reiknið öll gildin $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ og prentið $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, þar sem $\oplus$ táknar bitbundið XOR.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Öll inntaksgildi eru heiltölur.
Úttak
Prentið svarið.
Dæmi 1
2 2
14
Dæmi 2
24 167
21925979855
Dæmi 3
4297614 4167924
4162418864110099
Athugasemd
Í fyrsta dæminu er $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Því er gildið sem á að prenta $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.