On activities held by Algorithm Association, lemon teas are provided to the participants almost infinitely. To store such a large number of lemon teas, Rikka wants to build some storehouses.
Rikka plans to build storehouses, together with N-1 bidirectional roads. The i-th road connects the (i+1)-th storehouse and the -th storehouse.
These storehouses will be built on an uneven piece of land. For each , the altitude of the i-th storehouse is known to be . Rikka can choose the altitudes for other storehouses arbitrarily. (The value of altitude can be any real number).

Carrying lemon teas on a steep hill is difficult. Rikka wants to make the road system as convenient as possible. Therefore, Rikka wants to minimize the square sum of the altitude difference of each road, i.e.

Due to the geological movement, the altitude of the last storehouses often changes. Lucky, it is free for Rikka to change the altitude of the first storehouses at any time.
Your task is to help Rikka to find out the optimal plan after each change.

The first line contains two integers .
The second line contains  integers , representing  in order, where . 
Then m lines follow, each line with two integers , representing the altitude of the -th storehouse is changed to  during the i-th movement.

Output m+1 lines, each with a single number: the initial value of ans followed by the value of ans after each movement.
Writing a special judge is a tiring task. Therefore, you are required to output the answer module 998244353. Formally, if the simplest fraction representation of ans is , you need to output .

2 0
1 3

2

For the first sample, one optimal solution is  and the value of ans is .

3 3
1 2 3 4
6 4
5 4
4 4

332748120
83187032
748683270
0