#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int) (n); i++)
using namespace std;

#define INF 100000000
#define MAX_N 18

int N, ds0[MAX_N], ds1[MAX_N], d[MAX_N][MAX_N], dp[1<<MAX_N][MAX_N];

int rec(int bit, int v){
    if(dp[bit][v] < INF) return dp[bit][v];
    if(bit == (1<<v)) return dp[bit][v] = ds1[v];
    
    int prev_bit = bit & ~(1<<v), res = INF;
    
    rep(u, N){
        if(!(prev_bit & (1<<u))) continue;
        res = min(res, rec(prev_bit, u) + d[u][v]);
    }
    return dp[bit][v] = res;
}

int main(){
    cin >> N;
    int X[N], Y[N], Z[N];
    rep(i, N) cin >> X[i] >> Y[i] >> Z[i];
    rep(i, (1<<N)) rep(j, N) dp[i][j] = INF;
    rep(i, N) ds1[i] = abs(X[i + 1] - X[0]) + abs(Y[i + 1] - Y[0]) + max(0, Z[i + 1] - Z[0]);
    rep(i, N) ds0[i] = abs(X[i + 1] - X[0]) + abs(Y[i + 1] - Y[0]) + max(0, Z[0] - Z[i + 1]);
    rep(i, N) rep(j, N) d[i][j] = abs(X[i + 1] - X[j + 1]) + abs(Y[i + 1] - Y[j + 1]) + max(0, Z[j + 1] - Z[i + 1]);
    int ans = INF;
    rep(i, N - 1) ans = min(ans, rec((1<<(N - 1)) - 1, i) + ds0[i]);
    cout << ans << endl;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const long long MOD =  998244353;
const long long INF = 9999999999999999;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
long long pow(long long x, long long n, long long MM) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MM;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MM;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}



int main(){
  ll N;
  cin>>N;
  vector <ll> a(N);
  rep(i,N){
    cin>>a[i];
  }
  sort(all(a));
  ll temp = 0;
  rep(i,N){
    if(i == 0){
      temp += a[i];
      temp%=MOD;
    }
    else{
      temp += a[i]*pow(2,i-1,MOD);
      temp%=MOD;
    }
  }
  ll waru = pow(2,MOD-2,MOD);
  ll ans = 0;
  rep(i,N){
    if(i != (N-1)){
      ans += a[i]*temp%MOD;
      ans%=MOD;
      if(temp<(a[i]+a[i+1])){
        temp+=MOD;
      }
      temp -= a[i];
      temp -= a[i+1];
      temp *= waru%MOD;
      temp%=MOD;
      temp += a[i+1];
      temp%=MOD;
      //cout << ans << endl;
      //cout << temp << endl;
    }
    else{
      ans += a[N-1]*a[N-1]%MOD;
      ans%=MOD;
    }
  }
  cout << ans%MOD << endl;
  return 0;
}
      