题目背景

望眼欲穿的回信总是在收信人离开时送达的。

题目描述

漫漫冬日，我坐在火车上，看着无边的荒漠，雨水落在车窗上。沿途我经过了 $n$ 处风景，每一处风景我都标记了一个浪漫值 $a_i$。昏暗的灯光，从清晨到黄昏，下车时，所有的记忆都已经模糊。我只能依稀记得，每一处风景的风景值 $a_i$ 属于一个区间 $[l_i,r_i]$，特别的，保证 $r_i-l_i+1=L$ 为一定值。设 $m$ 为一定值，数据保证 $a_i<2^m$。

我对于有些风景的记忆是独特的，然而如今也已忘却了。设 $U$ 为 $\{a_1,a_2...a_n\}$ 表示全体风景的集合，我将任意挑选一个集合 $T$ 为 $U$ 的子集为我拥有独特记忆的风景集合（注意 $T$ 可能为空）。

现在我的脑海中开始回放过去的记忆，每一次我会从独特的风景子集 $T$ 中挑选一个子集 $S$，来回顾这一趟旅途，并积累我的满意度 $X$ 变为 $X$ 异或上 $S$ 内所有风景的风景值。特别的，当 $S$ 为空时，$X$ 保持不变，$X$ 的初始值为 $0$。

我将进行 $N$ 次回顾，并最终得到一个满意值 $X$。我希望对于所有 $c\in [0,2^m)$ 知道对于所有可能的回顾旅途的方案，有多少种回顾旅途的方案使得满意值 $X=c$。

其中，两个方案不同当且仅当：对于某个 $i$ 有 $a_i$ 不同，或者 $T$ 的选取不同，或者某次回顾时，$S$ 的选取不同。

为了避免输出规模过大，设 $ans_i$ 表示使得 $X=i$ 的方案数对 $998244353$ 取模的结果，你只需要输出 $\bigoplus_{i=0}^{2^m-1} (ans_i+i)$。

输入格式

从文件 train.in 中读入数据。

第一行四个正整数分别代表 $m,n,L,N$

接下来一行 $n$ 个正整数，第 $i$ 个正整数代表 $l_i$，表示风景值的取值范围的左端点。

输出格式

输出到文件 train.out 中。

一行一个整数表示答案。

样例 1 输入

2 2 1 2
1 3

样例 1 输出

1

样例 1 说明

对于 $X=0,1,2,3$ 方案数分别为：$9,6,4,6$。

样例 2/3/4

见下发文件 train2/3/4.in/ans。

数据范围

对于全部数据：保证 $n\le 2\times 10^5,m\le 22,L\le 32,N\le 10^9$。

sample