Chef Does Coke Yet Again

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME75/hindi/COKE2.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME75/bengali/COKE2.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME75/mandarin/COKE2.pdf), [Russian](http://www.codechef.com/download/translated/LTIME75/russian/COKE2.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME75/vietnamese/COKE2.pdf) as well. Chef went to the store in order to buy one can of coke. In the store, they offer $N$ cans of coke (numbered $1$ through $N$). For each valid $i$, the current temperature of the $i$th can is $C_i$ and its price is $P_i$. After buying a can of coke, Chef wants to immediately start walking home; when he arrives, he wants to immediately drink the whole can. It takes Chef $M$ minutes to get home from the store. However, Chef does not know the value of $M$ yet. The ambient temperature outside is $K$. When a can of coke is outside, its temperature approaches the ambient temperature. Specifically, if its temperature is $t$ at some point in time:  if $t \gt K+1$, then one minute later, its temperature will be $t1$  if $t \lt K1$, then one minute later, its temperature will be $t+1$  if $K1 \le t \le K+1$, then one minute later, its temperature will be $K$ When Chef drinks coke from a can, he wants its temperature to be between $L$ and $R$ (inclusive). For each $i$ between $1$ and $Q$ inclusive, find the cheapest can for which this condition is satisfied when $M = i$ or determine that there is no such can. ### 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 each test case contains five spaceseparated integers $N$, $Q$, $K$, $L$ and $R$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $C_i$ and $P_i$. ### Output For each test case, print a single line containing $Q$ spaceseperated integers. For each valid $i$, the $i$th of these integers should be the answer for $M = i$: the price of the can Chef should buy, or $1$ if it is impossible to buy a can such that Chef's condition is satisfied. ### Constraints  $1 \le T \le 1,000$  $1 \le N, Q \le 10^5$  $C_i \le 10^5$ for each valid $i$  $K \le 10^5$  $10^5 \le L \le R \le 10^5$  $1 \le P_i \le 10^9$ for each valid $i$  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $Q$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (30 points):**  $N, Q \le 1,000$  $C_i \le 10^3$ for each valid $i$  $K \le 10^3$  $10^3 \le L \le R \le 10^3$  the sum of $N$ over all test cases does not exceed $10,000$  the sum of $Q$ over all test cases does not exceed $10,000$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 2 3 2 5 4 6 1 6 2 8 8 10 3 5 10 20 30 21 20 22 22 23 23 ``` ### Example Output ``` 1 8 20 22 23 1 1 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/COKE2 
Tags  basicmath, easy, kingofnumbers, lazypropagation, ltime75, segmenttree, taran_1407 
Date Added:  30082019 
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, R, 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. 