행성 방어
시간 제한2초메모리 제한256 MB
각 소행성의 초기 위치와 일정한 속도가 주어질 때, 각 정수 시각마다 원점에서 거리가 R 미만인 소행성의 수를 구한다.
문제
최근 우랄 지역에 운석이 떨어진 뒤, 여러 나라 정부는 지구를 소행성으로부터 보호할 방법을 고민하게 되었다. 이를 위해 국제 반운석 기구(МАМА)가 만들어졌고, 천체물리학 분야의 최고 과학자들이 초빙되었다.
몇 주 동안 연구한 끝에 과학자들은 지구 근처에 n개의 소행성이 돌고 있으며, 소행성이 지구로부터 거리가 R보다 엄격히 크면 지구에 위협이 되지 않는다는 사실을 알아냈다. 단순화를 위해 과학자들은 지구 근처의 모든 소행성이 직선으로 움직인다고 가정하고, 0 시각에서의 위치와 속도 벡터를 구했다. 이제 과학자들은 특정 시각에 몇 개의 소행성이 지구에 위협이 되는지 묻는 질의에 답하려 한다.
편의를 위해 직교 좌표계를 도입하자. 지구의 좌표는 (0, 0, 0)이다. 모든 소행성과 지구는 공간에서 질점으로 간주한다.
여러 시각에 대한 질의가 주어진다. 각 시각마다 그 시각에 지구에 위협이 되는 소행성의 수를 구해야 한다.
입력
첫째 줄에 두 정수 n과 R (1 ≤ n ≤ 100000, 1 ≤ R ≤ 10^6)이 주어진다. 이는 소행성의 수와 위험 구역의 반지름이다.
다음 n개 줄에는 각각 여섯 정수 xi, yi, zi, vxi, vyi, vzi (−10^6 ≤ xi, yi, zi ≤ 10^6, −100 ≤ vxi, vyi, vzi ≤ 100)가 주어진다. 이는 i번째 소행성의 초기 위치와 속도 벡터이다. 속도 벡터는 0이 아님을 보장한다.
다음 줄에는 하나의 정수 m (1 ≤ m ≤ 100000)이 주어진다. 이는 과학자들이 관심을 가지는 시각의 수이다.
다음 m개 줄에는 각각 하나의 정수 ti (0 ≤ ti ≤ 10^7)가 주어진다. 이는 과학자들이 관심을 가지는 시각이다.
출력
각 시각마다 위험 구역 안에 있는 소행성의 수를 하나의 정수로 출력한다.