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$。

當然，對於 $S$ 的每個修改後的版本，Vuong 也樂於尋找 $X(S)$ 和 $Y(S)$，因為這是他的生日！

不過，謎題沒有答案就不完整。給定字串 $S$ 和對 $S$ 的 $q$ 次修改列表，請幫助工程師朋友求出每次修改後的 $X(S)$ 和 $Y(S)$，以便他用答案檢查 Vuong 的結果。

由於答案可能很大，請輸出答案對 $10^9+7$ 取模的結果。

如果字串 $a$ 可以透過從字串 $b$ 中刪除若干個字元（可以不刪，也可以全部刪除）得到，就稱 $a$ 是 $b$ 的子序列。例如，bd、acd、b 都是 abcd 的子序列，而 da 不是。

輸入格式

第一行包含兩個整數 $n,q$ ($1\le n,q\le100\,000$)，表示字串 $S$ 的長度和修改次數。

第二行包含長度為 $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$，但不需要輸出這兩個數。