화학 성분 조합

Силко와 그의 수석 과학자 Сингед는 연구실에서 위험한 약물을 계속 만들고 있다.

지금 만들고 있는 물질의 이름은 "Мерцание"다. 이 물질은 효과 $e$를 가지며, 단순한 화학 성분으로 구성된다. 같은 성분이 여러 번 들어갈 수 있다. 각 화학 성분에도 효과가 정해져 있다.

과학자들은 최종 조성을 아직 정하지 않았다. 하지만 약의 강도가 다음과 같이 정해진다는 것은 알고 있다. $i \neq j$인 성분 쌍 $(i, j)$ 중에서, 두 성분 효과의 합 $a_i + a_j$가 $e$의 배수가 되는 쌍의 개수가 약의 강도이다.

처음에는 조성에 성분이 없다. 다음 두 종류의 질의를 $n$개 처리하라.

1. 효과가 $a_i$인 화학 성분을 조성에 추가한다.
2. 효과가 $a_i$인 화학 성분을 조성에서 제거한다. 그 효과를 가진 성분이 여러 개 있으면 하나만 제거한다.

각 질의를 처리한 후, 현재 조성의 약의 강도를 출력하라.

첫 줄에 공백으로 구분된 두 정수 $n$과 $m$이 주어진다. $n$은 질의의 수이고, $m$은 약의 목표 효과이다. 문제 본문의 $e$에 해당한다 ($1 \le n \le 10^5$; $2 \le m \le 10^9$).

다음 $n$개 줄에는 각각 두 정수 $t_i$와 $a_i$가 주어진다. $t_i$는 질의의 종류이며 ($t_i \in \{1, 2\}$, 1이면 추가, 2이면 제거), $a_i$는 성분의 효과이다 ($-10^9 \le a_i \le 10^9$).

$n$개 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 질의를 적용한 후의 약의 강도를 출력한다.