Vuong은 역사상 가장 위대한 수학자 중 한 명이다! 그의 취미는 모든 것의 수학적 성질을 찾아내는 것이며, 때로는 존재하지 않는 것에서도 찾는다! 생일날 그의 프로그래머 친구가 길이가 $n$인 이진 문자열 $S$를 선물했다. 얼마 후 그는 $S$의 두 가지 매우 흥미로운 성질을 발견했다.

• $X(S)$: $S$의 부분 수열이 아닌 가장 짧은 문자열의 길이.

• $Y(S)$: 길이가 $X(S)$이고 $S$의 부분 수열이 아닌 문자열의 수.

Vuong이 두 성질을 찾으며 즐거워하는 것을 보고, 프로그래머 친구는 문자열 $S$도 조금 바꾸면 좋겠다고 생각했다. 프로그래머는 $S$에 $q$번의 수정을 순서대로 한다. 각 수정은 다음 유형 중 하나이다.

• 0 l r: $S_l,S_{l+1},\ldots,S_r$을 $0$으로 설정한다.

• 1 l r: $S_l,S_{l+1},\ldots,S_r$을 $1$로 설정한다.

• F l r: $S_l,S_{l+1},\ldots,S_r$을 뒤집는다. 즉, $l\le i\le r$에 대해 $S_i$가 $0$이면 $1$로, 아니면 $0$으로 설정한다.

물론 Vuong은 수정된 $S$의 각 버전에서도 기꺼이 $X(S)$와 $Y(S)$를 찾았다. 그의 생일이었으니까!

하지만 답이 없는 퍼즐은 완성된 것이 아니다. 문자열 $S$와 $q$번의 수정 목록이 주어졌을 때, 매 수정 후 $X(S)$와 $Y(S)$를 구해 프로그래머 친구가 정답으로 Vuong의 결과를 확인하도록 도와라.

답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력하라.

문자열 $b$에서 여러 문자(0개 또는 전부도 가능)를 삭제하여 문자열 $a$를 얻을 수 있으면 $a$는 $b$의 부분 수열이다. 예를 들어 bd, acd, b는 abcd의 부분 수열이지만 da는 아니다.

입력

첫 줄에는 문자열 $S$의 길이와 수정 횟수를 나타내는 두 정수 $n,q$ ($1\le n,q\le100\,000$)가 주어진다.

둘째 줄에는 길이가 $n$인 이진 문자열 $S$가 주어진다.

다음 $q$줄 중 $i$번째 줄에는 다음 형식 중 하나로 $i$번째 연산이 주어진다.

• 0 l r ($1\le l\le r\le n$): $S_l,S_{l+1},\ldots,S_r$을 $0$으로 설정한다.

• 1 l r ($1\le l\le r\le n$): $S_l,S_{l+1},\ldots,S_r$을 $1$로 설정한다.

• F l r ($1\le l\le r\le n$): $S_l,S_{l+1},\ldots,S_r$을 뒤집는다.

출력

$S$의 각 수정마다 $X(S)$와 $Y(S)$를 $10^9+7$로 나눈 나머지인 두 정수를 한 줄에 출력하라.

예제

입력 1

4 3
0110
0 2 3
1 3 4
F 2 3

출력 1

1 1
2 1
3 4

참고

예제에서 문자열 $S$는 0110이고 $S$에 $q=3$번의 수정이 있다.

다음 표는 $S$의 수정을 보여 준다.

• $S=$ 0000이면 $X(S)=1$, $Y(S)=1$이다. 길이가 $1$이고 $S$의 부분 수열이 아닌 문자열은 1 하나이기 때문이다.

• $S=$ 0011이면 문자열 10이 가장 짧고, 길이가 $2$이며 $S$의 부분 수열이 아닌 유일한 문자열이다.

• $S=$ 0101이면 $S$의 부분 수열이 아닌 가장 짧은 문자열 목록은 {000, 100, 110, 111}이다.

• 초기 문자열 $S=$ 0110에서 $S$의 부분 수열이 아닌 가장 짧은 문자열 목록은 {000, 001, 100, 101, 111}이다. 따라서 $X(S)=3$, $Y(S)=5$이지만 이 수들은 출력할 필요가 없다.