Chef Restaurant

All submissions for this problem are available.
###Read problems statements [Bengali](http://www.codechef.com/download/translated/LTIME64/bengali/CHEFRES.pdf) , [Mandarin chinese](http://www.codechef.com/download/translated/LTIME64/mandarin/CHEFRES.pdf) , [Russian](http://www.codechef.com/download/translated/LTIME64/russian/CHEFRES.pdf) and [Vietnamese](http://www.codechef.com/download/translated/LTIME64/vietnamese/CHEFRES.pdf) as well. Chef is a cook and he has recently opened a restaurant. The restaurant is open during $N$ time intervals $[L_1, R_1), [L_2, R_2), \dots, [L_N, R_N)$. No two of these intervals overlap — formally, for each valid $i$, $j$ such that $i \neq j$, either $R_i \lt L_j$ or $R_j \lt L_i$. $M$ people (numbered $1$ through $M$) are planning to eat at the restaurant; let's denote the time when the $i$th person arrives by $P_i$. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time. For each person, calculate how long they have to wait (possibly $0$ time), or determine that they will wait forever for the restaurant to open. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of the input contains two spaceseparated integers $N$ and $M$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains two spaceseparated integers $L_i$ and $R_i$.  $M$ lines follow. For each valid $i$, the $i$th of these lines contains a single integer $P_i$. ### Output For each test case, print $M$ lines. For each valid $i$, the $i$th of these lines should contain a single integer — the time person $i$ has to wait, or $1$ if person $i$ has to wait forever. ### Constraints  $1 \le T \le 100$  $1 \le N, M \le 10^5$  $1 \le L_i \lt R_i \le 10^9$ for each valid $i$  $1 \le P_i \le 10^9$ for each valid $i$  the intervals are pairwise disjoint  the sum of $N$ for all test cases does not exceed $3 \cdot 10^5$  the sum of $M$ for all test cases does not exceed $3 \cdot 10^5$ ### Subtasks **Subtask #1 (30 points):**  the sum of $N$ for all test cases does not exceed $1,000$  the sum of $M$ for all test cases does not exceed $1,000$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 1 4 5 5 7 9 10 2 3 20 30 5 6 7 35 1 ``` ### Example Output ``` 0 0 2 1 1 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/CHEFRES 
Tags  binarysearch, easy, kingofnumbers, linesweep, ltime64, taran_1407 
Date Added:  29092018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, 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. 