题目描述

MACARON is going to read a book, which contains $n$ chapters, and the $i$-th chapter has $a_i$ characters. MACARON wants to read this book in the next $k$ days. On each day, he either reads several chapters from the first unread chapter, or just takes a rest (does not read the book), but he should finish his reading in $k$ days.

MACARON enjoys his reading time and likes happy endings, so he does not want to be too sad during these days. He has an unlucky number $d$, because he thinks number $d$ will lead to a bad ending. We use a sadness value to quantify his mood on each day. On the $i$-th day, if he reads, suppose that he reads chapters from $L_i$ to $R_i$. The sadness value of this day is the number of intervals $[l, r]$ such that $L_i\leq l\leq r\leq R_i$ and $\bigoplus_{i=l}^r a_i=d$. The $\oplus$ denotes the bitwise XOR operator. If he doesn't read, let the sadness value be $0$.

MACARON wants to arrange his reading schedule to minimize the sum of sadness value in $k$ days. Can you help him find the minimum value?

输入格式

The first line contains three integers $n, k$ and $d$ ($1\leq n\leq 10^5, 1\leq k\leq \min(n, 20), 0\leq d\leq 10^6$) --- the number of chapters, the days for reading, and the unlucky number.

The second line contains $n$ integers $a_i$ ($0\leq a_i\leq 10^6$) --- the number of characters in each chapter.

输出格式

Output a single integer denoting the minimized sum of the sadness value.

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

3

提示

Here is an optimal schedule for reading:

• on the first day, just take a rest, and the sadness value is 0;
• on the second day, read from chapter 1 to chapter 3, and the sadness value is 0;
• on the third day, read from chapter 4 to chapter 7, and the sadness value is 2;
• on the fourth day, read from chapter 8 to chapter 10, and the sadness value is 1.