{"raw_statement":[{"iden":"background","content":"dottle bot。"},{"iden":"statement","content":"定义一个数列区间的 $\\textrm{mex}$ 为区间中最小的没有出现过的自然数，定义一个数列的价值为其中 $\\textrm{mex}\\geq k$ 的区间数量。\n\n给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$，令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值，对于每一个 $k\\in [l,r]$，求出 $f(k)$。\n\n令 $a_i$ 表示数字 $i$ 出现的次数，保证存在正整数 $X$，使得  $\\forall i\\le m-1,a_i\\in \\{X,X+1\\}$。"},{"iden":"input","content":"由于 $n$ 可能很大，将采取如下方式减少读入量：\n\n第一行四个整数 $m,l,r,X$。\n\n第二行一个长度为 $m$ 的 $01$ 串，若其中第 $i$ 个位置为 $1$ 则数字 $i-1$ 的出现次数为 $X+1$，否则出现次数为 $X$。\n\n根据输入可以推出 $n=mX+S$，其中 $S$ 为 $01$ 串中 $1$ 的数量。"},{"iden":"output","content":"为了减少输出量，令 $ans=\\displaystyle{\\bigoplus_{i=l}^r}  (233^if(i)\\bmod 998244353)$，其中 $\\displaystyle\\bigoplus$ 表示二进制下的按位异或，输出一行一个整数 $ans$。"},{"iden":"note","content":"#### 样例 1 解释\n\n在样例给出的数列中，有 $3$ 个 $0$ 和 $2$ 个 $1$，任意排列 $f(0)$ 均为 $15$，排列为 $\\textrm{01010}$ 时 $f(1)$ 有最大值 $13$，答案为：\n$$\n\\displaystyle (233^0\\times 15\\bmod 998244353)\\oplus(233^1\\times 13\\bmod 998244353)=3034\n$$\n\n#### 数据范围\n\n- Subtask 1（5 points）：$n,m\\leq 9$。\n- Subtask 2（15 points）：$n,m\\leq 200$。\n- Subtask 3（15 points）：$n,m\\leq 5\\times 10^3$。\n- Subtask 4（5 points）：$m\\leq 2$，$l=0$，$r=1$。\n- Subtask 5（10 points）：$m\\leq 10^6$，$l=m$，$r=m$。 \n- Subtask 6（10 points）：$m\\leq 10^6$，$X=1$，$s_i=0$。\n- Subtask 7（15 points）：$m\\leq 10^6$，$r-l+1\\leq 10^4$。\n- Subtask 8（15 points）：$m\\leq 2\\times 10^6$。\n- Subtask 9（10 points）：无特殊限制。\n\n对于所有数据，满足 $n\\leq 10^9$，$m\\leq 10^7$，$0\\leq l\\leq r\\leq m$，$X\\geq 1$。"}],"translated_statement":null,"sample_group":[["2 0 1 2\n10","3034"],["14 1 14 13\n10110101110101","379883349"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}