如下定义一个在 Alice 和 Bob 之间进行的数字游戏：选中一个正整数 $n$, 之后 Alice 会在 $1$ 到 $n$ 之间选取一个整数 $x$, 每次 Bob 会选择一些区间并询问 Alice $x$ 是不是在其中的某个区间内，一个特殊的规则就是，Alice 可以撒谎至多一次。
在游戏中，给定一个 $n$, 所有的问题已经由 Bob 提出，并由 Alice 一一回答。请计算 Bob 为了确定整数 $x$ ，最少需要额外问几次。
输入格式
每个测试点最多包含 $10000$ 组测试数据，每组数据包含 $n$, $m$ （Bob 已经问的问题数），用一个空格隔开
下面紧跟 $m$ 行，每行第一个整数 $c$, 之后 $c$ 对 $[s_i, t_i], (1\le s_i \le t_i \le n) $, 表示本次询问中的第 $i$ 个区间，最后一个字符串 yes 或 no 表示 Alice 给出的答案，假设 Alice 十分遵守规则，且 Bob 如果继续进行游戏，一定能确定 $x$ 的值
输出格式
对于每组测试数据，输出一行包含一个整数，表示最少需要额外问的次数
样例数据
样例输入
1 0 2 0 2 2 1 1 1 yes 1 1 1 no 2 2 1 1 1 yes 1 1 1 yes 2 3 1 1 1 yes 1 1 1 no 1 1 1 yes
样例输出
0 3 1 0 0
限制
$1 \leq n \leq 10^{16}$, $0 \leq m \leq 10$, 且 $1 \leq c \leq 100$
特别鸣谢楼天城和吉如一提供试题，数据。