노이족과 ICPC의 대전

문제

노이족은 수학과 컴퓨터에 유별나게 끌리는 유서 깊고 교양 있는 종족이다. 원래는 평화로운 종족이지만, 지금은 숙적인 대륙간 초원 코기(줄여서 ICPC)와 전면전을 벌이고 있다. 전쟁은 몇 년째 이어지고 있고, 어느 쪽도 상대 영토에 발판을 마련하지 못했다.

노이족은 마침내 전쟁을 끝내고 새 정리를 발견하고 수학 문제를 만드는 일상으로 돌아갈 원대한 계획을 세웠다. 무시무시한 지성으로 ICPC를 수학도 컴퓨터도 없는 다른 차원으로 날려 버릴 초병기를 만들어 낸 것이다. (그런 차원이 존재한다는 생각만으로도 노이족은 뼛속까지 오싹해지는데, 그 차원을 발견한 가여운 노이족 한 명은 지금 정신병동에 갇혀 있다. 그건 또 다른 이야기다.) 그런데 ICPC 첩자가 이 계획을 알아냈고, 몰래 숨어든 공작원이 초병기의 설정을 망가뜨렸다.

초병기는 정수 $N$ 개로 이루어진 수열로 설정하며, 노이족은 올바른 설정인지 빠르게 검사하는 방법을 고안했다. 하지만 검사 코드를 짤 수 있는 유일한 노이족이 정신병동에 있어서 도움이 절실하다. 노이족은 당신의 뛰어난 프로그래밍 실력을 전해 듣고 초병기 재설정을 도와 달라고 요청했다.

그들이 보낸 메시지는 이렇다. 위대한 이여, 우리를 도와 달라! 못된 ICPC를 무찌를 프로그램이 필요하다. 올바른 설정을 찾을 때 우리는 설정 수열 $A$ 에 두 연산 중 하나를 수행한다. $A_L, A_{L+1}, \dots, A_{R-1}, A_R$ 을 모두 $V$ 로 바꾸거나, $L \le i < j < k \le R$ 을 만족하는 모든 인덱스 $i$ , $j$ , $k$ 에 대해 $A_i A_j A_k$ 의 합을 구한다.

입력

첫째 줄에 정수 $N$ 과 $Q$ 가 공백 하나를 사이에 두고 주어진다. $N$ 은 설정 수열의 길이이고, $Q$ 는 노이족이 수행할 연산의 개수이다.

다음 $Q$ 개 줄에는 수열에 수행할 연산이 순서대로 주어지며, 형식은 다음 두 가지 중 하나이다.

SET L R V: $A_L, A_{L+1}, \dots, A_{R-1}, A_R$ 을 모두 $V$ 로 바꾼다.
ASK L R: $L \le i < j < k \le R$ 을 만족하는 모든 인덱스 $i$ , $j$ , $k$ 에 대한 $A_i A_j A_k$ 의 합을 $10^8$ 으로 나눈 나머지를 출력한다.

설정 수열의 모든 원소는 처음에 1이다.

제한은 다음과 같다.

$1 \le N \le 10^9$
$1 \le Q \le 10^5$
$1 \le L \le R \le N$
$1 \le V \le 10^6$

출력

두 번째 종류의 연산 개수를 $M$ 이라 할 때 $M$ 개 줄을 출력한다. 각 줄에는 $L \le i < j < k \le R$ 을 만족하는 모든 인덱스 $i$ , $j$ , $k$ 에 대한 $A_i A_j A_k$ 의 합 $S$ 를 $10^8$ 으로 나눈 나머지를 정수 하나로 출력한다. 범위에 속한 인덱스가 세 개보다 적으면 더할 항이 없으므로 답은 0이다.