给你一个排列 \(a_1,\cdots,a_n\) 以及 \(m\) 次操作，操作有两种：

1. \(b_i=\min(X,Y)\)
2. \(b_i=\max(X,Y)\)

其中 \(X,Y\) 可能是 \(a_j(1\leq j\leq n)\) 或者 \(b_j(1\leq j\lt i)\) 。

现在排列 \(a_1,\cdots,a_n\) 是随机的，求 \(b_m\) 的期望值。

多组测试数据 \((\leq 20)\) ，你可以用EOF判断输入结束。

每组数据第一行两个整数 \(n(2\leq n\leq 15)\) 和 \(m(1\leq m\leq 1000)\) 。

接下来 \(m\) 行，每行一个操作，格式如下：

1. \(\min\quad tp_0\quad id_0\quad tp_1\quad id_1\)
2. \(\max\quad tp_0\quad id_0\quad tp_1\quad id_1\)

其中一组 \((tp,id)\) 表示一个变量， \(tp\in\{\texttt{a},\texttt{b}\}\) 。

每组数据输出一行，包含一个整数 \(E[b_m]\times n!\) 。