Monocarp 有 $$$n$$$ 数字 $$$1、2、\dots、n$$$ 和一组(最初为空)。他按某种顺序将自己的数字 $$$n$$$ 次添加到这个集合中。在每个步骤中,他都会添加一个新数字(之前的集合中没有出现过)。换句话说,数字相加的序列是长度$$$n$$$的排列。
除了第一次之外,每次 Monocarp 向集合中添加一个元素时,他都会写出一个字符:
- 如果 Monocarp 尝试插入的元素成为集合中的最大元素,Monocarp 会写出字符 >;
- 如果 Monocarp 尝试插入的元素成为集合中的最小元素,Monocarp 会写出字符 <;
- 如果以上都不是,Monocarp 会写出字符 ?。
给定一个由 $$$n-1$$$ 个字符组成的字符串 $$$s$$$,它代表 Monocarp 写出的字符(按照他写出的顺序)。您必须处理对字符串的 $$$m$$$ 查询。每个查询都具有以下格式:
- $$$i$$$ $$$c$$$ — 将 $$$s_i$$$ 替换为字符 $$$c$$$。
在处理查询之前和每次查询之后,您都必须计算对整数 $$$1, 2, 3, \dots, n$$$ 进行排序的不同方式的数量,这样,如果 Monocarp 按该顺序将整数插入到集合中,他会得到字符串 $$$s$$$。由于答案可能很大,请以 $$$998244353$$$ 为模打印它们。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m \le 3 \cdot 10^5$$$)。
第二行包含字符串 $$$s$$$,由 $$$n-1$$$ 字符 <、> 和/或 ? 组成。
然后是 $$$m$$$ 行。它们中的每一个都代表一个查询。每行包含一个整数 $$$i$$$ 和一个字符 $$$c$$$ ($$$1 \le i \le n-1$$$;$$$c$$$ 是 <、> 或 ?)。
输出
在处理查询之前和每次查询之后,打印一个整数 - 对整数 $$$1, 2, 3, \dots, n$$$ 进行排序的方法数,这样,如果 Monocarp 按该顺序将整数插入到集合中,他会得到字符串 $$$s$$$。由于答案可能很大,请以 $$$998244353$$$ 为模打印它们。
示例
输入 #1
6 4 <?>?> 1 ? 4 < 5 < 1 >
输出 #1
3 0 0 0 1
输入 #2
2 2 > 1 ? 1 <
输出 #2
1 0 1
注意
在第一个示例中,所有查询之前有三种可能的排序:
- $$$3, 1, 2, 5, 4, 6$$$;
- $$$4, 1, 2, 5, 3, 6$$$;
- $$$4, 1, 3, 5, 2, 6$$$.
最后一次查询后,只有一种可能的排序:
- $$$3, 5, 4, 6, 2, 1$$$.