Բիթային AND և OR

Էդուարդը և Էլիզան սիրում են միասին հաղթահարել կամայական ինտելեկտուալ խաղ և այսօր նրանց առաջադրվել է հետևյալ խնդիրը.

Շրջանաձև կանգնած են n մարդիկ, որոնցից յուրաքանչյուրը ունի գիտելիքի աստիճան՝ $A_1, A_2, A_3, ..., A_n$: Դա նշանակում է, որ $A_i$-ի ձախ մասում կանգնած է $A_{i-1}$-ը, երբ i > 1, իսկ $A_1$-ի ձախ մասում $A_n$-ը, $A_i$-ի աջ մասում կանգնած է $A_{i+1}$-ը, երբ i < n, իսկ $A_n$-ի աջ մասում կանգնած է $A_1$-ը:

Էդուարդին և Էլիզային անհրաժեշտ է մարդկանց բաժանել k անընդհատ խմբերի այնպես, որ ամեն մարդ լինի ճիշտ մի խմբում, բոլոր մարդիկ մասնակցեն և այդ բաժանման հզորությունը լինի մաքսիմալ: Բաժանման հզորությունը հավասար է խմբերի հզորությունների բիթային AND-ին, իսկ խմբի հզորությունը հավասար է խմբում մարդկանց գիտելիքների աստիճանի բիթային OR-ին:

Էդուարդը և Էլիզան իրար շատ լավ են հասկանում և այս խնդիրը լուծեցին շատ արագ, հերթը ձերն է:

Մուտքային տվյալներ

Առաջին տողում տրված են n-ը և k-ն: Երկրորդ տողում տրված են մարդկանց գիտելիքների աստիճանները (0 ≤ Ai < $2^{30}$):

Ելքային տվյալներ

Բաժանման առավելագույն հզորությունը:

Սահմանափակումներ

• Թեստերի առաջին խմբի համար 1 ≤ k ≤ n ≤ 1000։

• Թեստերի երկրորդ խմբի համար 1 ≤ k ≤ n ≤ 500 000։

Օրինակներ

Աղբյուրը. Մարզային 2020