Trade

In recent years, commercial development in country A has been rapid, but domestic road construction has not kept up with it. This clearly restricts people's trade and worries the managers greatly.

Specifically, country A has $2^n-1$ cities, and city $1$ is the capital. For every non-capital city $i$, there is a single one-way road from city $i$ to city $\lfloor \frac{i}{2}\rfloor$. These are called "first-class roads", and city $\lfloor \frac{i}{2}\rfloor$ is called the "superior city" of city $i$.

In addition, there are $m$ directed roads. The $i$-th road goes from city $u_i$ to city $v_i$. All of them have one special property: starting from city $v_i$ and repeatedly walking along first-class roads toward the superior city, one can always reach city $u_i$. These roads are called "second-class roads".

Each road has a length. For any two cities $x$ and $y$, let $\mathrm{dist}(x, y)$ be the minimum total length of the roads on a path from $x$ to $y$. Some pairs may be unreachable because of serious defects in the road construction. In that case $\mathrm{dist}(x, y)$ is defined as $0$. A city needs no road to reach itself, so $\mathrm{dist}(x, x)$ is defined as $0$.

The managers want to measure the convenience of trade through these $\mathrm{dist}(x, y)$ values. Listing every value takes too long, so they only want the sum $\sum_{x=1}^{2^n-1}\sum_{y=1}^{2^n-1}\mathrm{dist}(x, y)$. Please help them compute it.

Since the answer may be very large, output it modulo $998244353$.

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

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

Then $m$ lines follow. Each line contains three positive integers $u$, $v$, and $w$, which describe a second-class road from city $u$ to city $v$ with length $w$.

Output one line containing an integer, the answer modulo $998244353$.

For all test data, $2 \leq n \leq 18$, $1 \leq m \leq 2^n$, $1 \leq u, v \leq 2^n-1$, and $1 \leq a_i, w \leq 10^9$.