Problem E: Median I

Problem E: Median I

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2192  Solved: 258
[Submit][Status][Web Board]

Description

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.

Input

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

Output \(T\) lines. Each line contains an integer \(ans\), the median of  after combining the  subarray \(a[l..r]\)  and subarray \(b[l..r]\) .

Sample Input

5 2
1 3 5 7 9
2 3 4 5 6
5 5
1 5

Sample Output

6
4

HINT

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.

[Submit][Status]