In recent years, the trade of Country A has developed rapidly, but the domestic road construction has not kept pace, which has clearly become a limitation on trade exchanges, causing the administrators much concern.

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 called the "superior city" of city $i$.

In addition, there are $m$ one-way roads. Let the $i$-th such road go from city $u_i$ to city $v_i$. These roads have a special property: starting from city $v_i$ and continuously moving towards the "superior city" along Type 1 roads, one can always eventually reach city $u_i$. Such roads are called "Type 2 roads."

Each road has a corresponding length. Thus, for any two cities $x$ and $y$ in Country A, one can calculate the minimum sum of lengths of the roads traversed to travel from city $x$ to city $y$, denoted as $dist(x, y)$. However, due to severe defects in the road construction of Country A, it may be impossible to reach city $y$ from city $x$. For convenience, we define $dist(x, y) = 0$ in this case. Also, no roads need to be traversed to travel from a city to itself, so we define $dist(x, x) = 0$.

Now, the administrators wish to calculate these $dist(x, y)$ values to reasonably measure the convenience of trade exchanges. However, because the number of cities in Country A is too large, the workload of listing these values one by one is too great. Therefore, the administrators only wish 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 for your help.

Input

The first line 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

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

Constraints

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$, and $1 \le a_i, w \le 10^9$.

Special property: It is guaranteed that every "Type 2 road" starts from the capital (city 1).

Examples

Input 1

2 1
2 1
1 2 2

Output 1

8