대형 선형 충돌기

과학자들은 국제 연구소에서 실험 설비인 "대형 선형 충돌기"(БЛК)에서 소립자의 거동을 연구한다. БЛК는 직선이며, 그 위의 여러 지점에 입자가 놓여 직선을 따라 움직일 수 있다.

다음 실험에서 БЛК에는 n개의 입자가 놓인다. 각 입자는 음전하를 띤 전자 е–이거나 양전하를 띤 양전자 е+이다. 실험에서 i번째 입자는 처음에 좌표 xi인 지점에 놓인다. 실험이 시작되면 БЛК가 작동하여 입자들이 직선을 따라 서로 반대 방향으로 움직인다. е– 입자는 좌표가 감소하는 방향으로, е+ 입자는 좌표가 증가하는 방향으로 움직인다. 모든 입자의 속도 크기는 1로 같다.

움직이는 도중 е– 입자와 е+ 입자가 같은 지점에 오면 두 입자는 상호작용하여 모두 사라지며, 다른 입자의 이후 거동에는 영향을 주지 않는다.

과학자들은 m개의 서로 다른 시각 t1, t2, …, tm을 선택했고, 각 시각에 대해 그 시각 바로 직후에 БЛК에 있는 입자의 개수를 알고 싶어 한다. 시간은 입자가 움직이기 시작하는 순간 0부터 측정한다. 시각 tj에 상호작용으로 사라진 입자는 그 시각의 입자 개수를 셀 때 포함하지 않는다.

초기 배치와 입자 종류, 주어진 시각에 대한 정보를 입력으로 받아, 각 시각에 대해 그 시각 바로 직후에 БЛК에 있는 입자의 개수를 구하는 프로그램을 작성해야 한다.

입력 파일의 첫째 줄에는 입자의 개수 n이 주어진다 (1 ≤ n ≤ 200 000). 다음 n개의 줄은 입자를 설명한다. 각 줄에는 두 정수 xi와 vi가 주어진다. xi는 i번째 입자의 좌표이고 vi는 그 종류이다 (–109 ≤ x1 < x2 < … < xn ≤ 109, vi는 –1 또는 1). 입자 е–는 vi = –1로, 입자 е+는 vi = 1로 주어진다.

그다음 줄에는 과학자들이 선택한 시각의 개수 m이 주어진다 (1 ≤ m ≤ 200 000). 마지막 줄에는 m개의 정수 t1, t2, …, tm이 주어진다 (0 ≤ t1 < t2 < … < tm ≤ 109).

각 시각에 대해 그 시각 바로 직후에 БЛК에 있는 입자의 개수를 한 줄에 하나씩 출력한다.

주어진 예에서 처음에 БЛК에는 4개의 입자가 있다. 좌표 –1의 입자 е+, 좌표 0의 입자 е–, 좌표 1의 입자 е+, 좌표 5의 입자 е–이다.

시각 0.5에 첫 번째 입자 е+와 첫 번째 입자 е–가 좌표 –0.5인 지점에서 충돌하여 사라진다. 시각 1에 남은 두 입자는 각각 좌표 2와 4인 지점에 있다. 시각 2에 두 입자는 좌표 3인 지점에서 충돌하여 사라진다. БЛК에는 더 이상 입자가 없다.