#5159. 小花认为人生艰难

小花认为人生艰难

Description

人生是艰难的,但是小花决定把一道不是那么艰难的问题放在第二题。

小花会给你一个长为 nn 的序列 {a}\{a\} 和一个正整数 mm。定义一段区间的“艰难值” h(l,r)h(l,r) 如下:

$$h(l,r) = \sum_{l\leq x\leq y\leq r} \{a_{x} \operatorname{xor} a_{x+1} \operatorname{xor} a_{x+2}\cdots \operatorname{xor} a_y = m\}_{0~\mathrm{or}~1} $$

其中 xor\operatorname{xor} 为异或运算,{t}0 or 1=1\{t\}_{0~\mathrm{or}~1}=1 当且仅当 tt 为真,其余情况下均为 00

现在小花需要让你将 {a}\{a\} 划分为互不相交的恰好 pp 个连续段,且这些段的并等于 {a}\{a\} 。Ta 想知道,所有划分方案中,全部连续段的艰难值之和最小是多少?

形式化的讲,你需要确定一系列不交且并为 [1,n][1,n] 的恰好 pp 个区间 [li,ri][l_i,r_i] 使得

i=1ph(li,ri)\sum_{i=1}^p h(l_i,r_i)

最小。

Format

Input

第一行共 33 个正整数 n,p,mn, p, m,含义见题目描述。

接下来一行共 nn 个整数描述序列 {a}\{a\}

Output

输出一行共 11 个整数,表示所有划分方案中艰难值之和的最小值。

Samples

10 2 3
2 3 3 2 1 0 1 3 9 6
4

输入数据2

见样例文件 ex1.in

输出数据2

见样例文件 ex1.out

输入数据3

见样例文件 ex2.in

输出数据3

见样例文件 ex2.out

Constraints

对于前 20%20\% 的数据,满足 1n5001\leq n\leq 500

对于前 40%40\% 的数据,满足 1n50001\leq n\leq 50001p81\leq p\leq 8

对于前 60%60\% 的数据,满足 1n3×1041\leq n\leq 3\times 10^41p121\leq p\leq 120ai,m2×1050\leq a_i,m \leq 2\times 10^5

另有 10%10\% 的数据,满足 m=0m = 0

对于全部 100%100\% 的数据,满足 1n2×1051 \leq n \leq 2\times 10^51p201 \leq p \leq 200ai,m1060\leq a_i,m\leq 10^6