题目描述

近年来，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$，所经过的道路的长度之和的最小值，将这一数值记为 $\mathop{dist}(x,y)$。但由于 A 国的道路建设存在严重缺陷，从城市 $x$ 出发可能根本到达不了城市 $y$，此时定义 $\mathop{dist}(x,y)=0$。同时一个城市出发到自己是不需要经过任何道路的，因此定义 $\mathop{dist}(x,x)=0$。

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

输入格式

从文件 trade.in 中读入数据。

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

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

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

输出格式

输出到文件 trade.out 中。

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

样例 1

输入

$2$ $1$ $2$ $1$ $1$ $2$ $2$

输出

$8$

样例 2

见附加文件中的 trade2.in 与 trade2.ans。

样例 3

见附加文件中的 trade3.in 与 trade3.ans。

样例 4

见附加文件中的 trade4.in 与 trade4.ans。

数据范围与提示

对于所有测试数据保证：$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$。