Chef and Function

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has a sequence A containing N integers A_{1}, A_{2}, ..., A_{N} and an integer K.
For each pair (l, r) such that 1 ≤ l ≤ r ≤ N, Chef defines functions MIN(l, r) = min(a_{l}, a_{l+1}, ..., a_{r}) and XOR(l, r) = a_{l} xor a_{l+1} xor ... xor a_{r}. Then, Chef defines a function f(l, r) = MIN(l, r) ∙ XOR(l, r).
Chef wants to know the Kth smallest possible value of f(l, r). Formally, consider a sorted array of all N(N+1)/2 possible values of f(l, r) for all possible pairs (l, r); Chef wants to know the Kth element of this array after it's sorted.
Help Chef!
Input
 The first line of each test case contains two spaceseparated integers N and K.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
Output
For each test case, print a single line containing one integer — the Kth smallest value of f(l, r).
Constraints
 1 ≤ N ≤ 50,000
 1 ≤ K ≤ N ∙ (N+1) / 2
 1 ≤ A_{i} ≤ 50,000 for each valid i
Subtasks
Subtask #1 (10 points):
 1 ≤ N ≤ 100
 1 ≤ A_{i} ≤ 100 for each valid i
Subtask #2 (20 points):
 1 ≤ N ≤ 10,000
 1 ≤ A_{i} ≤ 100 for each valid i
Subtask #3 (30 points):
 1 ≤ N ≤ 30,000
 1 ≤ A_{i} ≤ 30,000 for each valid i
Subtask #4 (40 points): original constraints
Example
Input: 4 7 1 3 6 4 Output: 9
Example
There are N(N+1)/2 = 10 distinct pairs (l, r). The values of MIN(l, r), XOR(l, r) and f(l, r) for each pair are:
 l = 1, r = 1: MIN = 1, XOR = 1, f = 1
 l = 1, r = 2: MIN = 1, XOR = 2, f = 2
 l = 1, r = 3: MIN = 1, XOR = 4, f = 4
 l = 1, r = 4: MIN = 1, XOR = 0, f = 0
 l = 2, r = 2: MIN = 3, XOR = 3, f = 9
 l = 2, r = 3: MIN = 3, XOR = 5, f = 15
 l = 2, r = 4: MIN = 3, XOR = 1, f = 3
 l = 3, r = 3: MIN = 6, XOR = 6, f = 36
 l = 3, r = 4: MIN = 4, XOR = 2, f = 8
 l = 4, r = 4: MIN = 4, XOR = 4, f = 16
It's easy to see that the K=7th smallest value of MIN(l, r) ∙ XOR(l, r) is 9.
Note
:The time limit multiplier for python has been decreased to 3 from 5.
Author:  kefaa 
Tester:  mgch 
Editorial  https://discuss.codechef.com/problems/L56KTH 
Tags  binarysearch, kefaa, ltime56, mediumhard, persistence, trie 
Date Added:  18012018 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 