Problem Description

In recent years, the commerce of Country A has been developing rapidly, but the domestic road construction has not kept pace, clearly becoming a limitation for trade. The managers have been racking their brains over this issue.

Specifically, Country A has $2^n-1$ cities, with City 1 being the capital. For every non-capital city $i$, there is a one-way road from City $i$ to City $\lfloor \frac{i}{2} \rfloor$. For convenience, such roads are called "Type 1 Roads," and City $\lfloor \frac{i}{2} \rfloor$ is referred to as the "superior city" of City $i$.

Additionally, there are $m$ one-way roads. The $i$-th road of these goes from City $u_i$ to City $v_i$. These roads have a special property: starting from City $v_i$ and continuously moving to the "superior city" along Type 1 Roads, one will eventually reach City $u_i$. Such roads are called "Type 2 Roads."

Each road has a corresponding length value. Therefore, for any two cities $x$ and $y$ in Country A, one can calculate the minimum sum of the lengths of the roads traveled from City $x$ to City $y$, denoted as $dist(x,y)$. However, due to the severe deficiencies in Country A's road construction, it might be impossible to travel from City $x$ to City $y$, in which case $dist(x,y)$ is defined as $0$. Also, traveling from a city to itself does not require any roads, so $dist(x,x)$ is defined as $0$.

Now, the managers wish to calculate these $dist(x,y)$ values to reasonably measure the convenience of trade. However, due to the large number of cities, listing these values individually is too cumbersome. Therefore, the managers only want to find the sum of all $dist(x,y)$ values, which is $\sum_{x=1}^{2^n-1}{\sum_{y=1}^{2^n-1}{dist(x,y)}}$, and they hope you can help with this.

Input Format

The first line of input contains two positive integers $n$ and $m$.

The second line contains $2^n-2$ positive integers, where the $i$-th number $a_i$ represents the length of the Type 1 Road from City $i+1$ to City $\lfloor \frac{i+1}{2} \rfloor$.

The next $m$ lines each contain three positive integers $u, v, w$, describing a Type 2 Road from City $u$ to City $v$ with length $w$.

Output Format

Output a single positive integer, representing the corresponding answer. Since the answer may be very large, you only need to output the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

2 1
2 1
1 2 2

Sample Output #1

8

Sample Input #2

See the attached file trade/trade2.in.

Sample Output #2

See the attached file trade/trade2.ans.

Sample Input #3

See the attached file trade/trade3.in.

Sample Output #3

See the attached file trade/trade3.ans.

Sample Input #4

See the attached file trade/trade4.in.

Sample Output #4

See the attached file trade/trade4.ans.

Notes/Hints

[Data Range]

For all test data, it is guaranteed that: $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$.

Special Property: Each Type 2 Road starts from the capital (City 1).

见题面 Input 部分

见题面 Output 部分