Given two nondecreasing sequences \(a\) and \(b\), and their length are both \(n\). What's the median of after combining the subarray \(a[l..r]\) and subarray \(b[l..r]\) ?
Subarray \(a[l..r]\) is a sub-array of \(a\), it includes \(a_l, a_{l+1} ... a_r\) for \(1≤l≤r≤n\), its length is \(r−l+1\).
You’d like to determine the median of this set of \(2k(k=r-l+1)\) values, which we will define here to be the \(k\)-th smallest value. For example: median([1,2,3,4])=2.
The 1st line contains two positive integers \(n(1⩽ n ⩽ 100000)\) and \(T(1⩽ T ⩽ 100000)\) which is the number of testcase.
The 2nd line contains \(n\) integers: \(a_1, a_2 ... a_n\). For each \(a_i(0⩽ a_i ⩽ 10^9)\)
The 3rd line contains \(n\) integers: \(b_1, b_2 ... b_n\). For each \(b_i(0⩽ b_i ⩽ 10^9)\)
Then \(T\) lines follow. Each line contains two integers \(l\) and \(r(1⩽ l ⩽ r ⩽ n)\) for a test case.
Output \(T\) lines. Each line contains an integer \(ans\), the median of after combining the subarray \(a[l..r]\) and subarray \(b[l..r]\) .
The correspond solutions to the sample is :
(1)\(a_5\)=9, \(b_5\)=6, after combining is [9 6], the median is 6.
(2)Combine \(a\) and \(b\) then sort it can get [1 2 3 3 4 5 5 6 7 9], the median is 4.