Macaron's Happy Reading Schedule

MACARON has a book with \( n \) chapters, where the \( i \)-th chapter has \( a_i \) characters. He wants to finish reading the book in the next \( k \) days. On each day, he either reads a contiguous block of chapters starting from the first unread chapter or he takes a rest (reads nothing). Note that he must finish reading the entire book within \( k \) days, but he is allowed to take rest on some days.

MACARON is superstitious and dreads his unlucky number \( d \). For a day when he reads, suppose he reads chapters from \( L_i \) to \( R_i \). The sadness value of that day is defined as the number of subintervals \( [l, r] \) (with \( L_i \le l \le r \le R_i \)) such that \[ \bigoplus_{j=l}^{r} a_j = d \; , \] where \( \oplus \) denotes the bitwise XOR operator. If he takes a rest on a day, the sadness value is \( 0 \).

MACARON wants to plan his reading schedule so that the sum of daily sadness values over the \( k \) days is minimized. Help him determine the minimum possible total sadness.

Note: Even if MACARON reads on only a subset of the \( k \) days (thus leaving some days as rest days), the reading days must cover all chapters in order.

inputFormat

The first line contains three integers \( n \), \( k \), and \( d \) (the number of chapters, the number of days, and the unlucky number) separated by spaces.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) representing the number of characters in each chapter.

outputFormat

Output one integer: the minimum total sadness value achievable with an optimal reading schedule over \( k \) days.

sample

3 2 0
1 1 1

1