Little Monk and Mountains
Tag(s):

## Algorithms, Binary Search, Easy-Medium

Problem
Editorial
Analytics

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 $i^{th}$ mountain is represented by an interval $(l_i,\;r_i)$ i.e. the height of the mountain is in increasing order, $l_i, l_i+1, l_i+2, ...., r_i$. The heights of mountains are such that if $i < j$ then $r_i < l_j$. Now the little monk wants to know $x^{th}$ smallest height in the byteland.

Note: x will be always in the given range of intervals.

Input Format:
First line contains two space separated integers, N $(1 \le N \le 10^5)$ and Q $(1 \le Q \le 10^5)$, number of mountains and number of queries.
Next N lines contains two separated integers each, $l_i$ and $r_i$ $(1 \le l_i, r_i \le 10^{18})$. $i^{th}$ line contains the starting height and the end height of the $i^{th}$ mountain.
Next Q lines contains one integer, x $(1 \le x \le 10^{18})$, each, denoting the queries.

Output Format:
For each query, print $x^{th}$ smallest height in the byteland.

SAMPLE INPUT
3 3
1 10
11 20
21 30
5
15
25

SAMPLE OUTPUT
5
15
25

Explanation

The mountains will look like the image above. So the heights will be $[1, 2, 3, 4, ....., 8, 9, 10, 11, 12, 13, ...., 19, 20, 21, 22, ......, 29, 30]$.

$5^{th}$ smallest height will be 5.
$15^{th}$ smallest height will be $15$.
$25^{th}$ smallest height will be $25$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Searching)

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Algorithms > Searching
• Algorithms > Searching
• Algorithms > Searching