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\limits_{i=1}^{2^n-1}\sum\limits_{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 \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~.

Test ID	~n~	~m~	Additional Constraints
~1 \sim 2~	~=8~	~\leq 256~	None
~3 \sim 4~	~=9~	~\leq 512~
~5 \sim 8~	~=12~	~\leq 4\,096~
~9~	~=16~	~\leq 10~
~10~		~\leq 50~
~11~		~\leq 100~
~12~		~\leq 65\,536~	A
~13\sim 15~			None
~16\sim 17~	~=18~	~\leq 262\,144~	A
~18\sim 20~			None

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