近年来，A 国的商贸发展迅猛，但国内的道路建设却跟不上步伐，明显成为了人们贸易往来的限制，管理者为此费尽了心思。

具体而言，A 国共有 2^n-1 个城市，其中 1 号城市为首都。对于所有的非首都城市 i，都有一条单向道路从城市 i 出发，到达城市 \lfloor \frac{i}{2} \rfloor。为方便起见，称这样的道路为“第一类道路”，称城市 \lfloor \frac{i}{2} \rfloor 为城市 i 的“上级城市”。

除此之外，还有 m 条单向道路，设其中第 i 条道路从城市 u_i 出发，到达城市 v_i，这样的道路都有一个特殊性质：从城市 v_i 出发，沿着第一类道路不断向“上级城市”走去，最终总能走到城市 u_i。称这样的道路为“第二类道路”。

每一条道路都有相应的长度值。由此，对于 A 国的任意两个城市 x 和 y，都可以计算出从城市 x 出发，沿道路走到城市 y，所经过的道路的长度之和的最小值，将这一数值记为 dist(x,y)。但由于 A 国的道路建设存在严重缺陷，从城市 x 出发可能根本到达不了城市 y，此时定义 dist(x,y)=0。同时一个城市出发到自己是不需要经过任何道路的，因此定义 dist(x,x)=0。

现在管理者希望计算出这些 dist(x,y) 的值，以便合理衡量人们贸易往来的便捷程度。但由于 A 国的城市数量太多，将这些值一一列出的工作量太大，因此管理者只希望求出所有 dist(x,y) 值之和，也就是 $\sum{x=1}^{2^n-1}{\sum{y=1}^{2^n-1}{dist(x,y)}}$，并希望请你来帮忙。

输入的第一行包含两个正整数 n 和 m。

输入的第二行包含 2^n-2 个正整数，第 i 个数 a_i 表示从城市 i+1 出发, 到达城市 \lfloor \frac{i+1}{2} \rfloor 的“第一类道路”的长度。

接下来的 m 行，每行包含三个正整数 u,v,w，描述了一条从城市 u 到城市 v 的“第二类道路”, 其长度为 w。

输出一行一个正整数，表示对应的答案。由于答案可能很大, 你只需要输出模 998244353 意义下的答案即可。

对于所有测试数据保证：2 \le n \le 18，1 \le m \le 2 ^ n，1 \le u, v \le 2 ^ n - 1，1 \le a_i, w \le 10 ^ 9。

特殊性质：保证每一条“第二类道路”都是从首都（城市 1）出发。

NOI