The Ancient Password

Yelekastee, the famous archaeologist of country U, has discovered an ancient safe whose password is derived from a sequence \(\{a_n\}\). Initially, the sequence has two elements: \(a_0 = 0\) and \(a_1 = 1\). Then, a series of operations are performed on the sequence. Each operation is one of the following types:

• W: Increase the last element of the sequence by \(1\).
• E: If the last element is equal to \(1\), then increase the second to last element by \(1\). Otherwise, subtract \(1\) from the last element and append two \(1\)s to the sequence.

After all operations have been carried out, the password is computed by applying the function \(f\) on the sequence:

[ f(a_0, a_1, \ldots, a_{k}) = \begin{cases} a_0, & k=0\[6pt] f(a_0, a_1, \ldots, a_{k-2}, a_{k-1} + \frac{1}{a_{k}}), & k \ge 1 \end{cases} ]

This is equivalent to evaluating the following continued fraction exactly:

[ a_0 + \cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\ddots +\cfrac{1}{a_{k}}}}} ]

</p>

However, Yelekastee’s memory is not perfect. He will perform a series of modifications on the operation sequence before the safe checks the whole sequence. The modifications are of the following three types:

• APPEND c: Append an operation c (either W or E) at the end of the current sequence.
• FLIP l r: For operations in the interval from index \(l\) to \(r\) (1-indexed and inclusive), flip every operation (W becomes E and vice versa).
• REVERSE l r: Reverse the order of operations in the interval from index \(l\) to \(r\) (1-indexed and inclusive).

Your task is to process the modifications, simulate the operations on the sequence, and finally compute the safe's password as a reduced fraction in the form p/q (or as an integer if the denominator is \(1\)).

inputFormat

The input contains multiple lines:

1. The first line contains an integer \(N\) (\(N \geq 2\)), the initial number of operations.
2. The second line contains a string of length \(N\) consisting only of characters W and E, representing the initial operation sequence.
3. The third line contains an integer \(Q\), the number of modifications.
4. Each of the next \(Q\) lines describes a modification in one of the following formats:
   • APPEND c where c is either W or E.
   • FLIP l r where \(l\) and \(r\) are integers (1-indexed) with \(1 \le l \le r \le \) (current length of the sequence).
   • REVERSE l r with similar constraints as above.

It is guaranteed that there are at least three test cases in the judging system.

outputFormat

Output a single line containing the password, which is the value of the continued fraction computed from the final sequence of \(a_n\). The answer should be given as a reduced fraction p/q (if \(q \neq 1\)) or as an integer (if \(q = 1\)).

sample

3
WEE
2
APPEND W
FLIP 2 3

1/5