$\textrm{mex}$ của một đoạn trong dãy số được định nghĩa là số tự nhiên nhỏ nhất không xuất hiện trong đoạn đó. Giá trị của một dãy số được định nghĩa là số lượng các đoạn con có $\textrm{mex} \geq k$.

Cho $n$ số tự nhiên nhỏ hơn $m$ và một đoạn $[l, r]$. Gọi $f(k)$ là giá trị lớn nhất của giá trị dãy số trong tất cả các hoán vị của $n$ số đã cho. Với mỗi $k \in [l, r]$, hãy tính $f(k)$.

Gọi $a_i$ là số lần xuất hiện của số $i$. Đảm bảo rằng tồn tại số nguyên dương $X$ sao cho $\forall i < m, a_i \in \{X, X+1\}$.

Dữ liệu vào

Vì $n$ có thể rất lớn, dữ liệu được cung cấp theo cách sau để giảm dung lượng:

Dòng đầu tiên chứa bốn số nguyên $m, l, r, X$.

Dòng thứ hai chứa một xâu nhị phân độ dài $m$. Nếu vị trí thứ $i$ là $1$, số lần xuất hiện của số $i-1$ là $X+1$, ngược lại số lần xuất hiện là $X$.

Từ dữ liệu đầu vào, ta có thể suy ra $n = mX + S$, trong đó $S$ là số lượng chữ số $1$ trong xâu nhị phân.

Dữ liệu ra

Để giảm dung lượng đầu ra, gọi $ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$, trong đó $\displaystyle\bigoplus$ biểu thị phép toán XOR theo bit. Hãy in ra một số nguyên duy nhất là $ans$.

Dữ liệu giới hạn

• Subtask 1 (5 điểm): $n, m \leq 9$.
• Subtask 2 (15 điểm): $n, m \leq 200$.
• Subtask 3 (15 điểm): $n, m \leq 5 \times 10^3$.
• Subtask 4 (5 điểm): $m \leq 2, l = 0, r = 1$.
• Subtask 5 (10 điểm): $m \leq 10^6, l = m, r = m$.
• Subtask 6 (10 điểm): $m \leq 10^6, X = 1, s_i = 0$.
• Subtask 7 (15 điểm): $m \leq 10^6, r - l + 1 \leq 10^4$.
• Subtask 8 (15 điểm): $m \leq 2 \times 10^6$.
• Subtask 9 (10 điểm): Không có hạn chế đặc biệt.

Đối với tất cả các dữ liệu, thỏa mãn $n \leq 10^9, m \leq 10^7, 0 \leq l \leq r \leq m, X \geq 1$.

Ví dụ

Dữ liệu vào 1

2 0 1 2
10

Dữ liệu ra 1

3034

Ghi chú

Trong dãy số được cho ở ví dụ, có $3$ số $0$ và $2$ số $1$. Với mọi hoán vị, $f(0)$ đều bằng $15$. Với hoán vị $\textrm{01010}$, $f(1)$ đạt giá trị lớn nhất là $13$. Kết quả là: $$ \displaystyle (233^0 \times 15 \bmod 998244353) \oplus (233^1 \times 13 \bmod 998244353) = 3034 $$

Dữ liệu vào 2

14 1 14 13
10110101110101

Dữ liệu ra 2

379883349