All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK113/hindi/DCRTIT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK113/mandarin/DCRTIT.pdf), [Russian](http://www.codechef.com/download/translated/COOK113/russian/DCRTIT.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK113/vietnamese/DCRTIT.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK113/bengali/DCRTIT.pdf) as well. Since it's almost Christmas, Dr.D wants to get in "That Christmas Feeling". As the first step, he's going to decorate his home. Since he's out of Christmas decorations, he must go buy some at the mall. There are exactly $K$ types of Christmas decorations and Dr.D wants to buy exactly one decoration of each type. The mall can be viewed as a sequence of $N$ shops (numbered $1$ through $N$) in a straight line. For each valid $i$, the $i$-th shop is located at the point $P_i$, it sells only decorations of the type $D_i$ and it is only open in the time interval $[L_i, R_i]$. Dr.D wants to choose a point inside the mall, park his car there and start shopping for $K$ decorations. Since decorations are rather heavy, whenever Dr.D buys a decoration, he must load it into the car before buying another one. Shopping and moving around the mall (with or without decorations) does not take any time, but bringing heavy decorations back to the car still takes a lot of effort, so Dr.D would like to minimise the total distance he needs to walk with decorations. You should answer $Q$ queries. In each query, you are given two integers $X$ and $T$ - Dr.D parks at the point $X$ in the mall at time $T$, and you should find the minimum distance Dr.D needs to walk with decorations. However, if it is impossible to buy one decoration of each type or if Dr.D would have to wait for some shops to open in order to do that, he will go back home and destroy Christmas. We know that Dr.D is extremely smart, so he will choose the shops to buy decorations from optimally. ### Input - The first line of the input contains three space-separated integers $N$, $Q$ and $K$. - $N$ lines follow. For each valid $i$ ($1 \le i \le N$), the $i$-th of these lines contains four space-separated integers $P_i$, $D_i$, $L_i$ and $R_i$. - Each of the next $Q$ lines contains two space-separated integers $X$ and $T$ describing a query. ### Output For each query, print a single line containing one integer - the minimum distance Dr.D needs to walk with decorations, or $-1$ if Dr.D destroys Christmas. ### Constraints - $1 \le N, Q \le 3 \cdot 10^5$ - $1 \le K \le N$ - $1 \le D_i \le K$ for each valid $i$ - $1 \le P_i \le 10^9$ for each valid $i$ - $1 \le L_i \le R_i \le 10^9$ for each valid $i$ - $1 \le X, T \le 10^9$ ### Example Input ``` 3 5 2 4 1 3 8 7 2 1 13 9 1 5 7 8 5 8 8 5 7 3 2 2 6 ``` ### Example Output ``` 2 5 3 -1 7 ```
|Tags||cook113, data-structure, kmaaszraa, kmaaszraa, medium-hard|
|Time Limit:||4 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.