Description

MACARON 要读一本书，这本书包含 $n$ 章，第 $i$ 章有 $a_i$ 个字符。 MACARON 想在接下来的 $k$ 天内读完这本书。 每天，他要么从未读的第一章开始读若干章，要么就休息（不读书），但他必须在 $k$ 天内完成阅读。

MACARON 享受他的阅读时间，并喜欢圆满的结局，所以他不希望在这些日子里太过悲伤。 他有一个不吉利的数字 $d$，因为他认为数字 $d$ 会导致不好的结局。 我们用一个悲伤值来量化他每天的心情。 在第 $i$ 天，如果他阅读，假设他读了从 $L_i$ 到 $R_i$ 的章节。 这一天的悲伤值是满足 $L_i\leq l\leq r\leq R_i$ 且 $\bigoplus_{i=l}^r a_i=d$ 的区间 $[l, r]$ 的数量。 这里的 $\oplus$ 表示按位异或运算符。 如果他不读书，则悲伤值为 0。

MACARON 想安排他的阅读计划，以最小化 $k$ 天内悲伤值的总和。 你能帮他找到最小值吗？

Input Format

第一行包含三个整数 $n, k$ 和 $d$（$1\leq n\leq 10^5, 1\leq k\leq \min(n, 20), 0\leq d\leq 10^6$）——章节数、阅读天数和不吉利的数字。

第二行包含 $n$ 个整数 $a_i$（$0\leq a_i\leq 10^6$）——每章的字符数。

Output Format

输出一个整数，表示最小化后的悲伤值总和。

10 4 5
1 2 3 4 5 5 6 5 4 3

3

Hint

以下是一个最优的阅读计划：

• 第一天，休息，悲伤值为 0；
• 第二天，阅读第 1 章到第 3 章，悲伤值为 0；
• 第三天，阅读第 4 章到第 7 章，悲伤值为 2；
• 第四天，阅读第 8 章到第 10 章，悲伤值为 1。（由 ChatGPT 4o 翻译）