무역

최근 A국에서는 상업 개발이 빠르게 진행되고 있지만, 국내 도로 건설이 그 속도를 따라가지 못하고 있다. 이는 사람들의 무역을 분명히 제약하며 관리자들에게 큰 우려가 되고 있다.

구체적으로 A국에는 $2^n-1$개의 도시가 있고, 1번 도시가 수도이다. 수도가 아닌 모든 도시 $i$에는 도시 $i$에서 도시 $\lfloor \frac{i}{2}\rfloor$로 가는 일방통행 도로가 하나씩 있다. 이 도로를 '1급 도로'라고 부르고, 도시 $\lfloor \frac{i}{2}\rfloor$를 도시 $i$의 '상위 도시'라고 부른다.

또한 $m$개의 방향 도로가 있다. $i$번째 도로는 도시 $u_i$에서 도시 $v_i$로 간다. 이 도로들에는 모두 특별한 성질이 있다. 도시 $v_i$에서 출발해 1급 도로를 따라 상위 도시 방향으로 계속 이동하면 반드시 도시 $u_i$에 도달할 수 있다. 이 도로들을 '2급 도로'라고 부른다.

각 도로에는 길이가 있다. 임의의 두 도시 $x$, $y$에 대해 $x$에서 $y$로 가는 경로 위 도로 길이의 합의 최솟값을 $\mathrm{dist}(x, y)$로 나타낸다. 도로 건설에 심각한 결함이 있어 $x$에서 $y$로 갈 수 없는 경우도 있다. 이때 $\mathrm{dist}(x, y)$는 0으로 정의한다. 도시는 도로를 거치지 않고 자기 자신에게 도달하므로 $\mathrm{dist}(x, x)$는 0으로 정의한다.

관리자들은 이 $\mathrm{dist}(x, y)$ 값들로 무역의 편의성을 재고자 한다. 그러나 모든 값을 하나씩 나열하기에는 시간이 너무 오래 걸린다. 따라서 $\sum_{x=1}^{2^n-1}\sum_{y=1}^{2^n-1}\mathrm{dist}(x, y)$의 합만 구하고자 한다. 이 합을 계산하는 것을 도와 달라.

답이 매우 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

첫 줄에 양의 정수 $n$과 $m$이 주어진다.

둘째 줄에는 양의 정수 $2^n-2$개가 주어진다. $i$번째 정수 $a_i$는 도시 $i+1$에서 도시 $\lfloor\frac{i+1}{2}\rfloor$로 가는 1급 도로의 길이이다.

이어서 $m$개의 줄이 주어진다. 각 줄에는 양의 정수 $u$, $v$, $w$가 주어지며, 이는 도시 $u$에서 도시 $v$로 가는 길이 $w$의 2급 도로를 나타낸다.

답을 나타내는 정수를 한 줄에 출력한다. 값은 998244353으로 나눈 나머지이다.

모든 테스트 데이터에 대해 $2 \leq n \leq 18$, $1 \leq m \leq 2^n$, $1 \leq u, v \leq 2^n-1$, $1 \leq a_i, w \leq 10^9$가 보장된다.