BGSHOOT - Shoot and kill

no tags 

The problem is about Mr.BG who is a great hunter. Today he has gone to a dense forest for hunting and killing animals.

Sadly, he has only one bullet in his gun. He wants to kill as many animals as possible with only one bullet.

He has already known the information of duration availability of all animals of the forest.

So, he is planning to shoot at a time so that he could kill maximum animal. 

Input

Input begins with an integer N denoting total numbers of animals.

Next N lines contains the duration of availability of animal denoting by X (Starting time) and Y (Ending time) .

Then, there will be Q, denoting the total numbers of queries to be answer.

Each query giving two integer L and R, L denoting the time hunter will come to forest and begins shooting

and R denoting last time upto which he will stay at forest for hunting.

Output

For each query output an integer denoting maximum numbers of animals he could kill by shooting at a time during L and R (inclusive).

Constraints:

1<=N,Q<=100000

1<=X,Y,L,R<=1000000000

Example

Input:
4
1 2
2 3
4 5
6 7
4
1 5
2 3
4 7
5 7

Output:
2
2
1
1

hide comments
akt_1998: 2017-07-13 15:54:25

cakewalk ;)

sharif ullah: 2017-06-02 17:26:17

if u are beginner then need solution??? ha ha!!!!!!!!!! so,first search co-ordinate compression in google and then take pen and paper then choose DS then solve it

mycode_123: 2017-04-09 11:34:12

Nice problem....learnt new thing!:) lazy+seg tree+compression

realflash: 2016-07-25 15:01:26

segment tree, lazy propagation,path compression :)

Last edit: 2016-07-25 15:07:22
SUBHAM SANGHAI: 2016-06-03 20:24:30

Awesome Problem.. BIT+segment tree+path compression.. Everything in one qstn..

suggu: 2016-05-31 08:52:37

1st query - the maximum no. of animal will be killed at time =2 output = 2(1 2 and 2 3)
3rd query - the maximum no. of animal will be killed at time =4 output =1(4 7 or 6 7)

Last edit: 2016-05-31 09:16:10
BISHAL GAUTAM: 2016-05-15 13:15:12

If you had read carefully there is a line "by shooting at a time"....So, question is asking maximum number of segment that could be hit by any one of point from L to R. Hope it helps.

akshayvenkat: 2016-05-13 19:50:28

is the output correct?

shouldn't it be 3 1 2 1?

it_is_me: 2016-05-12 12:17:36

somebody elaborate output please


Added by:BISHAL GAUTAM
Date:2016-05-07
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY