为制作果核大陆，果冻需要编织一个精妙的法术集合。一个法术集合由许多子魔法构成。经研究，贤者禾枫发现可以通过调整子魔法的消耗改变果核大陆的各种属性。于是他们开始研究如何对异世界现有魔法进行调整。
果冻发现，法术集合能以树的形式表示，树上每个节点代表组成该法术集合的子魔法，每个节点都要消耗能量。树有 n 个节点，编号从 1 到 n ，第 i 个节点的消耗为 a_i 。对于树上两点，定义这两点形成的链为这两点之间的最短路径。
为了调整果核大陆的各种属性并实时观测效果，果冻开始进行实验。果冻每次可以选择两个节点，对于这两个节点形成的链，果冻可以在以下 3 种操作中选择一种执行：
操作 1 : 减小链上的每个节点的消耗，即：对链上的每个节点 x ，其消耗减小 a_x\&(-a_x) ，其中 \& 是按位与运算。
操作 2 : 增大链上的每个节点的消耗，即：对链上的每个节点 x ，若 a_x\neq0 ，则其消耗增大 2^k ，其中 k 是满足 2^k\le a_x < 2^{k+1} 的整数。
操作 3 : 查询链上所有节点的消耗之和对 998244353 取模的结果。
输入
输入一行一个整数 n
接下来输入一行 n 个整数，第 i 个整数代表初始消耗 a_i
接下来输入 n-1 行，每行两个整数 u,v ，代表节点 u,v 间连有一条边
接下来输入一行一个整数 q ，代表事件个数
接下来输入 q 行，每行三个整数 c,l,r
对 20\% 分数的数据，1\le n,q\le10^3
对 100\% 分数的数据， 1\le n,q\le10^5,1\le u,v,l,r\le n,1\le a_i\le10^9,1\le c\le3 ，保证输入的边能够形成一棵树
输出
对于每个查询，输出一行一个整数，代表编号为 l,r 的两点形成的链上的消耗之和对 998244353 取模的结果。
样例
| 标准输入 复制文本 |
5 5 2 2 9 7 1 2 1 3 3 4 3 5 4 1 2 5 3 1 5 2 5 4 3 4 2 |
| 标准输出 复制文本 |
10 21 |