/* #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include */ #include /* #include using namespace atcoder; using mint = modint998244353; */ using namespace std; using C = complex; const int mod = 998244353; const long long LINF = 1001002003004005006; const int INF = 1001001001; const double PI = acos(-1); const int MX = 200005; const int dx[4] = {-1,0,1,0}; const int dy[4] = {0,-1,0,1}; const int di[8] = {1,1,1,0,0,-1,-1,-1}; const int dj[8] = {1,0,-1,1,-1,1,0,-1}; int getint(){int x; scanf("%d",&x);return x;} # define sz(x) (int)(x).size() # define rsz(x,n) x.resize(n) # define yes {puts("Yes"); return;} # define no {puts("No"); return;} # define dame {puts("-1"); return;} # define yn {puts('Yes');} else{puts('No');} # define ret(x) {cout << (x) << endl; return;} # define ll long long # define fi first # define se second # define be begin # define en end # define vi vector # define vl vector # define vs vector # define vb vector # define vm vector # define vvi vector> # define vvl vector> # define vvb vector> # define vpi vector> # define vpl vector> # define vps vector> # define pb push_back # define ps push # define eb emplace_back # define em emplace # define pob pop_back # define S sort # define N next_permutation # define rep(i,n) for(int i = 0; i < (n); ++i) # define rrep(i, a, b) for(int i = a; i < b; i++) # define lrep(i, a, b) for(ll i = a; i < b; i++) # define srep(i, a, b) for(int i = a; i <= b; ++i) # define slrep(i, a, b) for(ll i = a; i <= b; ++i) # define drep(i, a, b) for(int i = a; i >= b; --i) # define dlrep(i, a, b) for(ll i = a; i >= b; --i) # define ALL(obj) (obj).begin(), (obj).end() # define rALL(obj) (obj).rbegin(), (obj).rend() # define Pll pair # define P pair void read() {} template void read(T &t, U &...u) { cin >> t; read(u...); } void out() { cout << endl; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } /* struct combination { vector fact, ifact; combination(int n):fact(n+1),ifact(n+1) { assert(n < mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i; } mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return fact[n]*ifact[k]*ifact[n-k]; } }; */ ll gcd (ll x, ll y) {return x ? gcd(y%x, x) : y;} ll lcm (ll x, ll y) {return x/gcd(x,y)*y;} vector> factorize(ll n) { vector> res; for(ll i = 2; i*i <= n; ++i) { if(n%i) continue; res.eb(i,0); while(n%i == 0) { n /= i; res.back().se++; } } if(n != 1) res.eb(n,1); return res; } ll binary_pow(ll a, ll n) { if(n == 0) return 1; ll x = binary_pow(a,n/2); x *= x; if(n%2) x *= a; return x; } ll pascal[4500][4500]; void pascal_init() { pascal[0][0] = 1; rep(i,4400) { rep(j,i+1) { pascal[i+1][j] += pascal[i][j]; pascal[i+1][j+1] += pascal[i][j]; } } } vector prime_table(ll n) { vector prime(n+1,true); prime[0] = false; prime[1] = false; for(ll i = 2; i*i <= n; i++) { if(!prime[i]) continue; for(int j = i*i; j <= n; j += i) prime[j] = false; } return prime; } vector divisor(ll n) { vl res; for(ll i = 1; i*i <= n; ++i) { if(n%i == 0) { res.pb(i); if(i*i != n) res.pb(n/i); } } S(ALL(res)); return res; } C input_complex() { double x, y; read(x,y); return C(x,y); } vector> runLengthEncoding(string s) { int n = s.length(); vector> res; char pre = s[0]; int cnt = 1; rrep(i, 1, n) { if (pre != s[i]) { res.push_back({ pre, cnt }); pre = s[i]; cnt = 1; } else cnt++; } res.push_back({ pre, cnt }); return res; } vector topologicalSort(vector> &G, vector &inDegree, int nodenum) { vector res; //答え用の配列 priority_queue, greater<>> q; //入次数が0の頂点の処理待ち //辞書順が最小のものを返す rep(i,nodenum) if(inDegree[i] == 0) q.push(i); while(sz(q)) { int v = q.top(); q.pop(); rep(i,sz(G[v])) { int u = G[v][i]; --inDegree[u]; if(inDegree[u] == 0) q.push(u); } res.push_back(v); } return res; } template vector dijkstra(vector>>& graph, int start) { int n = graph.size(); vector res(n, 2e18); res[start] = 0; priority_queue, vector>, greater>> que; que.push({0, start}); while(!que.empty()) { auto[c, v] = que.top(); que.pop(); if(res[v] < c) continue; for(auto[cost, nxt]: graph[v]) { if(res[v]+cost < res[nxt]) { res[nxt] = res[v] + cost; que.push(Pll(res[nxt], nxt)); } } } return res; } /* vvi to; vi go_in; vi go_out; vb seen; void dfs_time_stamp(int v, int &ptr) { go_in[v] = ptr++; //行きがけ seen[v] = true; for (auto u : to[v]) { if (seen[u]) continue; dfs(u,ptr); } go_out[v] = ptr++;//帰りがけ } */ /* vvi to; void dfs(int v, int p = -1) { for (auto u : to[v]) { if(u == p) continue; dfs(u,v); } } */ struct Solver { void solve() { int n; read(n); vl A(n); rep(i,n) read(A[i]); //dp[msk] : 集合mskの人がpairになっているときの戦闘力の最大値 vector dp(1<<14); rep(msk,1<