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 typec
after the current sequence of operations (that is used to generate the sequence ).c
will be either characterW
orE
.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 allW
toE
and switching allE
toW
.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
andcode2.ans
) corresponds to cases 1-4. - Sample 3 (
code3.in
andcode3.ans
) corresponds to cases 5-7. - Sample 4 (
code4.in
andcode4.ans
) corresponds to cases 8-10. - Sample 5 (
code5.in
andcode5.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