12895번 - 화려한 마을

민호가 관리하는 천나라에는 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번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다.