题目压缩包(内含样例)

七萤有一段 $[1,n]$ 的整数区间，共包含 $n$ 个整数，还有 $k$ 种颜料，每种颜料对应唯一一种颜色。刚开始时，用第 $1$ 种颜料将所有点染色。然后进行 $q$ 次简单的染色。

每次简单染色的格式为：

$L$ $R$ $X$ $C_2$

其中 $[L,R]$ 表示需要进行简单染色的区间，$X$ 表示将这段区间进行 $X$ 染色。

$X$ 染色：若一个点的颜色为 $C_1$ ,则将其染成第 $((X \oplus {C_1}) \bmod k) + 1$ 种颜色（其中 $\oplus$ 为异或运算，$mod$ 为取模运算）。对于每次简单的染色之后，你需要输出这 $n$ 个点中颜色为 $C_2$ 的点的数量。

第一行三个整数 $n$ ($1 \leq n \leq 10^{15}$) , $q$ ($1 \leq q \leq 10^3$) , $k$ ($1 \leq k \leq n$) ，含义如上所述。

接下来 $q$ 行，每行四个正整数 $L$ $R$ $X$ $C_2$ ($1 \leq L \leq R \leq n$ , $1 \leq X \leq 10^{15}$, $1 \leq C_2 \leq k$) 表示一次简单的染色。

对于每次简单的染色，输出一个整数，表示答案。