ChannelTalk

채널코퍼레이션의 커뮤니케이션 플랫폼 채널톡은 고객과의 실시간 소통을 통해 기업의 지속 가능한 성장을 돕는 올인원 AI 메신저이다. CRM 데이터와 AI를 활용해 상담 효율을 높이고 고객 경험을 개선하며, '고객이 답이다'라는 철학 아래 고객 중심의 서비스를 제공한다. 일본에서 업계 1위 수준의 점유율과 빠른 매출 성장을 이루며 아시아 시장을 넘어 미국 진출도 추진 중이다. 이러한 성과의 핵심은 '제품'에 있으며, 전체 직원 절반 이상이 개발자로 구성되어 하나의 우수한 제품 개발에 집중하고 있다.

채널코퍼레이션은 고객 의견을 수렴하기 위해 채널톡에서 여러 개의 토론 채널을 시범 운영하기로 하였다.

채널은 총 $N$개로, $1$번부터 $N$번까지의 번호가 붙어 있다. 모든 채널은 같은 의견 주제를 다루며, $i$번 채널에는 처음에 해당 의견에 찬성하는 사람 $A\_i$명과 반대하는 사람 $B\_i$명이 있다. 또한 $i$번 채널의 최대 수용 인원은 $C\_i$명이며, $C\_i$는 짝수이다. (예외적으로 마지막 $N$번 채널은 수용 인원 제한이 없다.)

시스템 동작 중 가끔 새로운 참여자가 특정 채널에 들어온다. 이 참가자 역시 찬성 또는 반대 중 하나의 의견을 가지고 있다. 새로운 참가자가 들어올 때, 채널톡의 관리 규칙에 따라 다음과 같은 일이 일어난다.

• 새로운 참가자가 들어왔을 때 해당 채널의 인원수가 수용 한도를 넘지 않으면 그대로 채널에 머무른다.
• 해당 채널의 인원수가 정원을 초과했다면, 그 순간 해당 채널의 총 인원은 홀수가 된다. 이 경우 찬성 측과 반대 측 인원수 중 더 많은 쪽에서 한 명의 참가자가 자동으로 다음 번호의 채널로 이동된다. (이동된 사람의 의견 성향은 변하지 않는다.)
• 만약 이 과정으로 인해 다음 채널의 인원수가 수용 한도를 넘는다면 같은 과정이 반복된다. 이 과정은 모든 채널의 인원수가 수용 한도 이하가 될 때까지 반복된다. 특히, 마지막 $N$번 채널은 수용 인원 제한이 없기 때문에 이 과정은 언젠가는 끝나게 된다.

당신은 시범 운영을 돕기 위해, 새로운 참가자들이 토론 채널에 들어올 때 각 채널의 인원수를 빠르게 관리하는 프로그램을 작성해야 한다. 구체적으로, 다음과 같은 쿼리가 주어질 때, 해당 쿼리를 빠르게 처리해야 한다.

• 1 x v: $x$번 채널에 찬성 의견을 가진 사람 $v$명이 들어온다.
• 2 x v: $x$번 채널에 반대 의견을 가진 사람 $v$명이 들어온다.
• 3 x: $x$번 채널에 있는 사람 중 찬성 의견과 반대 의견을 가진 사람의 수를 각각 출력한다.

단, 1번과 2번 종류의 쿼리에서, $v$명의 사람들은 채널에 한 사람씩 차례로 들어가고, 이전 사람으로 인해 생긴 모든 이동 과정이 끝난 뒤 다음 사람이 들어온다고 생각한다.

첫 줄에는 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. ($2\le N\le 200\\, 000$; $1\le Q\le 200\\, 000$)

이후 $N-1$개의 줄에 걸쳐, 그중 $i$번째 줄에는 세 정수 $A\_i$, $B\_i$, $C\_i$가 공백으로 구분되어 주어진다. ($0\le A\_i,B\_i\le 10^9$; $2\le C\_i\le 10^9$; $A\_i+B\_i\le C\_i$; $C\_i$는 짝수)

$N+1$번째 줄에는 두 정수 $A\_N$, $B\_N$이 공백으로 구분되어 주어진다. ($0\le A\_N,B\_N\le 10^9$)

이후 $Q$개의 줄에 걸쳐, 그중 $i$번째 줄에는 $i$번 쿼리의 정보가 지문에서 안내된 형태로 주어진다. 모든 쿼리에 대해 $1\le x\le N$, $1\le v\le 10^9$이다.

3번 종류의 쿼리가 적어도 하나 주어짐이 보장된다.

모든 $3$번 형태의 쿼리에 대해, 해당 채널에 있는 사람 중 찬성과 반대 의견을 가진 사람의 수를 출력한다.