Hard Data Structures > Segment Tree/Interval Tree

**Sanvi** is a very cute girl. She likes chocolates so much. There are **N** chocolate boxes numbered from **1** to **N**, arranged linearly from left to right. Sanvi has a list of favorite chocolate boxes. She always takes chocolate only from these boxes. Sanvi has **M** friends numbered from **2** to **M+1**. Her id number is **1**. Like Sanvi, her friends also has list of favorite chocolate boxes. All the chocolate boxes are initially empty. Sanvi recently builds a robot which can add chocolate to these boxes. The robot operates total **D** days. Every day, the robot starts from some box numbered **L** and goes upto box **R** and add **C** chocolates to every boxes from left (L) to right(R) inclusive. Your task is to process **Q** wishes of Sanvi and her friends. Every wish start with id of friend -**X** and total number of chocolates he/she wants to collect-**Y**. You have to find the total number of days required to fulfill his/her wish. He/She always collects chocolates from his/her favorite chocolate boxes. **Note:** total ***distinct*** Yi for each Xi will be at most **15** ![enter image description here][1] ![enter image description here][2] Input: ------ Input starts with four integers **N,M,D,Q** denoting respectively total boxes, number of Sanvi's friends, total operation days of robot and total wishlist. For each person with id from **1** to **M+1**, there will be one line of input that starts with ***Ti*** denoting total number of favorite boxes of ith person. Then space separated ***Ti*** integers denoting favorite box id of ith person. Then there will be **D** more lines with space separated three integers ***Li, Ri , Ci*** as explained above. Then there will be **Q** more lines with space separated two integers ***Xi, Yi*** as explained above. ---------- Constraints: --------------- **1<=N,M,D<=50000** **1<=Q<=100000** **1<=X<=M+1, 1<=L<=R<=N** **1<=C,Y<=1000000000** - total summation of favorite chocolate count will be at most **200000**. - In **Q** wishlists, **total distinct Yi** for each **Xi** will be at most **15**. ---------- Output: ------- For every **Q** wishes output a line of output denoting total number of days required to fulfill that wish.if it is not possible to fulfill wish, output **-1** instead. Sample Input ------------ 3 3 3 4 2 2 3 2 1 3 1 2 1 1 1 1 3 3 3 6 1 2 2 4 1 4 4 1 2 3 4 Sample Output ------------- 1 3 2 -1 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/99a3e085-c018-ce96-6c49-08d488b654f1_580097342030471b884ace3e66f6d3e0_W280xH200.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/3fd51c42-2f92-c863-0dec-08d488b698dd_399edca124db4d71b79dfe6ca0cd2f49_W262xH204.png

Bishal Gautam