비타로는 큰 원형 호수 주변에 살고 있습니다. 호수의 둘레 길이는 L이고, 호수의 주변에 있는 특정 지점에는 비타로의 집이 있습니다. 비타로의 집에서 호수 주변을 시계방향으로 x (0 ≦ x < L) 만큼 이동한 지점을 지점 x라고 합니다. 현재, 호수 주변에서 마라톤 대회가 예정되어 있습니다.

비타로는 마라톤 대회가 다음과 같이 진행될 것이라고 들었습니다.

0부터 L-1까지 번호가 붙은 번호표가 1장씩 준비되어 있습니다. 마라톤 대회 참가자는 이 번호표 중 하나를 착용합니다. 번호표 l (0 ≦ l ≦ L-1)을 착용한 참가자의 출발 지점은 지점 l이 됩니다. 마라톤 대회가 시작된 후, T초 동안 참가자들은 각자의 속도로 호수 주변을 시계방향으로 이동합니다. 마라톤 대회가 시작된 후, t초 (0 ≦ t ≦ T)가 경과한 시점을 시간 t라고 부릅니다. 비타로는 마라톤 대회 참가자 명단을 가지고 있습니다. 현재 N명의 참가자가 명단에 기록되어 있고, i번째 참가자 (1 ≦ i ≦ N)는 번호표 A_i를 착용하고, 1초에 S_i의 속도로 호수 주변을 시계방향으로 이동할 예정입니다.

참가자 명단을 바탕으로, 비타로는 마라톤 대회 중에 일어나는 충돌 횟수를 구하려고 합니다. 여기서 충돌이란, 서로 다른 2명의 참가자가 같은 지점에 있는 경우를 말합니다. 정확히는, 0 ≦ p < q ≦ L-1을 만족하는 정수 p, q와 0 ≦ t ≦ T을 만족하는 실수 t에서 다음 조건을 만족하는 경우를 충돌로 정의합니다.

번호표 p를 착용한 참가자가 있음.
번호표 q를 착용한 참가자가 있음.
번호표 p를 착용한 참가자와 번호표 q를 착용한 참가자가 시간 t에 같은 지점에 있음.

하지만, 그 후 참가자 명단에 Q번의 변경이 이루어졌습니다. j번째 (1 ≦ j ≦ Q)의 변경은 2개의 정수 X_j, Y_j로 표현되며, 다음과 같은 방식으로 이루어집니다.

현재, 번호표 X_j을 착용하고, 1초에 Y_j의 속도로 호수 주변을 시계방향으로 이동하는 사람이 참가자 명단에 기록되어 있으면, 그 사람을 참가자 명단에서 삭제합니다. 그렇지 않으면, 번호표 X_j을 착용하고, 1초에 Y_j의 속도로 호수 주변을 시계방향으로 이동하는 사람을 새로 참가자 명단에 추가합니다.

단, 변경이 완료된 후에도 참가자 명단에 기록된 참가자는 2명 이상이며, 참가자들이 착용한 번호표는 모두 다를 것이라고 보장됩니다.

비타로는 각각의 변경이 완료된 후, 참가자들에 의해 일어날 충돌의 횟수를 알고 싶습니다. 문제의 제약에 의해, 마라톤 대회 중 발생하는 충돌 횟수는 유한하다는 것이 증명됩니다.

마라톤 대회와 참가자 명단에 대한 변경 정보가 주어졌을 때, 각 변경이 끝난 후 참가자들에 의한 충돌 횟수를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하십시오.

#8232 upload 5 done - how_to_reg - call_split Subtarea

충돌 timer 9s memory 2048MB

#8232
Subtarea

충돌 9s 2048MB