Background

Xiao Z has been studying sequences. He wants to know, for the sequence he studies, what the maximum number is (Max), what the minimum number is (Min), what Max to the power of Min (Max^Min) is, and what the product of all numbers is. Of course, such questions are no problem for Xiao Z. However, he recently had a sudden idea to explore deeper properties of this sequence, so he decided to keep deleting some numbers from the sequence and study the current sequence after each deletion. Since the sequence has many terms, this causes a lot of trouble for Xiao Z, so he asks you to write a program to perform the following operations.

Problem Description

You need to maintain a multiset that supports five operations:

• D x Delete $x$; it is guaranteed that $x$ exists. If there are multiple occurrences, delete only one.
• B Query the maximum value in the set.
• S Query the minimum value in the set.
• M Let the maximum be $a$ and the minimum be $b$; query $a^b \bmod 317847191$.
• T Query the product of all numbers, modulo $317847191$.

For all queries, the multiset is guaranteed to be non-empty.

Input Format

The first line contains two positive integers $n, m$, the initial multiset size and the number of operations.
The second line contains $n$ positive integers $a_i$, the initial multiset.
Then $m$ lines follow, each describing one operation.

Output Format

For each query, output one integer per line representing the answer.

3 6
2 6 9
M
D 9
B
S
M
T

81
6
2
36
12

Hint

Constraints
For partial testdata, $1 \le n \le 1000$, $1 \le m \le 100$, $1 \le a_i \le 400$.
For $100\%$ of the testdata, $1 \le n, m \le 10^6$, $1 \le a_i \le 10^8$.

Translated by ChatGPT 5