시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB108443743.529%

문제

날다람쥐 한 마리가 자유 낙하를 하려고 한다.

$N$개의 휴식점이 주어지고, 각각의 휴식점의 좌표 $X_i, Y_i$가 주어진다. 가장 많은 수의 휴식점을 지나가는 것이 날다람쥐의 목표이다.

안아줘요 날다람쥐는 언제나 안아줘요 포즈를 취하고 있기 때문에 공기 저항을 크게 받아 좌우 방향의 이동보다 빠르게 낙하할 수는 없다.

즉, $|Y_i - Y_j| ≤ |X_i - X_j|$이고 $Y_i > Y_j$인 경우에만 $i$번 휴식점에서 $j$번 휴식점으로 이동할 수 있다.

여러 낙하 경로 중에, 가장 많은 휴식점을 지날 수 있는 경로를 선택하여 낙하하려고 한다.

$Q$개의 출발 휴식점 번호가 주어질 때, 해당 휴식점에서 출발해서 지날 수 있는 휴식점의 수를 날다람쥐에게 알려주자.

입력

입력은 아래와 같이 주어진다.

$N$ $Q$

$X_1$ $Y_1$

...

$X_N$ $Y_N$

$q_1$

...

$q_Q$

출력

출발 휴식점에서 경유할 수 있는 최대 휴식점의 개수를 한 줄에 하나씩 출력한다. 출발 휴식점과 도착 휴식점도 출력하는 숫자에 포함한다.

제한

  • $1 \leq N,Q \leq 500\,000$
  • $0 ≤ X_i, Y_i ≤ 10^9$
  • $i \neq j $ $\Rightarrow$ $Y_i \neq Y_j$
  • $1 \leq q_i \leq N$

예제 입력 1

5 3
8 8
6 7
7 6
5 5
4 4
1
2
3

예제 출력 1

5
4
3