题目描述

有一个长为 $n$ 的跑道，位置 $i$ 有两个道具 $a_{i, 0}, a_{i, 1}$ ，其中每个道具是 $+x, * x$ 这两种中的一种现给定 $q$ 组询问，每次给定三个数字 $u, l, r$ ，表示 $u$ 个人要从跑道的位置 $l$ 开始跑酤到位置 $r$ ，毎到达一个位置（包括起点和终点），便可选取该位置上两个道具中的一个。并以此改变当前的人数，问从 $l$走到 $r$ 人数最多可能可以变成多少，输出模 998244353 的结果。

输入格式

第一行一个整数 $n\left(1 \leq n \leq 10^5\right)$ ，表示跑道的长度。 接下来 $n$ 行，每行两个字符串 $a_{i, 0}, a_{i, 1}$ ，毎个字符串由首位运算字符 $o p(o p \in\{+, *\})$ 和后续数字 $x\left(1 \leq x \leq 10^9\right)$ 组成。表示位置 $i$ 上的道具。 接下来一行一个整数 $q\left(1 \leq q \leq 10^5\right)$ ，表示询问组数。 接下来 $q$ 行。每行三个整数 $u, l, r\left(1 \leq u \leq 10^9, 1 \leq l \leq r \leq n\right)$ ，表示一次询问。

输出格式

输出共 $q$ 行，每行一个整数，表示询问答案模 998244353 的结果。

样例输入1

5
+3 +1
+4 *1
*5 *9
*2 +6
+5 +3
2
1 1 4
5 4 5

样例输出1

144
16

Note

• 对于第一组询问，可以分别选取 $+3,+4, * 9, * 2$ 四个道具，最终人数为 $(((1+3)+4) \times 9) \times 2=144$ 。
• 对于第二组询问，可以分别选取 $+6,+5$ 两个道具，最终人数为 $(5+6)+5=16$ 。