인터넷 채팅

인터넷에서 친구들과 채팅을 즐기다 보면, 여러 채팅 그룹에 쏟아지는 수많은 메시지에 압도되어 짜증이 날 때가 있다. 이런 메시지 대부분은 우리에게 흥미롭지 않지만, 그룹을 조용히 해 두면 중요한 공지를 놓칠 수도 있다. 우리는 모든 온라인 채팅 그룹에서 메시지를 얼마나 많이 받을까? 아무도 이 질문을 진지하게 파고든 적이 없다.

정보학부의 조교 연구원으로서, 당신은 우리가 매일 받는 온라인 메시지의 수를 조사해야 한다. 우리는 이미 $n$개의 그룹과 $m$명의 학생을 표본으로 추출했다. 모든 그룹은 $m$명의 학생 중 일부로 이루어진 부분집합을 포함하며, 이는 비어 있을 수도 있다. 또한 그룹의 구성원은 끊임없이 변한다. 기존 구성원이 나가고, 새 구성원이 채팅 그룹에 들어올 수 있다. 구성원은 그룹에서 메시지를 보낼 수 있으며, 메시지는 현재 같은 그룹에 있는 다른 모든 구성원에게 전송된다.

이제 우리는 이 채팅 그룹들의 로그를 수집했다. 로그는 이벤트의 나열이며, 이벤트는 학생이 그룹에 들어오거나, 그룹에서 나가거나, 그룹에서 메시지를 보내는 것 중 하나일 수 있다. 당신의 임무는 모든 학생이 받은 메시지의 총 개수를 계산하는 것이다.

입력의 첫째 줄에는 세 정수 $n, m, s$ $(1 \leq n \leq 100\,000, 1 \leq m \leq 200\,000, 1 \leq s \leq 1\,000\,000)$가 주어지며, 이는 그룹의 수, 학생의 수, 로그에 있는 이벤트의 수를 나타낸다.

다음 $s$개 줄에는 로그의 이벤트가 시간 순서대로 주어진다. 각 줄은 세 정수 $t, x, y$ $(t \in \{1, 2, 3\}, 1 \leq x \leq m, 1 \leq y \leq n)$를 포함하며, 이는 다음과 같은 세 가지 범주 중 하나에 해당하는 이벤트를 나타낸다.

• $t = 1$이면 $x$번째 학생이 $y$번째 그룹에 들어왔다는 뜻이다. 그 학생이 이전에 그룹에 없었음이 보장된다.
• $t = 2$이면 $x$번째 학생이 $y$번째 그룹에서 나갔다는 뜻이다. 그 학생이 현재 그룹에 있었음이 보장된다.
• $t = 3$이면 $x$번째 학생이 $y$번째 그룹에서 메시지를 보냈다는 뜻이다. 그 학생이 지금 그룹에 있음이 보장된다.

처음에 모든 그룹은 비어 있었다.

$m$개 줄을 출력한다. $i$번째 줄에는 $i$번째 학생이 받은 메시지의 총 개수를 나타내는 정수를 출력한다.