D. MACARON Likes Happy Endings
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

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?

Input

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

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

Example
Input
10 4 5
1 2 3 4 5 5 6 5 4 3
Output
3
Note

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.