문제
옛날에 일어났던 중일전쟁에서 중국 북부 평야에서는 터널을 이용한 전술을 사용했다. 터널은 직선의 형태이다. 터널의 양쪽 끝을 제외하면, 각 도시들은 터널에 의해 인접한 두 도시와 연결되어 있다.
가끔은 터널들이 공격에 의해 파괴되기도 한다. 한편, 군사본부에서는 특정 도시를 선택해서 그 도시에서 좌우로 이동할 때 도달 가능한 범위를 조사한다. 또, 공병부대에서 파괴된 터널을 복구하기도 한다.
N개의 도시에 대해서 M번의 무전이 올 때 군사본부에서 온 무전에 대한 답을 구하는 프로그램을 작성하여라.
입력
입력은 두 정수 N과 M (1 ≤ N, M ≤ 50,000)으로 시작한다. N은 도시의 수를 의미하며 M은 무전의 수를 의미한다. 다음 M줄에 걸쳐서 무전에 대한 정보가 입력된다.
무전은 세 가지 종류 중 하나로 입력된다:
1. D x: x번째 마을 부분이 파괴되었음. 2. Q x: 군사본부에서 x번째 마을에서 도달 가능한 마을의 수를 요청하였음. (1 ≤ x ≤ N) 3. R: 가장 최근에 파괴된 마을 부분의 터널을 복구하였음.
출력
입력된 이벤트들을 처리하여 한 줄에 하나씩 Q 이벤트의 답을 출력한다.
단, Q x에서 x가 이미 파괴된 경우 0을 출력한다.
예제
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
1
0
2
4
힌트
로그인해야 코드를 작성할 수 있어요.