## Little Monk

QUESTION

Little monk has travelled across the world but he has never seen a place like byteland. The mountains in the byteland have a unique order. Height of ith mountain is represented by an interval (li,ri) i.e. the height of the mountain is in increasing order, li,li+1,li+2,….,ri. The heights of mountains are such that if i<j then ri<lj. Now the little monk wants to know xth smallest height in the byteland.\nNote: x will be always in the given range of intervals.\nInput Format:\nFirst line contains two space separated integers, N (1N105) and Q(1Q105), number of mountains and number of queries.\nNext N lines contains two separated integers each, li and ri (1li,ri1018). ith line contains the starting height and the end height of the ith mountain.\nNext Q lines contains one integer, x (1×1018), each, denoting the queries.\nOutput Format:\nFor each query, print xth smallest height in the byteland\n\n.

“TESTCASE_1”: “3 3\n1 10\n11 20\n21 30\n5\n15\n25\n###—###SEPERATOR—###—\n5\n15\n25”, “TESTCASE_2”: “4 4\n2 14\n9 22\n21 34\n44 65\n6\n20\n34\n###—###SEPERATOR—###—\n7\n15\n27\n27”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include <stdio.h>
#define ll long long int

int binarySearch(ll arr[], ll x, int l, int h) {
int mid = l + (h - l) / 2;
if (l < h) {
if (arr[mid] > x) return binarySearch(arr, x, l, mid);
if (arr[mid] < x) return binarySearch(arr, x, mid+1, h);
return mid;
}
return mid;
}

int main() {
int n, Q, i, pos;
scanf("%d%d", &n, &Q);
ll Height[n], mountain[n], x;
for (i = 0; i < n; ++i) {
scanf("%lld %lld",&Height[i],&mountain[i]);
mountain[i] -= (Height[i] - 1);
if (i > 0) mountain[i] += mountain[i-1];
}
while (Q--) {
scanf("%lld",&x);
if (x <= mountain[0])
printf("%lld\n", Height[0] + x - 1);
else {
pos = binarySearch(mountain, x, 0, n);
printf("%lld\n", Height[pos] + (x - mountain[pos-1] - 1));
}
}
}``````