In recent years, the commercial development in country A has been rapid, but the domestic road construction has not kept up with the pace, which has clearly become a restriction on people's trade and has caused great concern for the managers.

Specifically, there are $2^n-1$ cities in country A, where city $1$ is the capital. For all non-capital cities $i$, there is a single one-way road that starts from city $i$ and reaches city $\lfloor \frac{i}{2}\rfloor$. For convenience, these roads are called "first-class roads", and the city $\lfloor \frac{i}{2}\rfloor$ is called the "superior city" of city $i$.

In addition, there are $m$ directed roads, where the $i$-th road goes from city $u_i$ to city $v_i$, and they all have a special property: starting from city $v_i$ and continuously walking along the first-class roads towards the "superior city", one can always reach city $u_i$. These roads are called "second-class roads".

Each road has a corresponding length. Therefore, for any two cities $x$ and $y$ in country A, one can calculate the minimum value of the sum of the lengths of the roads passed through from city $x$ to city $y$, and this value is denoted as $\mathrm{dist}(x,y)$. However, due to serious defects in the road construction in country A, it may be impossible to reach city $y$ from city $x$. For convenience, $\mathrm{dist}(x,y)$ is defined as $0$ in this case. At the same time, a city does not need to pass through any road to reach itself, so $\mathrm{dist}(x,x)$ is defined as$0$.

Now, the managers hope to calculate these $\mathrm{dist}(x,y)$ values in order to measure the convenience of people's trade. However, since there are too many cities in country A, listing all these values one by one is too time-consuming. Therefore, the managers only hope to find the sum of all $\mathrm{dist}(x,y)$ values, that is, $\sum _{i=1}^{2^n-1}\sum _{y=1}^{2^n-1}\mathrm{dist}(x,y)$, and they hope that you can help.

Since the answer may be very large, you only need to output the answer modulo $998244353$.

Input Specification

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

The second line of input contains $2^n-2$ positive integers. The $i$-th integer $a_i$ represents the length of the "first-class road" from city $i+1$ to city $\lfloor \frac{i+1}{2}\rfloor$.

Then $m$ lines follow, each containing three positive integers $u,v$ and $w$, representing a "second-class road" from city $u$ to city $v$ with length $w$.

Output Specification

Output a line containing an integer, representing the answer, taken modulo $998244353$.

Sample Input 1

2 1
2 1
1 2 2

Sample Output 1

8

Additional Samples

Sample inputs and outputs can be found here.

• Sample 2 (ex_trade2.in and ex_trade2.ans).
• Sample 3 (ex_trade3.in and ex_trade3.ans).
• Sample 4 (ex_trade4.in and ex_trade4.ans).

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

Test ID	$n$	$m$	Additional Constraints
$1\sim 2$	$=8$	$\le 256$	None
$3\sim 4$	$=9$	$\le 512$
$5\sim 8$	$=12$	$\le 4096$
$9$	$=16$	$\le 10$
$10$		$\le 50$
$11$		$\le 100$
$12$		$\le 65536$	A
$13\sim 15$			None
$16\sim 17$	$=18$	$\le 262144$	A
$18\sim 20$			None

Additional Constraint A: It is guaranteed that every "second-class road" starts from the capital (city $1$).