시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 83 16 14 28.000%

문제

민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … N번으로 부르기로 했다.

어느 날 미적 감각에 눈을 뜬 민호는 특정 구간의 집들의 색들을 새롭게 칠하거나, 특정 구간의 집들에 존재하는 색의 수를 알고 싶어졌다.

작업은 다음과 같은 두가지로 이루어 진다.

  1. “C x y z” : x번부터 y번 집까지 z번 색으로 색칠한다.
  2. “Q x y” : x번부터 y번 집까지 존재하는 색의 가짓수를 출력한다.

민호가 사용할 색의 종류는 (1번, 2번, … T번) 이라 하고 처음 모든 집은 1번으로 색칠되어 있다고 생각한다.

민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자.

입력

첫 번째 줄에 N, T, Q ( 1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000 )이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다.

두 번째 줄부터 작업이 주어진다. 작업은 “C x y z” 또는 “Q x y” 둘 중에 하나의 형식으로 주어진다.

출력

작업이 “Q x y”일 때의 경우 x번부터 y번 집까지 존재하는 색의 가짓수를 출력한다.

예제 입력 1

2 2 4
C 1 1 2
Q 1 2
C 2 2 2
Q 1 2

예제 출력 1

2
1