Decorate It

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 spaceseparated 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 spaceseparated integers $P_i$, $D_i$, $L_i$ and $R_i$.  Each of the next $Q$ lines contains two spaceseparated 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 ```Author:  kmaaszraa 
Editorial  https://discuss.codechef.com/problems/DCRTIT 
Tags  cook113, datastructure, kmaaszraa, kmaaszraa, mediumhard 
Date Added:  20122019 
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 
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. 