The password of a lockbox is determined by a sequence . The sequence may be constructed as follows:

- Initially, the length of the sequence is 2 and , .
- Perform some operations on the sequence. Each operation must be one of the following two types:
- Type
`W`

- add 1 to the*last term*of the sequence. - Type
`E`

- if the*last term*of the sequence is 1, then add 1 to the second-to-last term. Otherwise, subtract 1 from the last term of the sequence, and append two terms to the end of the sequence. The values of the two new terms are both 1.

- Type

The lockbox cannot check the entire sequence, so the password is set to be the value of after transformation by function . The function is defined as follows:

You need to compute the password based on the sequence of operations. However, the sequence of operations may be updated. The updates are one of the following three types:

`APPEND c`

: Append an operation of type`c`

after the current sequence of operations (that is used to generate the sequence ).`c`

will be either character`W`

or`E`

.`FLIP l r`

: Flip the operations between the -th operation and the -th operation in the current sequence of operations (the indices begin with 1, and the update will include the endpoints and ). Here, flipping means switching all`W`

to`E`

and switching all`E`

to`W`

.`REVERSE l r`

: Reverse the operations between the -th operation and the -th operation, which means reverse the order of operations in this interval.

#### Input Specification

The first line of the input contains two integers , denoting the length of the initial sequence of operations and the number of updates.

The second line contains a string of length consisting of upper-case
letters `E`

and `W`

, denoting the initial sequence of operations.

For the following lines, each line specifies an operation. The format is defined in the problem description.

#### Output Specification

The output consists of lines. Each line contains two integers. The first line denotes the password corresponding to the initial sequence of operations, and the following lines denote the passwords after each update.

It is easy to see the password must be a positive rational number. If the password is where and , then you need output and modulo in the corresponding line.

#### Sample Input 1

```
2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3
```

#### Sample Output 1

```
2 3
3 4
5 3
5 2
```

#### Explanation for Sample Output 1

Operations | Password | ||
---|---|---|---|

Initial | `WE` |
||

After 1st update | `WEE` |
||

After 2nd update | `EWE` |
||

After 3rd update | `EEW` |

#### Additional Samples

The samples can be found here.

- Sample 2 (
`code2.in`

and`code2.ans`

) corresponds to cases 1-4. - Sample 3 (
`code3.in`

and`code3.ans`

) corresponds to cases 5-7. - Sample 4 (
`code4.in`

and`code4.ans`

) corresponds to cases 8-10. - Sample 5 (
`code5.in`

and`code5.ans`

) corresponds to cases 15-20.

#### Constraints

For all test cases, , .

For updates `APPEND`

, it is guaranteed that the given `c`

will be
upper-case letter `W`

or `E`

.

For updates `FLIP`

and `REVERSE`

, it is guaranteed that
where is the length of the current
sequence.

Please notice because there are updates of type `APPEND`

, the maximum
length of the sequence of operations might be as large as
.

Test Case | Additional Constraints | |
---|---|---|

1~4 | None. | |

5~7 | A | |

8~10 | B, C | |

11~14 | C | |

15~20 | None. |

Constraint A: it is guaranteed that at any point there won't be two consecutive
identical characters in the sequence of operations.

Constraint B: there are no `FLIP`

updates.

Constraint C: there are no `REVERSE`

updates.

## Comments