#include <bits/stdc++.h>

using namespace std;

void fastio() {
	cin.tie(nullptr);
	cin.sync_with_stdio(false);
}

using LL = long long;
using LD = long double;

const LL MOD = 998244353;
const LL INF = LLONG_MAX;
const LL N = 3e5+1;

#define S second
#define F first
#define vt vector

LL binpow (LL x, LL p, LL m) {
	LL res = 1;
	x %= m;

	while (p) {
		if (p&1) {
			res = res * x % m;
		}
		x = x * x % m;
		p >>= 1;
	}
	return res;
}

int main () {
	fastio();

	LL n, k;
	cin >> n >> k;

	vt<LL> a(n);

	for (LL i = 0; i < n; ++i) {
		cin >> a[i];
	}

	vt<vt<LL>> binom(k+1, vt<LL>(k+1));
	binom[0][0] = 0;

	for (LL i = 1; i <= k; ++i) {
		binom[i][0] = binom[i][i] = 1;

		for (LL j = 1; j <= i-1; ++j) {
			binom[i][j] = binom[i-1][j-1]+binom[i-1][j];
			binom[i][j] %= MOD;
		}
	}

	vt<vt<LL>> sum(k+1, vt<LL>(n, 1));

	for (LL i = 0; i < n; ++i) {
		sum[1][i] = a[i];
	}
	for (LL i = 2; i <= k; ++i) {
		for (LL j = 0; j < n; ++j) {
			sum[i][j] = (sum[1][j]*sum[i-1][j]) % MOD;
		}
	}

	vt<LL> sumacc(k+1, 0);
	LL twoinv = binpow(2, MOD-2, MOD);
	LL tp = 2;

	for (LL i = 0; i <= k; ++i) {
		for (LL j = 0; j < n; ++j) {
			sumacc[i] = (sumacc[i] + sum[i][j])%MOD;
		}
	}

	for (LL i = 1; i <= k; ++i, tp <<= 1, tp %= MOD) {
		LL accum = 0;
		for (LL j = 0; j <= i; ++j) {
			accum = (accum + sumacc[j]*sumacc[i-j] % MOD * binom[i][j] % MOD) % MOD;
		}
		accum = ((accum - tp * sumacc[i] % MOD) % MOD + MOD) % MOD;
		accum = (accum * twoinv) % MOD;
		cout << accum << "\n";
	}


}
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
using namespace std;


typedef struct edge{
	int to;
	int cost;
}Edge;
typedef pair<int,int> P;

long long INF=250000010;
int V;
vector<Edge> G[1000000];
long long d[1000000];

void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P>> que;
	fill(d,d+V,INF);
	d[s]=0;
	que.push(P(0,s));
	while(!que.empty()){
		P p=que.top();que.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(unsigned int i=0;i<G[v].size();i++){
		  Edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
			  d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

int main(){
  int R,C;
  cin>>R>>C;
  V=R*C*2;
  vector<vector<int>> A,B;
  for(int i=0;i<R;i++){
    vector<int>tmp(C-1);
    for(int j=0;j<C-1;j++)cin>>tmp.at(j);
    A.push_back(tmp);
  }
  for(int i=0;i<R-1;i++){
    vector<int>tmp(C);
    for(int j=0;j<C;j++)cin>>tmp.at(j);
    B.push_back(tmp);
  }
  int q=R*C;
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      if(j<C-1){
        G[C*i+j].push_back({C*i+j+1,A.at(i).at(j)});
      }
      if(j>0){
        G[C*i+j].push_back({C*i+j-1,A.at(i).at(j-1)});
      }
      if(i<R-1){
        G[C*i+j].push_back({C*(i+1)+j,B.at(i).at(j)});
      }
      G[C*i+j].push_back({q+C*i+j,1});
      G[q+C*i+j].push_back({C*i+j,0});
      if(i>0){
        G[q+C*i+j].push_back({q+C*(i-1)+j,1});
      }
    }
  }
  dijkstra(0);
  printf("%d\n",d[R*C-1]);
  return 0;
}