fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    for (t in 1..T) {
        val (n, x) = readLine()!!.split(' ').map { it.toLong() }
        println(x * 2)
    }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
	int q;
	cin >> q;
	forn(_, q){
		int n, m;
		cin >> n >> m;
		vector<string> s(n);
		forn(i, n)
			cin >> s[i];
		vector<int> cntn(n), cntm(m);
		forn(i, n) forn(j, m){
			cntn[i] += (s[i][j] == '.');
			cntm[j] += (s[i][j] == '.');
		}
		int ans = n + m;
		forn(i, n) forn(j, m){
			ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
		}
		cout << ans << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int q;
string s, t, p;
int cnt[30];

int main() {
	cin >> q;
	for(int iq = 0; iq < q; ++iq){
		cin >> s >> t >> p;
		memset(cnt, 0, sizeof cnt);
		for(auto x : p)
			++cnt[x - 'a'];

		bool ok = true;
		int is = 0, it = 0;
		while(is < s.size()){
			if(it == t.size()){
				ok = false;
				break;
			}
			
			if(s[is] == t[it]){
				++is, ++it;
				continue;
			}
			
			--cnt[t[it] - 'a'];
			++it;
		}
        while(it < t.size()){
            --cnt[t[it] - 'a'];
			++it;
        }
        
		if(*min_element(cnt, cnt + 30) < 0)
			ok = false;

		if(ok) cout << "YES\n";
		else cout << "NO\n";
	}		
	return 0;
}                             	



}                             	

#include <bits/stdc++.h>
using namespace std;

int n, k;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	return true;
}

void solve() {
	bool win = true;
	if(k % 3 == 0) {
		int np = n % (k + 1);
		if(np % 3 == 0 && np != k)
			win = false;
	} else {
		int np = n % 3;
		if(np == 0)
			win = false;
	}
	
	puts(win ? "Alice" : "Bob");
}

int main(){
	int T; cin >> T;
	while(T--) {
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair

const int N = 10009;
const int INF = 1000000009;
 
int n;
vector <pair<int, int> > vs[N], hs[N];
int f[N];
vector <int> d[N];

void upd(int pos, int x){
	for(; pos < N; pos |= pos + 1)
		f[pos] += x;
}

int get(int pos){
	int res = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += f[pos];
	return res;
}

int get(int l, int r){
	return get(r) - get(l - 1);
}

const int D = 5000;

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1 += D, y1 += D, x2 += D, y2 += D; 
		if(y1 == y2) 
			hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) );	
		else 
			vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) );	
	}

	long long res = 0;
	for(int y = 0; y < N; ++y) for(auto s : hs[y]){
		for(int i = 0; i < N; ++i) d[i].clear();
		memset(f, 0, sizeof f);

		int l = s.first, r = s.second;
		for(int x = l; x <= r; ++x) for(auto s2 : vs[x])
			if(s2.first <= y && s2.second > y) {
				d[s2.second].push_back(x);
				upd(x, 1);
			}

		for(int y2 = y + 1; y2 < N; ++y2){
			for(auto s2 : hs[y2]){			
				int cur = get(s2.first, s2.second);
				res += cur * (cur - 1) / 2;
			}
			for(auto x : d[y2]) upd(x, -1);
		}
	}

	cout << res << endl;
	return 0;
}                             	

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}

const int MOD = int(1e9) + 7;

inline int norm(int a) {
    if(a >= MOD) a -= MOD;
    if(a < 0) a += MOD;
    return a;
}
inline int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}
inline int binPow(int a, int k) {
    int ans = 1;
    while(k > 0) {
        if(k & 1) ans = mul(ans, a);
        a = mul(a, a);
        k >>= 1;
    }
    return ans;
}
inline int inv(int a) {
    return binPow(a, MOD - 2);
}

int n;
li T;
vector<li> t;

inline bool read() {
    if(!(cin >> n >> T))
        return false;
    t.resize(n);
    fore(i, 0, n)
        cin >> t[i];
    return true;
}

vector<int> f, inf;

int C(int n, li k) {
    if(k > n || k < 0)
        return 0;
    return mul(f[n], mul(inf[k], inf[n - k]));
}

inline void solve() {
    f.resize(n + 5);
    inf.resize(n + 5);
    f[0] = inf[0] = 1;
    fore(i, 1, sz(f)) {
        f[i] = mul(i, f[i - 1]);
        inf[i] = mul(inf[i - 1], inv(i));
    }

    int sumC = 1;
    li bd = T;
    int pw2 = 1, i2 = (MOD + 1) / 2;

    vector<int> p(n + 1, 0);
    fore(i, 0, n) {
        pw2 = mul(pw2, i2);

        sumC = norm(mul(2, sumC) - C(i, bd));
        li need = t[i];
        if(bd > i + 1) {
            li sub = min(bd - i - 1, need);
            bd -= sub, need -= sub;
        }
        li rem = min(bd + 1, need);
        fore(k, 0, rem)
            sumC = norm(sumC - C(i + 1, bd - k));
        bd -= rem;

        p[i] = mul(sumC, pw2);
    }

    int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD);
    cout << ans << endl;
//    cerr << mul(ans, binPow(2, n)) << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 105;

int a[N];
int n;
int numPos[10], denPos[10];
int num, den;
const int MOD = 998244353;

struct halfState
{
	int carry;
	int mask;
	bool comp;
	
	halfState() {};
	halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {};
};

bool operator <(const halfState& x, const halfState& y)
{
	if(x.carry != y.carry) return x.carry < y.carry;
	if(x.mask != y.mask) return x.mask < y.mask;
	return x.comp < y.comp;
}

bool operator ==(const halfState& x, const halfState& y)
{
	return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp;
}

bool operator !=(const halfState& x, const halfState& y)
{
	return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp;
}

halfState go(const halfState& s, int pos, int digit, bool isNum)
{
	int newDigit = digit * (isNum ? num : den) + s.carry;
	int newCarry = newDigit / 10;
	newDigit %= 10;
	int newMask = s.mask;
	int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]);
	if(maskPos != -1) newMask |= (1 << maskPos);
	bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp);
	return halfState(newCarry, newMask, newComp);
}

struct state
{
	halfState numState;
	halfState denState;
	
	state() {};
	state(halfState numState, halfState denState) : numState(numState), denState(denState) {};
	
	void norm()
	{
		if(numState.mask & denState.mask)
			numState.mask = denState.mask = 1;
	};
	
	bool valid()
	{
		return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0);
	};
};

bool operator <(const state& x, const state& y)
{
	if(x.numState != y.numState) return x.numState < y.numState;
	return x.denState < y.denState;
}

state go(const state& s, int pos, int digit)
{
	halfState newNum = go(s.numState, pos, digit, true);
	halfState denNum = go(s.denState, pos, digit, false);
	state res(newNum, denNum);
	res.norm();
	return res;
}

int add(int x, int y)
{
	return (x + y) % MOD;
}

int ans = 0;

void calcFixed(int x, int y)
{
	num = x;
	den = y;
	for(int i = 0; i <= 9; i++)
		numPos[i] = denPos[i] = -1;
	int cnt = 0;
	for(int i = 1; i <= 9; i++)
		for(int j = 1; j <= 9; j++)
			if(i * y == j * x)
			{
				numPos[i] = denPos[j] = cnt++;
			}
	vector<map<state, int> > dp(102);
	dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1;
	for(int i = 0; i <= 100; i++)
		for(auto x : dp[i])
		{
			state curState = x.first;
			int curCount = x.second;
			for(int j = 0; j <= 9; j++)
			{
				state newState = go(curState, i, j);
				dp[i + 1][newState] = add(dp[i + 1][newState], curCount);
			}
		}
	for(auto x : dp[101])
	{
		state curState = x.first;
		int curCount = x.second;
		if(curState.valid())
			ans = add(ans, curCount);
	}
}

int main()
{
	string s;
	cin >> s;
	int len = s.size();
	reverse(s.begin(), s.end());
	for(int i = 0; i < len; i++)
	{
		a[i] = s[i] - '0';
 	}
 	for(int i = 1; i <= 9; i++)
 		for(int j = 1; j <= 9; j++)
 			if(__gcd(i, j) == 1)
 				calcFixed(i, j);
 	cout << ans << endl;
}

fun main(args: Array<String>) {
    val tc = readLine()!!.toInt()
    for (i in 1..tc) {
        val (n, s, t) = readLine()!!.split(' ').map { it.toInt() }
        println(maxOf(n - s, n - t) + 1)
    }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n, m;
string s, t;
vector<int> pos[26];

int main() {
	cin >> n >> s;
	forn(i, n)
		pos[s[i] - 'a'].push_back(i + 1);
	
	cin >> m;
	forn(i, m){
		cin >> t;
		vector<int> cnt(26);
		for (auto &c : t)
			++cnt[c - 'a'];
		int ans = -1;
		forn(j, 26) if (cnt[j] > 0)
			ans = max(ans, pos[j][cnt[j] - 1]);
		cout << ans << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int n, m;
int l[N], r[N], s[N];
int d[N];
int dx[N];
int res[N];
int nxt[N];

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; ++i){
		scanf("%d %d %d", s + i, l + i, r + i);
		--l[i], --r[i];
		if(s[i] == 1)
			++d[l[i]], --d[r[i]];
	}

	memset(dx, -1, sizeof dx);
	int sum = 0;
	for(int i = 0; i < n - 1; ++i){
		sum += d[i];
		if(sum > 0)	
			dx[i] = 0;
	}		

	res[0] = n;
	for(int i = 1; i < n; ++i)
		res[i] = res[i - 1] + dx[i - 1];	

	nxt[n - 1] = n - 1;
	for(int i = n - 2; i >= 0; --i){
		if(res[i] <= res[i + 1])
			nxt[i] = nxt[i + 1];
		else 
			nxt[i] = i;
	}			

	for(int i = 0; i < m; ++i){
		if(s[i] != (nxt[l[i]] >= r[i])){
			puts("NO");
			return 0;		
		}
	}	

	puts("YES");
	for(int i = 0; i < n; ++i)
		printf("%d ", res[i]);
	puts("");

	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;

int t, n;
int a[N], b[N];
vector <int> p[N];
int st[4 * N + 55];

int getMin(int v, int l, int r, int L, int R){
	if(L >= R) return INF;
	if(l == L && r == R)
		return st[v];

	int mid = (l + r) / 2;
	return min(getMin(v * 2 + 1, l, mid, L, min(R, mid)),
		getMin(v * 2 + 2, mid, r, max(mid, L), R));	
}

void upd(int v, int l, int r, int pos, int x){
	if(r - l == 1){
		st[v] = x;
		return;
	}

	int mid = (l + r) / 2;
	if(pos < mid) upd(v * 2 + 1, l, mid, pos, x);
	else upd(v * 2 + 2, mid, r, pos, x);
		
	st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

int main() {
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			p[i].clear();					
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			--a[i];
			p[a[i]].push_back(i);	
		}	
		for(int i = 0; i < n; ++i){
			scanf("%d", b + i);	
			--b[i];		
		}

		for(int i = 0; i < 4 * n; ++i) st[i] = INF;
		for(int i = 0; i < n; ++i){
			reverse(p[i].begin(), p[i].end());
			if(!p[i].empty()) upd(0, 0, n, i, p[i].back());
		}

		bool ok = true;
		for(int i = 0; i < n; ++i){
			if(p[b[i]].empty()){
				ok = false;
				break;
			}

			int pos = p[b[i]].back();
			if(getMin(0, 0, n, 0, b[i]) < pos){
				ok = false;
				break;
			}

			p[b[i]].pop_back();
			upd(0, 0, n, b[i], p[b[i]].empty()? INF : p[b[i]].back());			
		}

		if(ok) puts("YES");
		else puts("NO");
	}	
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
long long ans;
vector<int> siz;
vector<long long> dp;
vector<vector<int>> g;

int calcsize(int v, int p = -1) {
	siz[v] = 1;
	for (auto to : g[v]) {
		if (to == p) continue;
		siz[v] += calcsize(to, v);
	}
	return siz[v];
}

long long calcdp(int v, int p = -1) {
	dp[v] = siz[v];
	for (auto to : g[v]) {
		if (to == p) continue;
		dp[v] += calcdp(to, v);
	}
	return dp[v];
}

void dfs(int v, int p = -1) {
	ans = max(ans, dp[v]);
	for (auto to : g[v]) {
		if (to == p) continue;
		
		dp[v] -= dp[to];
		dp[v] -= siz[to];
		siz[v] -= siz[to];
		siz[to] += siz[v];
		dp[to] += siz[v];
		dp[to] += dp[v];
		
		dfs(to, v);
		
		dp[to] -= dp[v];
		dp[to] -= siz[v];
		siz[to] -= siz[v];
		siz[v] += siz[to];
		dp[v] += siz[to];
		dp[v] += dp[to];
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	ans = 0;
	siz = vector<int>(n);
	dp = vector<long long>(n);
	
	calcsize(0);
	calcdp(0);
	dfs(0);
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long li;

using namespace std;

const int N = 200 * 1000 + 13;

int n;
vector<int> g[N];

int siz[N];
li sum[N];

void init(int v, int p = -1){
	siz[v] = 1;
	sum[v] = 0;
	for (auto u : g[v]) if (u != p){
		init(u, v);
		siz[v] += siz[u];
		sum[v] += sum[u];
	}
	sum[v] += (siz[v] - 1);
}

li dp[N];

void dfs(int v, int p = -1){
	dp[v] = 0;
	li tot = 0;
	for (auto u : g[v]) if (u != p)
		tot += sum[u];
	for (auto u : g[v]) if (u != p){
		dfs(u, v);
		dp[v] = max(dp[v], (n - siz[u] - 1) + dp[u] + (tot - sum[u]));
	}
	if (g[v].size() == 1){
		dp[v] = n - 1;
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	if (n == 2) {
		cout << 3 << endl;
		return 0;
	}
	
	forn(i, n) if (int(g[i].size()) > 1){
		init(i);
		dfs(i);
		printf("%lld\n", dp[i] + n);
		break;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = int(1e9) + 7;

int norm(int a) {
	while(a >= MOD) a -= MOD;
	while(a < 0) a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
	int ans = 1;
	for(; k > 0; k >>= 1) {
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
	}
	return ans;
}
int inv(int a) {
	int b = binPow(a, MOD - 2);
	assert(mul(a, b) == 1);
	return b;
}

int n;
vector<int> l, r;

inline bool read() {
	if(!(cin >> n))
		return false;
	l.resize(n);
	r.resize(n);
	
	fore(i, 0, n)
		cin >> l[i];
	fore(i, 0, n) {
		cin >> r[i];
		r[i]++;
	}
	return true;
}

vector<int> p;

int calcEq(int i0) { 
	int i1 = i0 + 1;
	int pSame = 0;
	if(i0 > 0) {
		int cnt = max(0, min({r[i0 - 1], r[i0], r[i1]}) - max({l[i0 - 1], l[i0], l[i1]}));
		pSame = mul(cnt, inv(mul(mul(r[i0 - 1] - l[i0 - 1], r[i0] - l[i0]), r[i1] - l[i1])));
	}
	return norm(1 - norm(2 - p[i0] - p[i1]) + pSame);
}

inline void solve() {
	p.assign(n, 0);
	p[0] = 1;
	fore(i, 1, n) {
		int cnt = max(0, min(r[i - 1], r[i]) - max(l[i - 1], l[i]));
		p[i] = norm(1 - mul(cnt, inv(mul(r[i - 1] - l[i - 1], r[i] - l[i]))));
	}
	
	int sum = 0;
	fore(i, 0, n)
		sum = norm(sum + p[i]);
	
	int ans = 0;
	fore(i, 0, n) {
		int curS = sum;
		for(int j = max(0, i - 1); j < min(n, i + 2); j++)
			curS = norm(curS - p[j]);
		
		ans = norm(ans + mul(p[i], curS));
		
		if(i > 0)
			ans = norm(ans + calcEq(i - 1));
		ans = norm(ans + p[i]);
		if(i + 1 < n)
			ans = norm(ans + calcEq(i));
	}
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
} 

#include<bits/stdc++.h>

using namespace std;

struct edge
{
	int y, c, f, cost;
	edge() {};
	edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};

vector<edge> e;

const int N = 14043;
vector<int> g[N];

long long ans = 0;
long long d[N];
int p[N];
int pe[N];
int inq[N];

const long long INF64 = (long long)(1e18);

int s = N - 2;
int t = N - 1;

int rem(int x)
{
	return e[x].c - e[x].f;
}

void push_flow()
{
	for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0;
	d[s] = 0;
	queue<int> q;
	q.push(s);
	inq[s] = 1;
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		inq[k] = 0;
		for(auto x : g[k])
		{
			if(!rem(x)) continue;
			int c = e[x].cost;
			int y = e[x].y;
			if(d[y] > d[k] + c)
			{
				d[y] = d[k] + c;
				p[y] = k;
				pe[y] = x;
				if(inq[y] == 0)
				{
					inq[y] = 1;
					q.push(y);
				}
			}
		}
	}
	int cur = t;
//	vector<int> zz(1, cur);
	while(cur != s)
	{
		e[pe[cur]].f++;
		e[pe[cur] ^ 1].f--;
		cur = p[cur];
//		zz.push_back(cur);
	}
//	reverse(zz.begin(), zz.end());
//	for(auto x : zz) cerr << x << " ";
//	cerr << endl;
	ans += d[t];
}

void add_edge(int x, int y, int c, int cost)
{
	g[x].push_back(e.size());
	e.push_back(edge(y, c, 0, cost));
	g[y].push_back(e.size());
	e.push_back(edge(x, 0, 0, -cost));
}

int main()
{
	int n, m, k, c, d;
	cin >> n >> m >> k >> c >> d;
	for(int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		--x;
		add_edge(s, x, 1, 0);
	}
	int tt = 101;
	for(int i = 0; i < tt; i++)
		add_edge(0 + i * n, t, k, i * c);
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		for(int i = 0; i < tt - 1; i++)
			for(int j = 0; j < k; j++)
				add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1));
		for(int i = 0; i < tt - 1; i++)
			for(int j = 0; j < k; j++)
				add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1));
 	}
 	for(int i = 0; i < n; i++)
 		for(int j = 0; j < tt - 1; j++)
 			add_edge(i + j * n, i + j * n + n, k, 0);
 	for(int i = 0; i < k; i++)
 		push_flow();
 	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

long long n, k;

int main(){
    int tc;
    cin >> tc;
    for(int i = 0; i < tc; ++i){
    	cin >> n >> k;
    	long long res = 0;
    	while(n > 0){
    	    if(n % k == 0){
    	        n /= k;
    	        ++res;
    	    }
    	    else{
    	        long long rem = n % k;
    	        res += rem;
    	        n -= rem;
    	    }
    	}
    	
    	cout << res << endl;
    }
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

const long long INF = 1ll << 32;

int main(){
	int l;
	cin >> l;
	
	stack<long long> cur;
	cur.push(1);
	
	long long res = 0;
	forn(_, l){
		string t;
		cin >> t;
		if (t == "for"){
			int x;
			cin >> x;
			cur.push(min(INF, cur.top() * x));
		}
		else if (t == "end"){
			cur.pop();
		}
		else{
			res += cur.top();
		}
	}
	
	if (res >= INF)
		cout << "OVERFLOW!!!" << endl;
	else
		cout << res << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

int n, k;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	a.resize(n);
	fore(i, 0, n)
		cin >> a[i];
	return true;
}

inline void solve() {
	pair<int, int> ans = {int(1e9) + 7, -1};
	fore(i, 0, n - k) {
		int dist = a[i + k] - a[i];
		ans = min(ans, make_pair(dist, a[i] + dist / 2));
	}
	
	cout << ans.second << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	
	while(tc--) {
	    read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300009;

int n, k;
int a[N];

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	
	long long sum = 0;
	vector <long long> v;
	for(int i = n - 1; i >= 0; --i){
	    sum += a[i];
	    if(i > 0) v.push_back(sum);
	}
	
	long long res = sum;
	
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	
	
	for(int i = 0; i < k - 1; ++i)
	    res += v[i];
	    
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;
const int LOGN = 18;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int up[LOGN][N];

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	forn(i, n)
		up[0][i] = nxt[a[i].y];
	for (int j = 1; j < LOGN; ++j) forn(i, n){
		if (up[j - 1][i] == -1)
			up[j][i] = -1;
		else
			up[j][i] = up[j - 1][up[j - 1][i]];
	}
	
	forn(i, m){
		int x = nxt[q[i].x];
		
		if (x == -1){
			puts("-1");
			continue;
		}
		
		int res = 1;
		for (int j = LOGN - 1; j >= 0; --j){
			int y = up[j][x];
			if (y == -1)
				continue;
			if (a[y].y < q[i].y){
				res += (1 << j);
				x = y;
			}
		}
		
		if (a[x].y >= q[i].y)
			printf("%d\n", res);
		else if (up[0][x] == -1)
			puts("-1");
		else
			printf("%d\n", res + 1);
	}
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int ans[N];

pair<int, int> p[N];

pair<int, int> get(int x, int r){
	if (x == -1)
		return make_pair(-1, -1);
	if (a[x].y >= r)
		return make_pair(x, 0);
	auto res = get(p[x].x, r);
	if (res.x == -1)
		p[x] = make_pair(-1, -1);
	else
		p[x] = make_pair(res.x, p[x].y + res.y);
	return p[x];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	vector<int> perm(m);
	iota(perm.begin(), perm.end(), 0);
	sort(perm.begin(), perm.end(), [](int a, int b){
		return q[a].y < q[b].y;
	});
	
	forn(i, n)
		p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1);
	
	for (auto i : perm){
		int x = nxt[q[i].x];
		auto res = get(x, q[i].y).y;
		ans[i] = (res == -1 ? -1 : res + 1);
	}
	
	forn(i, m)
		printf("%d\n", ans[i]);
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> pt;

const int N = int(3e5) + 99;
const pt zero = make_pair(0, 0);

int n;
int a[N];
pt hsh[N], sumHsh[N];

void upd(pt &a, pt b){
    a.first ^= b.first;
    a.second ^= b.second;
}

int calc(int pos){
	set <int> sl, sr;
	set<pt> s;
	int r = pos + 1, l = pos - 1;
	pt curr = hsh[0], curl = zero;
	s.insert(zero);
	sr.insert(0), sl.insert(0);
	
	int res = 0;	
	while(r < n && !sr.count(a[r])){
		sr.insert(a[r]);
		upd(curr, hsh[a[r]]);
		++r;

		while(l >= 0 && !sl.count(a[l]) && a[l] < *sr.rbegin()){
			sl.insert(a[l]);
			upd(curl, hsh[a[l]]);
			s.insert(curl);
			--l;	
		}

		pt need = sumHsh[*sr.rbegin()];
		upd(need, curr);
		if(s.count(need)) ++res;
	}	

	return res;
}	

int main() {
    long long x = 0;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		--a[i];	
		x ^= a[i];
	}
	
	
	mt19937_64 rnd(time(NULL));
	for(int i = 0; i < N; ++i){
		hsh[i].first = rnd() ^ x;
		hsh[i].second = rnd() ^ x;
		sumHsh[i] = hsh[i];
		if(i > 0) upd(sumHsh[i], sumHsh[i - 1]);
	}
	
	int res = 0;
		
	for(int tc = 0; tc < 2; ++tc){
		for(int i = 0; i < n; ++i)
			if(a[i] == 0)
				res += calc(i) + (tc == 0);
		reverse(a, a + n);
	}
	cout << res << endl;

	return 0;
} 

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) (int)((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e9);

pt operator -(const pt &a, const pt &b) {
    return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
    return a.x * b.x + a.y * b.y;
}
li operator %(const pt &a, const pt &b) {
    return a.x * b.y - a.y * b.x;
}
pt rotate(const pt &p) {
    return {-p.y, p.x};
}

struct LinearHull {
    deque<pt> pts, vecs;

    void addRight(const pt &l) {
        while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) {
            vecs.pop_back();
            pts.pop_back();
        }
        if(!pts.empty())
            vecs.push_back(rotate(l - pts.back()));
        pts.push_back(l);
    }
    void addLeft(const pt &l) {
        while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) {
            vecs.pop_front();
            pts.pop_front();
        }
        if(!pts.empty())
            vecs.push_front(rotate(pts.front() - l));
        pts.push_front(l);
    }

    li getMin(const pt &x) {
        auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) {
            return a % b > 0;
        });
        return x * pts[it - vecs.begin()];
    }
};

typedef unique_ptr<LinearHull> pHull;

void mergeHulls(pHull &a, pHull &b) {
    if(sz(b->pts) >= sz(a->pts)) {
        for(auto &p : a->pts)
            b->addRight(p);
    } else {
        for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++)
            a->addLeft(*it);
        swap(a, b);
    }
}

const int M = 1000 * 1000 + 555;
int szn = 0;
struct node {
    pt line;
    node *l, *r;

    node() : line(), l(nullptr), r(nullptr) {}
    node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {}
} nodes[M];

typedef node* tree;

tree getNode(const pt &line, tree l, tree r) {
    assert(szn < M);
    nodes[szn] = node(line, l, r);
    return &nodes[szn++];
}
tree copy(tree v) {
    if(v == nullptr) return v;
    return getNode(v->line, v->l, v->r);
}

li f(const pt &line, int x) {
    return line * pt{x, 1};
}

tree addLine(tree v, int l, int r, pt line) {
    if(!v)
        return getNode(line, nullptr, nullptr);
    int mid = (l + r) >> 1;
    bool lf = f(line, l) < f(v->line, l);
    bool md = f(line, mid) < f(v->line, mid);

    if(md)
        swap(v->line, line);

    if(l + 1 == r)
        return v;
    else if(lf != md)
        v->l = addLine(copy(v->l), l, mid, line);
    else
        v->r = addLine(copy(v->r), mid, r, line);
    return v;
}

li getMin(tree v, int l, int r, int x) {
    if(!v) return INF64;
    if(l + 1 == r)
        return f(v->line, x);
    int mid = (l + r) >> 1;

    if(x < mid)
        return min(f(v->line, x), getMin(v->l, l, mid, x));
    else
        return min(f(v->line, x), getMin(v->r, mid, r, x));
}

int n, k;
vector<li> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);

    fore(i, 0, n)
        cin >> a[i];
    return true;
}

struct state {
    int pos;
    pHull hull;
    tree v;

    state() : pos(-1), hull(nullptr), v(nullptr) {}
};

vector<li> d[2];

inline void solve() {
    int maxn = (int)*max_element(a.begin(), a.end()) + 3;
    fore(k, 0, 2)
        d[k].resize(n + 1, INF64);

    d[0][0] = 0;
    fore(_k, 1, k + 1) {
        szn = 0;

        int ck = _k & 1;
        int nk = ck ^ 1;

        vector< state > st;

        fore(i, 0, sz(d[ck])) {
            d[ck][i] = INF64;
            if(!st.empty())
                d[ck][i] = getMin(st.back().v, 0, maxn, i);

            if(i >= sz(a))
                continue;

            state curVal;
            curVal.pos = i;
            curVal.hull = make_unique<LinearHull>();
            curVal.hull->addRight({-i, d[nk][i]});
            curVal.v = nullptr;

            while(!st.empty() && a[st.back().pos] < a[i]) {
                mergeHulls(st.back().hull, curVal.hull);
                st.pop_back();
            }
            if(!st.empty())
                curVal.v = st.back().v;

            li val = curVal.hull->getMin({a[i], 1});
            curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val});

            st.push_back(move(curVal));
        }
    }
    cout << d[k & 1][n] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    int tc;
    cin >> tc;
    for(int t = 0; t < tc; ++t){
        cin >> n >> s;
        int pos = n;
        for(int i = 0; i < n; ++i)
            if(s[i] == '8'){
                pos = i;
                break;
            }
            
        if(n - pos >= 11)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

vector<int> p = {4, 8, 15, 16, 23, 42};
int ans[4];

int main()
{
	for(int i = 0; i < 4; i++)
	{
		cout << "? " << i + 1 << " " << i + 2 << endl;
		cout.flush();
		cin >> ans[i];
	}
	do
	{
		bool good = true;
		for(int i = 0; i < 4; i++)
			good &= (p[i] * p[i + 1] == ans[i]);
		if(good) break;
	}
	while(next_permutation(p.begin(), p.end()));
	cout << "!";
	for(int i = 0; i < 6; i++)
		cout << " " << p[i];
	cout << endl;
	cout.flush();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1000043;
vector<int> g[N];

int color[N];
int siz[N];
int n, m;
int cc = 0;

int dfs(int x)
{
	if(color[x])
		return 0;
	color[x] = cc;
	int ans = (x < n ? 1 : 0);
	for(auto y : g[x])
		ans += dfs(y);
	return ans; 
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++)
	{
		int k;
		scanf("%d", &k);
		for(int j = 0; j < k; j++)
		{
			int x;
			scanf("%d", &x);
			--x;
			g[x].push_back(i + n);
			g[i + n].push_back(x);
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(!color[i])
		{
			cc++;
			siz[cc] = dfs(i);
		}
		printf("%d ", siz[color[i]]);
	}
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;

int n, m;
int rk[N], p[N];

int getP(int a){
	return (a == p[a] ? a : p[a] = getP(p[a]));
}

void unite(int a, int b){
	a = getP(a), b = getP(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	p[b] = a;
	rk[a] += rk[b];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n) p[i] = i, rk[i] = 1;
	
	forn(i, m){
		int k;
		scanf("%d", &k);
		int lst = -1;
		forn(j, k){
			int x;
			scanf("%d", &x);
			--x;
			if (lst != -1)
				unite(x, lst);
			lst = x;
		}
	}
	
	forn(i, n)
		printf("%d ", rk[getP(i)]);
	puts("");
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

int n;
string s;

inline bool read() {
	if(!(cin >> n))
		return false;
	cin >> s;
	return true;
}

inline void solve() {
	string t(n, '0');
	
	int bal = 0;
	fore(i, 0, n) {
		if(s[i] == ')')
			bal--;
		
		t[i] = char('0' + (bal & 1));
		
		if(s[i] == '(')
			bal++;
	}
	
	cout << t << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e6) + 99;
int n, x;
int a[N];
vector <int> pos[N];
int prefMax[N];

int main() {
	scanf("%d %d", &n, &x);
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		pos[a[i]].push_back(i);	
		prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i]));
	}
	
	int p = 1;
	int lst = n + 5;
	for(int i = x; i >= 1; --i){
		if(pos[i].empty()){
		    p = i;
		    continue;
		}
		if(pos[i].back() > lst) break;
		p = i;
		lst = pos[i][0];
	}	

	long long res = 0;
	lst = -1;
	for(int l = 1; l <= x; ++l){
		int r = max(l, p - 1);
		if(lst != -1) r = max(r, prefMax[lst]);
		res += x - r + 1;
		if(!pos[l].empty()){
    		if(pos[l][0] < lst) break;
    		lst = pos[l].back();
		}
	}	

	cout << res << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

const int MOD = int(1e9) + 7;

int add(int a, int b) {
	a += b;
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}

int n;
vector<int> a;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore(i, 0, n)
		cin >> a[i];
	return true;
}

vector<li> f;
void inc(int pos, int val) {
	for(; pos < sz(f); pos |= pos + 1)
		f[pos] += val;
}
li sum(int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[pos];
	return ans;
}

vector<int> S[2];

inline void solve() {
	fore(k, 0, 2) {
		S[k].assign(n, 0);
		f.assign(n, 0);
		
		vector<int> dx(a.begin(), a.end());
		sort(dx.begin(), dx.end());
		
		fore(i, 0, n) {
			int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin());
			S[k][i] = int(sum(pos) % MOD);
			inc(pos, i + 1);
		}
		reverse(a.begin(), a.end());
	}
	
	reverse(S[1].begin(), S[1].end());
	int ans = 0;
	fore(i, 0, n) 
		ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 1)))));
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = 200 * 1000 + 555;
const int D = 7077;

int n, d, m;
int a[N], qs[N];

inline bool read() {
	if(scanf("%d%d", &n, &d) != 2)
		return false;
	fore(i, 0, n)
		scanf("%d", &a[i]);
	
	assert(scanf("%d", &m) == 1);
	fore(i, 0, m)
		scanf("%d", &qs[i]);
	return true;
}

bitset<D> L, R, cur;
int dist[N];
set<int> has;

void shiftL(int s, int t, int &uk) {
	L <<= t - s;
	for(; uk < n && a[uk] < t; uk++) {
		if(t - a[uk] - 1 < D)
			L[t - a[uk] - 1] = 1;
		if(t - a[uk] < D)
			L[t - a[uk]] = 1;
	}
}

void shiftR(int s, int t, int &uk) {
	R >>= t - s;
	if(!has.count(t))
		R[0] = 0;
	
	for(; uk < n && a[uk] < t + D; uk++) {
		if(a[uk] - t >= 0) {
			R[a[uk] - t] = 1;
			if(a[uk] - t + 1 >= 0)
				R[a[uk] - t + 1] = 1;
		}
	}
}

inline void solve() {
	fore(i, 0, m) {
		dist[i] = INF;
		int pos = int(lower_bound(a, a + n, qs[i]) - a);
		if(pos > 0)
			dist[i] = qs[i] - a[pos - 1] - 1;
		if(pos < n)
			dist[i] = min(dist[i], a[pos] - qs[i]);
	}
	has = set<int>(a, a + n);
	
	int uL = 0, uR = 0;
	L.reset();
	R.reset();
	fore(i, 0, m) {
		shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL);
		shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR);
		
		double ans = atan2(1, dist[i]);

		cur = L & R;
		int pos = (int)cur._Find_first();
		if(pos < D) {
			int ds = pos;
			ans = max(ans, 2 * atan2(1, ds));
		}
		printf("%.15f\n", ans);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	int sum = 0;
	int lst = 1;
	vector<int> figs;
	forn(i, n){
		int x;
		scanf("%d", &x);
		if (lst != 1 && x != 1){
			puts("Infinite");
			return 0;
		}
		if (x != 1){
			figs.push_back(x);
			sum += x + 1;
			if (i != 0 && i != n - 1)
				sum += x + 1;
		}
		lst = x;
	}
	forn(i, int(figs.size()) - 1) if (figs[i] == 3 && figs[i + 1] == 2)
		--sum;
	printf("Finite\n%d\n", sum);
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

bool check(string s){
	bool ok = true;
	forn(i, int(s.size()) - 1)
		ok &= (abs(s[i] - s[i + 1]) != 1);
	return ok;
}

int main() {
	int T;
	scanf("%d", &T);
	static char buf[120];
	forn(_, T){
		scanf("%s", buf);
		string s = buf;
		string odd = "", even = "";
		forn(i, s.size()){
			if (s[i] % 2 == 0)
				odd += s[i];
			else
				even += s[i];
		}
		sort(odd.begin(), odd.end());
		sort(even.begin(), even.end());
		if (check(odd + even))
			printf("%s\n", (odd + even).c_str());
		else if (check(even + odd))
			printf("%s\n", (even + odd).c_str());
		else
			puts("No answer");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int n, z;
int a[N];

int main()
{
	scanf("%d", &n);
	scanf("%d", &z);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int l = 0;
	int r = n / 2 + 1;
	while(r - l > 1)
	{
		int m = (l + r) / 2;
		bool good = true;
		for(int i = 0; i < m; i++)
			good &= (a[n - m + i] - a[i] >= z);
		if(good)
			l = m;
		else
			r = m;
	}
	cout << l << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int p[2][N];
int siz[2][N];

int get(int x, int c)
{
	if(p[c][x] == x)
		return x;
	return p[c][x] = get(p[c][x], c);
}

void merge(int x, int y, int c)
{
	x = get(x, c);
	y = get(y, c);
	if(siz[c][x] < siz[c][y])
		swap(x, y);
	p[c][y] = x;
	siz[c][x] += siz[c][y];
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		p[0][i] = p[1][i] = i;
		siz[0][i] = siz[1][i] = 1;
	}
	for(int i = 0; i < n - 1; i++)
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		--x;
		--y;
		merge(x, y, c);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(p[0][i] == i)
			ans += siz[0][i] * 1ll * (siz[0][i] - 1);
		if(p[1][i] == i)
			ans += siz[1][i] * 1ll * (siz[1][i] - 1);
		ans += (siz[0][get(i, 0)] - 1) * 1ll * (siz[1][get(i, 1)] - 1);
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int lf[N];
int rg[N];
int n;
int ans = 0;
int p[N];
int q[N];

void update(int l, int r, int l2, int r2, int sum)
{
	for(int i = l; i <= r; i++)
	{
		int o = sum - p[i];
		if(o >= 1 && o <= n && l2 <= q[o] && q[o] <= r2)
			ans++;
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &p[i]);
		q[p[i]] = i;
	}
	stack<pair<int, int> > s;
	s.push(make_pair(n + 1, -1));
	for(int i = 0; i < n; i++)
	{
		while(s.top().first < p[i])
			s.pop();
		lf[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	while(!s.empty())
		s.pop();
	s.push(make_pair(n + 1, n));
	for(int i = n - 1; i >= 0; i--)
	{
		while(s.top().first < p[i])
			s.pop();
		rg[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	for(int i = 0; i < n; i++)
	{
	//	cerr << i << " " << lf[i] << " " << rg[i] << endl;
		int lenl = i - lf[i] - 1;
		int lenr = rg[i] - i - 1;
		if(lenl == 0 || lenr == 0)
			continue;
		if(lenl < lenr)
			update(lf[i] + 1, i - 1, i + 1, rg[i] - 1, p[i]);
		else
			update(i + 1, rg[i] - 1, lf[i] + 1, i - 1, p[i]);
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5005;

void upd(int &a, int b){
    a += b;
    a %= MOD;
}

int mul(int a, int b){
    return (a * 1LL * b) % MOD;
}

int bp(int a, int n){
    int res = 1;
    for(; n > 0; n >>= 1){
        if(n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int getInv(int a){
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n;
int cnt[N];
int suf[N];
int dp[N][N];
int sum[N][N];
int inv[N];

int main(){
    for(int i = 1; i < N; ++i)
        inv[i] = getInv(i);
        
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        ++cnt[x];
    }
    cnt[0] = 1;
    for(int i = N - 2; i >= 0; --i)
        suf[i] = suf[i + 1] + cnt[i];
        
    for(int x = n; x >= 0; --x)
        for(int y = n; y >= 0; --y){
            if(cnt[x] == 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            int s = n - y;
            if(s <= 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            
            upd(dp[x][y], mul(cnt[x] - 1, inv[s]));
            upd(dp[x][y], mul(sum[x + 1][y + 1], inv[s]));
            
            upd(sum[x][y], sum[x + 1][y]);
            upd(sum[x][y], mul(cnt[x], dp[x][y]));
        }
    
    cout << dp[0][0] << endl;
	return 0;
}

Решение, которое описано в разборе.

Решение жюри:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;


struct expr {
	string t; // variable name or operation
	expr * l, * r; // only if operation
	long long hash;
	
	expr (string var)
		: t(var), l(0), r(0), hash(0)
		{ }
	expr (char op, expr * l, expr * r)
		: t(1,op), l(l), r(r), hash(0)
		{ }

	long long calc_hash() {
		if (!hash)
			if (!l) {
				long long pw = 257;
				for (size_t i=0; i<t.length(); ++i,  pw*=97)
					hash += t[i] * pw;
			}
			else
				hash += l->calc_hash() * t[0] + r->calc_hash() * 31;
		return hash;
	}
};

map<string,expr*> var;

void inc_var_name (string & cur) {
	for (size_t i=cur.length()-1; ; --i)
		if (cur[i] < 'z') {
			++cur[i];
			break;
		}
		else
			cur[i] = 'a';
}

string generate_var() {
	static string cur = "aaaa";
	while (var.count(cur))
		inc_var_name (cur);
	string res = cur;
	inc_var_name (cur);
	return res;
}

vector<string> ans;
map<long long,string> calced;

string restore (expr * e, string name = "") {
	if (!e->l)  return e->t;
	long long h = e->calc_hash();
	if (calced.count(h))  return calced[h];
	string l = restore (e->l),  r = restore (e->r);
	string my = name.empty() ? generate_var() : name;
	calced[h] = my;
	ans.push_back (my + "=" + l + e->t + r);
	return my;
}

int main() {
	int n;
	scanf ("%d\n", &n);
	for (int i=0; i<n; ++i) {
		static char buf[100];
		gets (buf);
		string s = buf;

		size_t pos1 = s.find ('='),  pos2 = s.find_first_of ("&^$#");
		string lname = s.substr (0, pos1);
		string r1name = s.substr (pos1 + 1, pos2 - pos1 - 1);
		if (!var.count(r1name))
			var[r1name] = new expr (r1name);
		if (pos2 != -1) {
			string r2name = s.substr (pos2 + 1);
			if (!var.count(r2name))
				var[r2name] = new expr (r2name);
			var[lname] = new expr (s [ s.find_first_of ("&^$#") ], var[r1name], var[r2name]);
		}
		else
			var[lname] = var[r1name];
	}

	if (!var.count("res")) {
		cout << 0;
		return 0;
	}

	string name = restore (var["res"], "res");
	if (name != "res")
		ans.push_back ("res=" + name);

	cout << ans.size() << endl;
	for (size_t i=0; i<ans.size(); ++i)
		puts (ans[i].c_str());

}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	
	for (int i = 1; i < int(s.size()); ++i) {
		if (s[i] < s[i - 1]) {
			cout << "YES" << endl;
			cout << i << " " << i + 1 << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    cin >> n >> s;
    int cnt1 = (n - 11) / 2;
    int cnt2 = cnt1;
    string res = "";
    for(int i = 0; i < n; ++i){
        if(s[i] == '8'){
            if(cnt1 > 0) --cnt1;
            else res += s[i];
        }
        else{
            if(cnt2 > 0) --cnt2;
            else res += s[i];
        }
    }
    
    if(res[0] == '8') cout << "YES\n";
    else cout << "NO\n";
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<long long> x(n), p(m);
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> p[i];
	}
	
	long long g = x[1] - x[0];
	for (int i = 2; i < n; ++i) {
		g = __gcd(g, x[i] - x[i - 1]);
	}
	
	for (int i = 0; i < m; ++i) {
		if (g % p[i] == 0) {
			cout << "YES" << endl;
			cout << x[0] << " " << i + 1 << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

typedef long long li;

const int N = 300 * 1000 + 13;
const li INF64 = 1e18;

int n, x;
int a[N];

li dp[N][3][3];

int main() {
	scanf("%d%d", &n, &x);
	forn(i, n) scanf("%d", &a[i]);
	
	forn(i, n + 1) forn(j, 3) forn(k, 3)
		dp[i][j][k] = -INF64;
	
	dp[0][0][0] = 0;
	forn(i, n + 1) forn(j, 3) forn(k, 3){
		if (k < 2)
			dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]);
		if (j < 2)
			dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
		if (i < n)
			dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1));
	}
	
	printf("%lld\n", dp[n][2][2]);
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int MOD = 1000 * 1000 + 3;

int norm(int a) {
	while(a >= MOD) a -= MOD;
	while(a < 0) a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}
int inv(int a) {
	return binPow(a, MOD - 2);
}

int k = 10;
vector<int> f;

int main() {
	f.resize(k + 1);
	fore(i, 0, sz(f)) {
		cout << "? " << i << endl;
		cout.flush();
		cin >> f[i];
	}
	
	vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1));
	fore(i, 0, sz(mat)) {
		mat[i][0] = 1;
		mat[i][sz(f)] = f[i];
		
		fore(j, 1, sz(mat[i]) - 1)
			mat[i][j] = mul(mat[i][j - 1], i);
	}
	
	/*
	fore(i, 0, sz(mat)) {
		fore(j, 0, sz(mat[i]))
			cerr << mat[i][j] << " ";
		cerr << endl;
	}
	*/
	
	fore(j, 0, sz(mat)) {
		int nid = -1;
		fore(i, j, sz(mat)) {
			if(mat[i][j] != 0) {
				nid = i;
				break;
			}
		}
		if(nid == -1)
			continue;
		
		swap(mat[j], mat[nid]);
		fore(i, 0, sz(mat)) {
			if(i == j) continue;
			int cf = mul(mat[i][j], inv(mat[j][j]));
			
			fore(cj, j, sz(mat[i]))
				mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj]));
		}
	}
	
	vector<int> a(sz(f), 0);
	fore(i, 0, sz(a)) {
		if(mat[i][i] == 0)
			continue;
		a[i] = mul(mat[i][sz(a)], inv(mat[i][i]));
	}
	
	fore(x0, 0, MOD) {
		int val = 0;
		for(int i = sz(a) - 1; i >= 0; i--)
			val = norm(mul(val, x0) + a[i]);
			
		if(val == 0) {
			cout << "! " << x0 << endl;
			return 0;
		}
	}
	
	cout << "! -1" << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 14;
const int INF = int(1e9);

int dp[1 << N];
int par[1 << N];
int last[1 << N];
pair<int, int> last_pair[1 << N];
int dp2[N][N][1 << N];
int lastv[N][N][1 << N];
vector<int> bits[1 << N];

int n;
int m;
vector<int> g[N];

int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i = 0; i < (1 << n); i++)
		dp[i] = INF;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int z = 0; z < (1 << n); z++)
				dp2[i][j][z] = INF;
	for(int i = 0; i < n; i++)
		for(auto x : g[i])
		{
			dp2[i][x][0] = 1;
			lastv[i][x][0] = i;
		}
	for(int mask = 0; mask < (1 << n); mask++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
			{
				if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF))
					continue;
				for(auto z : g[j])
				{
					if(mask & (1 << z)) continue;
					if(z == lastv[i][j][mask]) continue;
					int nmask = mask ^ (1 << j);
					if(dp2[i][z][nmask] == INF)
					{
						dp2[i][z][nmask] = 1;
						lastv[i][z][nmask] = j;
					}
				}
			}
	for(int mask = 0; mask < (1 << n); mask++)
		for(int j = 0; j < n; j++)
			if(mask & (1 << j))
				bits[mask].push_back(j);
	dp[1] = 0;
	for(int mask = 0; mask < (1 << n); mask++)
		for(int addmask = mask; addmask; addmask = (addmask - 1) & mask)
		{
			int lastmask = mask ^ addmask;
			int cnt = __builtin_popcount(addmask) + 1;
			if(dp[lastmask] + cnt >= dp[mask])
				continue;
			bool f = false;
			for(auto x : bits[lastmask])
			{
				for(auto y : bits[lastmask])
				{
					if(dp2[x][y][addmask] == 1)
					{
						dp[mask] = dp[lastmask] + cnt;
						last_pair[mask] = make_pair(x, y);
						last[mask] = addmask;
					}
					if(f) break;
				}
				if(f) break;
			}
		}
	if(dp[(1 << n) - 1] == INF)
		cout << -1 << endl;
	else
	{
		cout << dp[(1 << n) - 1] << endl;
		int cur = (1 << n) - 1;
		while(cur != 1)
		{
			int lst = last[cur];
			int x = last_pair[cur].first;
			int y = last_pair[cur].second;
			cur ^= lst;
			while(lst)
			{
				int ny = lastv[x][y][lst];
				cout << y + 1 << " " << ny + 1 << endl;
				lst ^= (1 << ny);
				y = ny;
			}
			cout << x + 1 << " " << y + 1 << endl;
		}
	}
}

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> a;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}
	return true;
}

inline void solve() {
	int cnt = 0, pos = 0;
	while(pos < n) {
		cnt++;
		int mx = pos;
		while(pos < n && pos <= mx) {
			mx = max(mx, a[pos]);
			pos++;
		}
	}
	cout << cnt << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif	
	if(read()) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t, n;
string s;

int main(){
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> n >> s;
		int res = n - 1;
		for(int i = 0; i < n; ++i)
			if(s[i] == '>' || s[n - 1 - i] == '<')
				res = min(res, i);
		
		cout << res << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

int n, k;
pair<int, int> a[N];

int main() {
	cin >> n >> k;
	
	for(int i = 0; i < n; ++i)
		cin >> a[i].second >> a[i].first;

	sort(a, a + n);
	long long res = 0;
	long long sum = 0;
	set<pair<int, int> > s;
	for(int i = n - 1; i >= 0; --i){
		s.insert(make_pair(a[i].second, i));
		sum += a[i].second;
		while(s.size() > k){
			auto it = s.begin();
			sum -= it->first;
			s.erase(it);
		}

		res = max(res, sum * a[i].first);
	}

	cout << res << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n; cin >> n;

	long long ans = 0;
	for(int id = 2; id < n; id++)
		ans += 1ll * id * (id + 1);
	
	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = 998244353;
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}

int n, k;
vector<int> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

pair<int, int> calc(int len) {
    if(len == 0) return {0, 1};
    if(len & 1) {
        auto res = calc(len >> 1);
        return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
                norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    }
    auto res = calc(len - 1);
    return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}

vector<int> curArray;

int calcSeg(int l, int r) {
    if(r >= sz(curArray)) {
        int len = r - l - 1, cf = 1;
        if(l < 0)
            len--, cf = k;
        if(len == 0) return cf;

        auto res = calc(len - 1);
        return mul(cf, norm(res.x + mul(k - 1, res.y)));
    }
    if(l < 0) {
        if(r - l == 1) return 1;
        auto res = calc(r - l - 2);
        return norm(res.x + mul(k - 1, res.y));
    }
    auto res = calc(r - l - 1);
    return curArray[l] == curArray[r] ? res.x : res.y;
}

inline void solve() {
    int ans = 1;
    fore(k, 0, 2) {
        curArray.clear();
        for(int i = 0; 2 * i + k < n; i++)
            curArray.push_back(a[2 * i + k]);

        int lst = -1;
        fore(i, 0, sz(curArray)){
            if(curArray[i] == -1) continue;
            ans = mul(ans, calcSeg(lst, i));
            lst = i;
        }
        ans = mul(ans, calcSeg(lst, sz(curArray)));
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

#define x first
#define y second

const int N = 300043;
const int K = 300000;

int p[2 * N];
int s1[2 * N];
int s2[2 * N];
li ans = 0;

int* where[80 * N];
int val[80 * N];
int cur = 0;

void change(int& x, int y)
{
	where[cur] = &x;
	val[cur] = x;
	x = y;
	cur++;
}

void rollback()
{
	cur--;
	(*where[cur]) = val[cur];
}

int get(int x)
{
	if(p[x] == x)
		return x;
	return get(p[x]);
}

void merge(int x, int y)
{
	x = get(x);
	y = get(y);
	if(x == y) return;
	ans -= s1[x] * 1ll * s2[x];
	ans -= s1[y] * 1ll * s2[y];
	if(s1[x] + s2[x] < s1[y] + s2[y])
		swap(x, y);
	change(p[y], x);
	change(s1[x], s1[x] + s1[y]);
	change(s2[x], s2[x] + s2[y]);
	ans += s1[x] * 1ll * s2[x];
}

void init()
{
	for(int i = 0; i < K; i++)
	{
		p[i] = i;
		p[i + K] = i + K;
		s1[i] = 1;
		s2[i + K] = 1;
	}
}

vector<pair<int, int> > T[4 * N];

void add(int v, int l, int r, int L, int R, pair<int, int> val)
{
	if(L >= R) return;
	if(L == l && R == r)
		T[v].push_back(val);
	else
	{
		int m = (l + r) / 2;
		add(v * 2 + 1, l, m, L, min(R, m), val);
		add(v * 2 + 2, m, r, max(m, L), R, val);
	}
}

li res[N];

void dfs(int v, int l, int r)
{
	li last_ans = ans;
	int state = cur;
	for(auto x : T[v])
		merge(x.x, x.y + K);
	if(l == r - 1)
		res[l] = ans;
	else
	{
		int m = (l + r) / 2;
		dfs(v * 2 + 1, l, m);
		dfs(v * 2 + 2, m, r);
	}
	while(cur != state) rollback();
	ans = last_ans;
}

int main()
{
	int q;
	scanf("%d", &q);
	map<pair<int, int>, int> last;
	for(int i = 0; i < q; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		pair<int, int> p = make_pair(x, y);
		if(last.count(p))
		{
			add(0, 0, q, last[p], i, p);
			last.erase(p);
		}
		else
			last[p] = i;
	}
	for(auto x : last)
		add(0, 0, q, x.y, q, x.x);
	init();
	dfs(0, 0, q);
	for(int i = 0; i < q; i++)
		printf("%I64d ", res[i]);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

#define x first
#define y second

const int N = 600043;

li d1[N];
li d2[N][2];
li dist_temp[N][2];
vector<pair<int, int> > g[N];
vector<int> qs[N];
int qq[N][2];
li ans[N];
int n;
int used[N];
int cnt[N];
int last[N];
int cc = 1;

void preprocess()
{
	set<pair<li, int> > q;
	for(int i = 0; i < n; i++)
		q.insert(make_pair(d1[i], i));
	while(!q.empty())
	{
		int k = q.begin()->second;
		q.erase(q.begin());
		for(auto e : g[k])
		{
			int to = e.first;
			li w = d2[e.second][0] + d2[e.second][1];
			if(d1[to] > w + d1[k])
			{
				q.erase(make_pair(d1[to], to));
				d1[to] = w + d1[k];
				q.insert(make_pair(d1[to], to));
			}
		}
	}
}

void dfs1(int x, int p = -1)
{
	if(used[x]) return;
	cnt[x] = 1;
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
		{
			dfs1(to, x);
			cnt[x] += cnt[to];
		}
	}
}

vector<int> cur_queries;
pair<int, int> c;
int S = 0;

void find_centroid(int x, int p = -1)
{
	if(used[x])	return;
	int mx = 0;
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
		{
			find_centroid(to, x);
			mx = max(mx, cnt[to]);
		}
	}
	if(p != -1)
		mx = max(mx, S - cnt[x]);
	c = min(c, make_pair(mx, x));
}	

void dfs2(int x, int p = -1, int e = -1)
{
	if(used[x]) return;
	if(p == -1)
	{
		dist_temp[x * 2][0] = dist_temp[x * 2 + 1][1] = 0ll;
		dist_temp[x * 2][1] = dist_temp[x * 2 + 1][0] = d1[x];
	}
	else
	{
		for(int k = 0; k < 2; k++)
		{
			li& D0 = dist_temp[x * 2][k];
			li& D1 = dist_temp[x * 2 + 1][k];
			D0 = dist_temp[p * 2][k] + d2[e][0];
			D1 = dist_temp[p * 2 + 1][k] + d2[e][1];
			D0 = min(D0, D1 + d1[x]);
			D1 = min(D1, D0 + d1[x]); 
		}
	}
	for(auto y : qs[x])
	{
		if(ans[y] != -1) continue;
		if(last[y] == cc)
			cur_queries.push_back(y);
		else
			last[y] = cc;
	}
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
			dfs2(to, x, y.second);
	}
}

void centroid(int v)
{
	if(used[v]) return;
	dfs1(v);
	S = cnt[v];
	c = make_pair(int(1e9), -1);
	find_centroid(v);
	int C = c.second;
	used[C] = 1;
	for(auto y : g[C])
		centroid(y.first);
	cc++;
	cur_queries.clear();
	used[C] = 0;
	dfs2(C);
	for(auto x : cur_queries)
	{
		int u = qq[x][0];
		int v = qq[x][1];
		ans[x] = min(dist_temp[u][0] + dist_temp[v][0], dist_temp[u][1] + dist_temp[v][1]);
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%I64d", &d1[i]);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		li w1, w2;
		scanf("%d %d %I64d %I64d", &x, &y, &w1, &w2);
		--x;
		--y;
		d2[i][0] = w1;
		d2[i][1] = w2;
		g[x].push_back(make_pair(y, i));
		g[y].push_back(make_pair(x, i));
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		scanf("%d", &qq[i][0]);
		scanf("%d", &qq[i][1]);
		--qq[i][0];
		--qq[i][1];
		qs[qq[i][0] / 2].push_back(i);
		qs[qq[i][1] / 2].push_back(i);
	}
	preprocess();
	for(int i = 0; i < q; i++)
		ans[i] = -1;
	centroid(0);
	for(int i = 0; i < q; i++)
		cout << ans[i] << endl;
}

cnt = []

for i in range(4):
	cnt.append(int(input()))
	
if(cnt[0] == cnt[3] and (cnt[2] == 0 or cnt[0] > 0)):
	print(1)
else:
	print(0)

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

int n;
int a[N];
long long res[N];

int main() {
	long long sum = 0;
	scanf("%d", &n);	
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		sum += a[i];	
	}
	sort(a, a + n);
	
	memset(res, -1, sizeof res);
	int m;
	scanf("%d", &m);
	for(int i = 0; i < m; ++i){
		int c;
		scanf("%d", &c);
		if(res[c] == -1){
			res[c] = sum - a[n - c];
		}	

		printf("%lld\n", res[c]);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 5043;

int p1[N];
int p2[N];
int p3[N];
int n, q;
int l[N], r[N];

int solve(int idx)
{
	memset(p1, 0, sizeof p1);
	for(int i = 0; i < q; i++)
	{
		if(i == idx) continue;
		p1[l[i]]++;
		p1[r[i]]--;
	}
	memset(p2, 0, sizeof p2);
	int c = 0;
	for(int i = 0; i < n; i++)
	{
		c += p1[i];
		p2[i] = c;
	}	
	memset(p3, 0, sizeof p3);
	for(int i = 0; i < n; i++)
		p3[i + 1] = p3[i] + (p2[i] == 1 ? 1 : 0);
	int ans = -int(1e9);
	for(int i = 0; i < q; i++)
	{
		if(i == idx) continue;
		ans = max(ans, p3[l[i]] - p3[r[i]]);
	}
	for(int i = 0; i < n; i++)
		if(p2[i] > 0)
			ans++;
	return ans;
}

int main()
{
	cin >> n >> q;
	for(int i = 0; i < q; i++)
	{
		cin >> l[i] >> r[i];
		l[i]--;
	}
	int ans = 0;
	for(int i = 0; i < q; i++)
		ans = max(ans, solve(i));
	cout << ans << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const long long INF64 = 1e18;

int n, k;
long long a[N];
int b[N];
long long cur[N];

vector<int> qr[N];

bool check(long long x){
	forn(i, k) qr[i].clear();
	forn(i, n) cur[i] = a[i];
	forn(i, n){
		long long t = cur[i] / b[i] + 1;
		cur[i] %= b[i];
		if (t < k) qr[t].push_back(i);
	}
	
	int lst = 0;
	forn(t, k){
		while (lst < k && qr[lst].empty())
			++lst;
		if (lst <= t)
			return false;
		if (lst == k)
			return true;
		int i = qr[lst].back();
		if (cur[i] + x < b[i]){
			cur[i] += x;
			continue;
		}
		qr[lst].pop_back();
		long long nt = (cur[i] + x) / b[i];
		cur[i] = (cur[i] + x) % b[i];
		if (lst + nt < k)
			qr[lst + nt].push_back(i);
	}
	
	return true;
}

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%lld", &a[i]);
	forn(i, n) scanf("%d", &b[i]);
	long long l = 0, r = INF64;
	while (l < r - 1){
		long long m = (l + r) / 2;
		if (check(m))
			r = m;
		else
			l = m;
	}
	if (!check(r))
		puts("-1");
	else
		printf("%lld\n", check(l) ? l : r);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 9;
const int L = 840;

typedef long long li;

li dp[N][L * N];
li W;
li cnt[N];

int main()
{
	cin >> W;
	for(int i = 0; i < 8; i++)
		cin >> cnt[i];
	for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
	dp[0][0] = 0;
	for(int i = 0; i < 8; i++)
	{
		for(int j = 0; j < L * N; j++)
		{
			if(dp[i][j] == -1) continue;
			int b = L / (i + 1);
			if(cnt[i] < b)
				b = cnt[i];
			for(int k = 0; k <= b; k++)
			{
				li& d = dp[i + 1][j + k * (i + 1)];
				d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
			}
		}
	}
	li ans = 0;
	for(int j = 0; j < L * N; j++)
	{
		if(j > W || dp[8][j] == -1)
			continue;
		ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
	}
	cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int n;
string s;
int dp[N][N];

int calc(int l, int r){	
	int &res = dp[l][r];
	if(res != -1) return res;
	
	if(l > r) return res = 0;
	if(l == r) return res = 1;
    
	res = 1 + calc(l + 1, r);
	for(int i = l + 1; i <= r; ++ i)
		if(s[l] == s[i])
			res = min(res, calc(l + 1, i - 1) + calc(i, r));
	return res;
}

int main(){
	cin >> n >> s;
	memset(dp, -1, sizeof dp);
	cout << calc(0, n - 1);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

int n, k;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	a.assign(n, 0);
	fore(i, 0, n)
		cin >> a[i];
	return true;
}

int T = 0;
vector< vector<int> > g;
vector<int> tin, tout;

void dfs(int v) {
	tin[v] = T++;
	for(int to : g[v])
		dfs(to);
	tout[v] = T;
}

vector<int> Tmax, Tadd;

inline void push(int v) {
	Tadd[2 * v + 1] += Tadd[v];
	Tadd[2 * v + 2] += Tadd[v];
	Tadd[v] = 0;
}
inline int getmax(int v) {
	return Tmax[v] + Tadd[v];
}

void addVal(int v, int l, int r, int lf, int rg, int val) {
	if(l == lf && r == rg) {
		Tadd[v] += val;
		return;
	}
	int mid = (l + r) >> 1;
	push(v);
	if(lf < mid) addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if(rg > mid) addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
	Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
}

inline void solve() {
	g.resize(n + 1);
	tin.resize(n + 1, 0);
	tout.resize(n + 1, 0);
	vector<int> st;
	for(int i = n - 1; i >= 0; i--) {
		while(!st.empty() && a[st.back()] <= a[i])
			st.pop_back();
		int nxt = st.empty() ? n : st.back();
		g[nxt].push_back(i);
		st.push_back(i);
	}
	dfs(n);
	Tmax.assign(4 * (n + 1), 0);
	Tadd.assign(4 * (n + 1), 0);
	
	fore(i, 0, k - 1)
		addVal(0, 0, n + 1, tin[i], tout[i], +1);
	
	for(int l = 0; l + k <= n; l++) {
		addVal(0, 0, n + 1, tin[l + k - 1], tout[l + k - 1], +1);
		cout << getmax(0) << " ";
		addVal(0, 0, n + 1, tin[l], tout[l], -1);
	}
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<iostream>
using namespace std;

int main() {
	int n; cin >> n;
	int mx = -1, lenMx = 0;
	
	int curEl = -1, curLen = 0;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		
		if(curEl != a)
			curEl = a, curLen = 0;
		curLen++;
		
		if(mx < curEl)
			mx = curEl, lenMx = 0;
		if(mx == curEl)
			lenMx = max(lenMx, curLen);
	}
	cout << lenMx << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	cin >> n >> m >> k;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	cout << m / (k + 1) * 1ll * (a[0] * 1ll * k + a[1]) + m % (k + 1) * 1ll * a[0] << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 100009;

pair<int, int> st, fi;
int n;
string s;

string mv = "UDLR";
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

pair<int, int> d[N];

int main(){
	cin >> st.x >> st.y >> fi.x >> fi.y;
	cin >> n >> s;		

	for(int i = 0; i < n; ++i){
		int id = -1;
		for(int j = 0; j < 4; ++j)
			if(mv[j] == s[i])
				id = j;
		assert(id != -1);
		d[i + 1] = make_pair(d[i].x + dx[id], d[i].y + dy[id]);
	}

	long long l = 0, r = 1e18;
	while(r - l > 1){
		long long mid = (l + r) / 2;
		long long cnt = mid / n, rem = mid % n;
		long long x = st.x + d[rem].x + cnt *  1LL * d[n].x;
		long long y = st.y + d[rem].y + cnt *  1LL * d[n].y;
		long long dist = abs(x - fi.x) + abs(y - fi.y);
		if(dist <= mid)
			r = mid;
		else
			l = mid;	
	} 

	if(r > 5e17) r = -1;
	cout << r << endl;

	return 0;
}

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define bolt ios::sync_with_stdio(0)
#define light cin.tie(0);cout.tie(0)
#define forr(i,p,n) for(ll i=p;i<n;i++)
#define MAXN 1000003
typedef long long ll;
using namespace std;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}

ll bin[103][103];

void mult_mat(ll m, ll ans[][100], ll bin[][100]){
    ll mult[m][m];
    forr(i,0,m){
        forr(j,0,m){
            mult[i][j]=0;
            forr(k,0,m){
                mult[i][j]+=ans[i][k]*bin[k][j];
                if(mult[i][j]>=MOD){
                    mult[i][j]%=MOD;
                }
            }
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=mult[i][j];
        }
    }
}

void pow_mat(ll n, ll fin[][100], ll m){
    ll ans[m][100];
    ll b[m][100];
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=bin[i][j];
            b[i][j]=bin[i][j];
        }
    }
    n--;
    while(n>0){
        if(n%2==1){
            mult_mat(m,ans,b);
            n--;
        }else{
            n=n/2;
            mult_mat(m,b,b);
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            fin[i][j]=ans[i][j];
        }
    }
}

int main(){
    bolt;
    ll n,m;
    cin>>n>>m;
    bin[0][0]=1;
    bin[0][m-1]=1;
    for(ll i=1;i<m;i++){
        bin[i][i-1]=1;
    }
    if(n<m){
        cout<<1<<"\n";
    }else{
        ll fin[m+1][100];
        pow_mat(n-m+1,fin,m);
        ll ans=0;
        forr(i,0,m){
            ans+=fin[0][i];
            if(ans>=MOD){
                ans-=MOD;
            }
        }
        cout<<ans<<"\n";
    }
}

#include <bits/stdc++.h>

using namespace std;

int main()
{
	string t;
	cin >> t;
	int n = t.size();
	string s1(n, 'a'), s2(n, 'a'), s3(n, 'a');
	for(int i = 0; i < n; i++)
	{
		s1[i] = char('a' + (i % 26));
		s2[i] = char('a' + ((i / 26) % 26));
		s3[i] = char('a' + ((i / 26 / 26) % 26));
	}
	cout << "? " << s1 << endl;
	string t1;
	cin >> t1;
	cout << "? " << s2 << endl;
	string t2;
	cin >> t2;
	cout << "? " << s3 << endl;
	string t3;
	cin >> t3;
	vector<int> p(n);
	for(int i = 0; i < n; i++)
		p[i] = (t1[i] - 'a') + (t2[i] - 'a') * 26 + (t3[i] - 'a') * 26 * 26;
	string s(n, 'a');
	for(int i = 0; i < n; i++)
		s[p[i]] = t[i];
	cout << "! " << s << endl;
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 100 * 1000 + 13;
const int P = 17;

int n, p;
string s;
int A[P][P];
vector<int> pos[P];
int pr[P][N];
bitset<(1 << P)> legal, cur, dp;
int cnt[P];

int main() {
	scanf("%d%d", &n, &p);
	char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, p) forn(j, p)
		scanf("%d", &A[i][j]);
	
	forn(i, n){
		pos[s[i] - 'a'].push_back(i);
		forn(j, p)
			pr[j][i + 1] = pr[j][i] + (s[i] == 'a' + j);
	}
	
	legal.reset();
	legal.flip();
	
	int fl = (1 << p) - 1;
	forn(c, p) forn(d, c + 1){
		if (A[c][d]) continue;
		cur.reset();
		cur.flip();
		int i = 0, j = 0;
		while (i < pos[c].size() && j < pos[d].size()){
			if (c == d && i == j){
				++j;
				continue;
			}
			int mask = 0;
			if (pos[c][i] < pos[d][j]){
				forn(e, p) if ((pr[e][pos[d][j]] - pr[e][pos[c][i] + 1]) != 0)
					mask |= (1 << e);
				++i;
			}
			else{
				forn(e, p) if ((pr[e][pos[c][i]] - pr[e][pos[d][j] + 1]) != 0)
					mask |= (1 << e);
				++j;
			}
			if ((mask >> c) & 1) continue;
			if ((mask >> d) & 1) continue;
			cur[mask ^ fl] = 0;
		}
		for (int mask = fl; mask > 0; --mask){
			if (cur[mask]) continue;
			forn(e, p) if (c != e && d != e && ((mask >> e) & 1))
				cur[mask ^ (1 << e)] = 0;
		}
		legal &= cur;
	}
	
	dp[fl] = 1;
	for (int mask = fl; mask > 0; --mask){
		if (!dp[mask]) continue;
		forn(i, p) if ((mask >> i) & 1){
			int nmask = mask ^ (1 << i);
			if (dp[nmask]) continue;
			dp[nmask] = legal[nmask];
		}
	}
	
	forn(i, n)
		++cnt[s[i] - 'a'];
	
	int ans = n;
	forn(mask, 1 << p) if (dp[mask]){
		int cur = 0;
		forn(i, p) if ((mask >> i) & 1)
			cur += cnt[i];
		ans = min(ans, cur);
	}
	
	printf("%d\n", ans);
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

int n, q;
vector<int> a;
vector< pair<pt, int> > qs;

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	a.resize(n);
	qs.resize(q);
	
	fore(i, 0, n)
		cin >> a[i];
	fore(i, 0, q) {
		cin >> qs[i].x.x;
		qs[i].x.x--;
	}
	fore(i, 0, q) {
		cin >> qs[i].x.y;
		qs[i].x.y--;
		qs[i].y = i;
	}
	return true;
}

bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
	if(a.x.y != b.x.y)
		return a.x.y < b.x.y;
	if(a.x.x != b.x.x)
		return a.x.x < b.x.x;
	return a.y < b.y;
}

typedef pair<li, li> func;
func operator +=(func &a, const func &b) {
	a.x += b.x, a.y += b.y;
	return a;
}

vector<func> t;
void add(int l, int r, const func &f) {
	for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if(l & 1) t[l++] += f;
		if(r & 1) t[--r] += f;
	}
}
func sum(int pos) {
	func ans(0, 0);
	for(pos += n; pos > 0; pos >>= 1)
		ans += t[pos];
	return ans;
}

inline void solve() {
	vector<li> ans(q, 0);
	fore(i, 0, q)
		ans[i] = qs[i].x.y - qs[i].x.x + 1;
	fore(_, 0, 2) {
		vector<int> st;
		vector<int> lf(n, -1);
		fore(i, 0, n) {
			while(!st.empty() && a[st.back()] < a[i])
				st.pop_back();
			if(!st.empty())
				lf[i] = st.back();
			st.push_back(i);
		}
		
		sort(qs.begin(), qs.end(), cmp);
		t.assign(2 * n, {0, 0});
		
		int uk = 0;
		fore(i, 0, n) {
			add(0, lf[i] + 1, {0, i - lf[i] - 1});
			add(lf[i] + 1, i, {-1, i});
			
			while(uk < q && qs[uk].x.y == i) {
				auto f = sum(qs[uk].x.x);
				ans[qs[uk].y] += f.x * qs[uk].x.x + f.y;
				uk++;
			}
		}
		
		reverse(a.begin(), a.end());
		for(auto &p : qs) {
			p.x.x = n - 1 - p.x.x;
			p.x.y = n - 1 - p.x.y;
			swap(p.x.x, p.x.y);
		}
	}
	for(auto v : ans)
		cout << v << ' ';
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		string s;
		cin >> n >> s;
		if (n == 2 && s[0] >= s[1]) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl << 2 << endl << s[0] << " " << s.substr(1) << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		long long k, x;
		cin >> k >> x;
		cout << (k - 1) * 9 + x << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	string s;
	cin >> s;
	
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int j = i;
		vector<int> vals;
		while (j < n && s[i] == s[j]) {
			vals.push_back(a[j]);
			++j;
		}
		sort(vals.rbegin(), vals.rend());
		ans += accumulate(vals.begin(), vals.begin() + min(k, int(vals.size())), 0ll);
		i = j - 1;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 5200;

int n;
bool a[N][N];

void parse_char(int x, int y, char c) {
	int num = -1;
	if (isdigit(c)) {
		num = c - '0';
	} else {
		num = c - 'A' + 10;
	}
	for (int i = 0; i < 4; ++i) {
		a[x][y + 3 - i] = num & 1;
		num >>= 1;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	
	scanf("%d", &n);
	char buf[N];
	for (int i = 0; i < n; ++i) {
		scanf("%s", buf);
		for (int j = 0; j < n / 4; ++j) {
			parse_char(i, j * 4, buf[j]);
		}
	}
	
	int g = n;
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int k = j;
			while (k < n && a[i][k] == a[i][j]) ++k;
			g = __gcd(g, k - j);
			j = k - 1;
		}
	}
	
	for (int j = 0; j < n; ++j) {
		for (int i = 0; i < n; ++i) {
			int k = i;
			while (k < n && a[k][j] == a[i][j]) ++k;
			g = __gcd(g, k - i);
			i = k - 1;
		}
	}
	
	cout << g << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 102;
const long long INF = 1e12;

int n;
string s;
int a[N];

long long ans[N][N];
long long dp[2][N][N][N];

long long calcDp(int c, int l, int r, int cnt);

long long calcAns(int l, int r){
	if(l >= r) return 0;
	long long &res = ans[l][r];
	if(res != -1) return res;

	res = 0;
	for(int cnt = 1; cnt <= r - l; ++cnt){
		res = max(res, calcDp(0, l, r, cnt) + a[cnt - 1]);
		res = max(res, calcDp(1, l, r, cnt) + a[cnt - 1]);
	}

	return res;
}

long long calcDp(int c, int l, int r, int cnt){
	if(cnt == 0) return calcAns(l, r);
	long long &res = dp[c][l][r][cnt];
	if(res != -1) return res;
	
	res = -INF;

	for(int i = l; i < r; ++i){
		if(c == s[i] - '0')
			res = max(res, calcAns(l, i) + calcDp(c, i + 1, r, cnt - 1));
	}

	return res;
}

int main(){
	cin >> n >> s;
	for(int i = 0; i < n; ++i)
		cin >> a[i];

	
	memset(dp, -1, sizeof dp);
	memset(ans, -1, sizeof ans);

	cout << calcAns(0, n) << endl;	

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const long long INF = 1e18;

int n;
long long a[N][N];
int up[N], down[N], k[N];
long long u[N], v[N];
int p[N], way[N];

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i)
		cin >> up[i] >> down[i] >> k[i];
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			a[i + 1][j + 1] = -(up[j] - min(i, k[j]) * 1LL * down[j]);

	long long res = 0;
	for(int i = 1; i <= n; ++i){
		p[0] = i;
		int j0 = 0;
		vector<long long> minv (n + 1, INF);
		vector<char> used (n + 1, false);
		do{
			used[j0] = true;
			int i0 = p[j0],   j1;
			long long delta = INF;
			for (int j = 1; j <= n; ++j)
				if (!used[j]){
					long long cur = a[i0][j] - u[i0] - v[j];
					if (cur < minv[j])
						minv[j] = cur,  way[j] = j0;
					if (minv[j] < delta)
						delta = minv[j],  j1 = j;
				}
			for (int j = 0; j <= n; ++j)
				if (used[j])
					u[p[j]] += delta,  v[j] -= delta;
				else
					minv[j] -= delta;
			j0 = j1;
		}while (p[j0] != 0);
		do {
			int j1 = way[j0];
			p[j0] = p[j1];
			j0 = j1;
		} while (j0);

		res = max(res, v[0]);
	}

	cout << res << endl;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

struct node{
	long long sum, ans, pref, suf;
	
	node () {}
	node(int x){
		sum = x;
		x = max(x, 0);
		pref = suf = ans = x;
	}
};

node merge(const node &a, const node &b){
	node res;
	res.sum = a.sum + b.sum;
	res.pref = max(a.pref, a.sum + b.pref);
	res.suf = max(b.suf, b.sum + a.suf);
	res.ans = max(max(a.ans, b.ans), a.suf + b.pref);
	return res;
}

int n, x;
pair<int, int> p[N];
node t[N * 4];

void upd(int v, int l, int r, int pos, int x){
	if(r - l == 1){
		assert(pos == l);
		t[v] = node(x);
		return;
	}
	
	int mid = (l + r) / 2;
	if(pos < mid) upd(v * 2 + 1, l, mid, pos, x);
	else upd(v * 2 + 2, mid, r, pos, x);
	
	t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}

node get(int v, int l, int r, int L, int R){
	if(L >= R) return node(0);
	
	if(l == L && r == R)
		return t[v];
	
	int mid = (l + r)/ 2;
	return merge(get(v * 2 + 1, l, mid, L, min(mid, R)),
				 get(v * 2 + 2, mid, r, max(L, mid), R));	
}

int main() {
	scanf("%d %d", &n, &x);
	for(int i = 0; i < n; ++i){
		scanf("%d %d", &p[i].first, &p[i].second);
		p[i].second = x - p[i].second;
	}
	
	sort(p, p + n);
	for(int i = 0; i < n; ++i) upd(0, 0, n, i, p[i].second);
	
	vector <pair<int, int> > v;
	for(int i = 1; i < n; ++i)
		v.emplace_back(p[i].first - p[i - 1].first, i);
	sort(v.begin(), v.end());
	
	long long res = 0;
	set <pair<int, int> > s;
	for(int i = 0; i < n; ++i){
		s.insert(make_pair(i, i + 1));
		res = max(res, 1LL * p[i].second);
	}
	
	int l = 0;
	while(l < v.size()){
		int r = l + 1;
		while(r < v.size() && v[l].first == v[r].first) ++r;
		long long d = v[l].first * 1LL * v[l].first;
		
		for(int i = l; i < r; ++i){
			int id = v[i].second;
			auto it = s.upper_bound(make_pair(id, -1));
			assert(it->first == id);
			assert(it != s.begin());
			auto R = *it;
			--it;
			auto L = *it;
			s.erase(L), s.erase(R);
			L.second = R.second;
			
			auto nd = get(0, 0, n, L.first, L.second);
			res = max(res, nd.ans - d);
			s.insert(L);
		}
		
		l = r;
	}
	
	cout << res << endl;
	return 0;
}

q = int(input())
for i in range(q):
    l, r, d = map(int, input().split())
    if(d < l or d > r):
        print(d)
    else:
        print((r // d) * d + d)

#include <bits/stdc++.h>

using namespace std;

void rem(string &s, const string &c) {
	auto pos = s.find(c);
	if (pos == string::npos) {
		cout << -1 << endl;
		exit(0);
	}
	s.erase(0, pos + 1);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> s;
	
	rem(s, "[");
	rem(s, ":");
	reverse(s.begin(), s.end());
	rem(s, "]");
	rem(s, ":");
	
	cout << count(s.begin(), s.end(), '|') + 4 << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int, int> pt;

int n;
vector< pair<pt, int> > segs;

inline bool read() {
	if(!(cin >> n))
		return false;
	segs.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> segs[i].x.x >> segs[i].x.y;
		segs[i].y = i;
	}
	return true;
}

bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
	if(a.x.y != b.x.y)
		return a.x.y < b.x.y;
	if(a.x.x != b.x.x)
		return a.x.x < b.x.x;
	return a.y < b.y;
}

inline void solve() {
	sort(segs.begin(), segs.end(), cmp);
	
	int mn = segs[n - 1].x.x;
	for(int i = n - 2; i >= 0; i--) {
		if(segs[i].x.y < mn) {
			vector<int> ts(n, 2);
			for(int id = 0; id <= i; id++)
				ts[segs[id].y] = 1;
			
			for(int t : ts)
				cout << t << ' ';
			cout << '\n';
				
			return;
		}
		mn = min(mn, segs[i].x.x);
	}
	cout << -1 << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc;
	cin >> tc;
	
	while(tc--) {
		assert(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 200 * 1000 + 13;

int n;
int a[N];
vector<int> g[N];

bool read () {
	if (scanf("%d", &n) != 1)
		return false;
	forn(i, n)
		g[i].clear();
	forn(i, n)
		scanf("%d", &a[i]);
	forn(i, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		--x, --y;
		g[x].pb(y);
		g[y].pb(x);
	}
	return true;
}

vector<pt> dp[N];
int ans;

void calc(int v, int p = -1){
	vector<pt> chd;
	for (auto u : g[v]) if (u != p){
		calc(u, v);
		for (auto it : dp[u])
			chd.pb(it);
	}
	
	sort(all(chd));
	forn(i, sz(chd)){
		int j = i - 1;
		int mx1 = 0, mx2 = 0;
		while (j + 1 < sz(chd) && chd[j + 1].x == chd[i].x){
			++j;
			if (chd[j].y >= mx1)
				mx2 = mx1, mx1 = chd[j].y;
			else if (chd[j].y > mx2)
				mx2 = chd[j].y;
		}
		if (a[v] % chd[i].x == 0){
			ans = max(ans, mx1 + mx2 + 1);
			dp[v].pb(mp(chd[i].x, mx1 + 1));
			while (a[v] % chd[i].x == 0)
				a[v] /= chd[i].x;
		}
		else{
			ans = max(ans, mx1);
		}
		i = j;
	}
	
	for (int i = 2; i * i <= a[v]; ++i) if (a[v] % i == 0){
		dp[v].pb(mp(i, 1));
		ans = max(ans, 1);
		while (a[v] % i == 0)
			a[v] /= i;
	}
	
	if (a[v] > 1){
		dp[v].pb(mp(a[v], 1));
		ans = max(ans, 1);
	}
}

void solve() {
	forn(i, N) dp[i].clear();
	ans = 0;
	calc(0);
	printf("%d\n", ans);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

#ifdef _DEBUG
	while(read()) {	
#else
	if (read()){
#endif
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	int mxa = 0, mxb = 0;
	static char buf[5];
	forn(i, n){
		int x, y;
		scanf("%s%d%d", buf, &x, &y);
		if (x < y)
			swap(x, y);
		if (buf[0] == '+'){
			mxa = max(mxa, x);
			mxb = max(mxb, y);
		}
		else{
			puts(mxa <= x && mxb <= y ? "YES" : "NO");
		}
	}
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define mp make_pair
#define pb push_back

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const int N = 411;

int n, m;
int a[N];
vector< pair<pt, pt> > qs;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	fore(i, 0, n)
		cin >> a[i];
	qs.resize(m);
	fore(i, 0, m) {
		cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
		qs[i].x.x--; qs[i].x.y--;
	}
	return true;
}

int getCnt(const pair<pt, pt> &q, li mx) {
	li dist = mx / q.y.x;
	
	int s = q.x.x, f = q.x.y;
	int u = s, cnt = 0;
	while(u < f) {
		int v = u;
		while(v < f && a[v + 1] - a[u] <= dist)
			v++;
		
		if(v == u)
			return INF;
		
		cnt++;
		u = v;
	}
	return cnt - 1;
}

li upd(const pair<pt, pt> &q, li lf, li rg) {
	if(getCnt(q, lf) <= q.y.y)
		return lf;
	
	while(rg - lf > 1) {
		li mid = (lf + rg) >> 1;
		(getCnt(q, mid) <= q.y.y ? rg : lf) = mid;
	}
	return rg;
}

inline unsigned int getHash(const vector<int> &vals) {
	unsigned int hash = 0;
	for(int v : vals)
		hash = hash * 3 + v;
	return hash;
}

inline void solve() {
	auto seed = getHash(vector<int>(a, a + n));
	fore(i, 0, m)
		seed = seed * 3 + getHash({qs[i].x.x, qs[i].x.y, qs[i].y.x, qs[i].y.y});
	mt19937 rnd(seed);
	
	vector<int> ids(m, 0);
	iota(all(ids), 0);
	shuffle(all(ids), rnd);
	
	li curv = 0;
	for(int id : ids)
		curv = upd(qs[id], curv, 2 * INF64);
	cout << curv << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define mp make_pair
#define pb push_back

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const int N = 411;

int n, m;
int a[N];
vector< pair<pt, pt> > qs;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	fore(i, 0, n)
		cin >> a[i];
	qs.resize(m);
	fore(i, 0, m) {
		cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
		qs[i].x.x--; qs[i].x.y--;
	}
	return true;
}

vector<int> ids[N];
int d[N][N];

inline void solve() {
	fore(i, 0, m)
		ids[qs[i].x.x].push_back(i);
	li ans = -1;
	
	fore(l, 0, n) {
		fore(r, l, n)
			d[0][r] = a[r] - a[l];
		
		fore(k, 1, n + 1) {
			int opt = l;
			fore(r, l, n) {
				while(opt < r && max(d[k - 1][opt], a[r] - a[opt]) >= max(d[k - 1][opt + 1], a[r] - a[opt + 1]))
					opt++;
				
				d[k][r] = max(d[k - 1][opt], a[r] - a[opt]);
			}
		}
		
		for(int id : ids[l])
			ans = max(ans, d[qs[id].y.y][qs[id].x.y] * 1ll * qs[id].y.x);
	}
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const int LOGN = 30;

int n;
int a[N], pr[N];
int base[LOGN];

void try_gauss(int v){
	for(int i = LOGN - 1; i >= 0; i--)
		if (base[i] != -1 && (v & (1 << i)))
			v ^= base[i];
	if (v == 0)
		return;
	for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){
		base[i] = v;
		return;
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d", &a[i]);
	memset(base, -1, sizeof(base));
	forn(i, n){
		pr[i + 1] = pr[i] ^ a[i];
		try_gauss(pr[i + 1]);
	}
	if (pr[n] == 0){
		puts("-1");
		return 0;
	}
	int siz = 0;
	forn(i, LOGN)
		siz += (base[i] != -1);
	printf("%d\n", siz);
}

T = int(input())
for i in range(T):
	l, r = map(int, input().split())
	print(l, l * 2)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	int cntl = 0, cntr = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == s[0]) {
			++cntl;
		} else {
			break;
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		if (s[i] == s[n - 1]) {
			++cntr;
		} else {
			break;
		}
	}
	if (s[0] == s[n - 1]) {
		cout << ((cntl + 1) * 1ll * (cntr + 1)) % 998244353 << endl;
	} else {
		cout << (cntl + cntr + 1) % 998244353;
	}
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int ang;

inline bool read() {
	if(!(cin >> ang))
		return false;
	return true;
}

inline void solve() {
	int g = __gcd(ang, 180);
	int k = ang / g;
	int n = 180 / g;
	
	if(k + 1 == n)
		k *= 2, n *= 2;
	cout << n << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		assert(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 100 * 1000 + 13;
const long long INF64 = 1e18;

int n;
string s;
int a[N];
long long dp[N][5];

const string h = "hard";

int main() {
	scanf("%d", &n);
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, n)
		scanf("%d", &a[i]);
	
	forn(i, N) forn(j, 5) dp[i][j] = INF64;
	dp[0][0] = 0;
	forn(i, n) forn(j, 4){
		dp[i + 1][j + (s[i] == h[j])] = min(dp[i + 1][j + (s[i] == h[j])], dp[i][j]);
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i]);
	}
	
	printf("%lld\n", *min_element(dp[n], dp[n] + 4));
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int MOD = 998244353;
const int N = 10 * 1000 + 7;
const int M = 100 + 7;

int fact[N], rfact[N];

int add(int a, int b){
	a += b;
	if (a >= MOD) a -= MOD;
	if (a < 0) a += MOD;
	return a;
}

int mul(int a, int b){
	return (a * 1ll * b) % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int cnk(int n, int k){
	if (n == k) return 1;
	if (k < 0 || k > n) return 0;
	return mul(fact[n], mul(rfact[k], rfact[n - k]));
}

int g(int s, int p, int m){
	int res = 0;
	forn(i, p + 1)
		res = add(res, mul(i & 1 ? MOD - 1 : 1, mul(cnk(p, i), cnk(s + p - 1 - i * (m + 1), p - 1))));
	return res;
}

int inv(int x){
	return mul(rfact[x], fact[x - 1]);
}

int main() {
	fact[0] = 1;
	for (int i = 1; i < N; ++i) fact[i] = mul(fact[i - 1], i);
	rfact[N - 1] = binpow(fact[N - 1], MOD - 2);
	for (int i = N - 2; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
	
	int p, s, r;
	scanf("%d%d%d", &p, &s, &r);
	
	int Q = cnk(s - r + p - 1, p - 1);
	int P = 0;
	for (int t = r; t <= s; ++t) for (int q = 1; q <= p; ++q)
		P = add(P, mul(mul(cnk(p - 1, q - 1), inv(q)), g(s - q * t, p - q, t - 1)));
	
	printf("%d\n", mul(P, binpow(Q, MOD - 2)));
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const int MOD = 998244353;

int n;
int p[N];
bool used[N];
int gt[N];

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}

int mul(int a, int b){
	return (a * 1ll * b) % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int f[N];

void upd(int x){
	for (int i = x; i < N; i |= i + 1)
		++f[i];
}

int get(int x){
	int sum = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		sum += f[i];
	return sum;
}

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &p[i]);
		if (p[i] != -1)
			used[p[i]] = true;
	}
	
	int cur = 0;
	for (int i = n; i >= 1; --i){
		gt[i] = cur;
		cur += !used[i];
	}
	
	// case 1
	int ans = mul(mul(cur, cur - 1), binpow(4, MOD - 2));
	
	int inv = binpow(cur, MOD - 2);
	
	// case 2
	int lft = 0;
	forn(i, n){
		if (p[i] == -1)
			++lft;
		else
			ans = add(ans, mul(lft, mul(gt[p[i]], inv)));
	}
	
	// case 3
	int rgh = 0;
	for (int i = n - 1; i >= 0; --i){
		if (p[i] == -1)
			++rgh;
		else
			ans = add(ans, mul(rgh, mul(cur - gt[p[i]], inv)));
	}
	
	// case 4	
	int tmp = 0;
	forn(i, n) if (p[i] != -1){
		ans = add(ans, tmp - get(p[i]));
		upd(p[i]);
		++tmp;
	}
	
	printf("%d\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define mp make_pair
#define pb push_back

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}

template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

const int N = 2500 * 1000 + 555;
const int LOGN = 22;

const int MOD = 998244353;
int g = 3;

inline int mul(int a, int b){
	return int(a * 1ll * b % MOD);
}

inline int norm(int a) {
	if(a >= MOD)
		a -= MOD;
	if(a < 0)
		a += MOD;
	return a;
}

inline int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

inline int inv(int a) {
	return binPow(a, MOD - 2);
}

vector<int> w[LOGN];
vector<int> rv[LOGN];

void precalc() {
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));

    for(int st = 0; st < LOGN - 1; st++) {
        w[st].assign(1 << st, 1);

        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int cw = 1;

        for (int k = 0; k < (1 << st); k++) {
            w[st][k] = cw;
            cw = mul(cw, bw);
        }
    }
    for(int st = 0; st < LOGN; st++) {
        rv[st].assign(1 << st, 0);

        if(st == 0) {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(int a[N], int n, bool inverse) {
    int ln = 0;
    while((1 << ln) < n)
        ln++;

    assert((1 << ln) < N);
    n = (1 << ln);

    forn(i, n) {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }

    for(int st = 0; (1 << st) < n; st++) {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) {
            for(int pos = k; pos < k + len; pos++) {
                int l = a[pos];
                int r = mul(a[pos + len], w[st][pos - k]);

                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }

    if(inverse) {
        int in = inv(n);
        forn(i, n)
            a[i] = mul(a[i], in);
        reverse(a + 1, a + n);
    }
}

int aa[N], bb[N], cc[N];

inline vector<int> multiply(const vector<int> a, const vector<int> b) {
	int ln = 1;
	while(ln < (sz(a) + sz(b)))
		ln <<= 1;
		
	forn(i, ln)
		aa[i] = (i < sz(a) ? a[i] : 0);
		
	forn(i, ln)
		bb[i] = (i < sz(b) ? b[i] : 0);
		
	fft(aa, ln, false);
	fft(bb, ln, false);
	
	forn(i, ln)
		cc[i] = mul(aa[i], bb[i]);
		
	fft(cc, ln, true);
	
	vector<int> c(ln, 0);
	forn(i, sz(c))
		c[i] = cc[i];
	
	while(sz(c) > 1 && c.back() == 0)
		c.pop_back();
	return c;
}

int n, k, a[11];

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	forn(i, k)
		cin >> a[i];
	return true;
}

inline void solve() {
	sort(a, a + k);
	
	vector<int> ans(1, 1);
	vector<int> f(10, 0);
	forn(i, k)
		f[a[i]] = 1;

	precalc();
		
	int pw = n / 2;
	while(pw > 0) {
		if(pw & 1)
			ans = multiply(ans, f);
		f = multiply(f, f);
		pw >>= 1;
	}
	
	int res = 0;
	forn(i, sz(ans))
		res = norm(res + mul(ans[i], ans[i]));
	cout << res << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int LOGN = 21;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;

#define forn(i, n) for(int i = 0; i < int(n); i++)

inline int mul(int a, int b)
{
	return (a * 1ll * b) % MOD;
}

inline int norm(int a) 
{
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int binPow(int a, int k) 
{
	int ans = 1;
	while(k > 0) 
	{
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

inline int inv(int a) 
{
	return binPow(a, MOD - 2);
}

vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];

void precalc() 
{
	int wb = binPow(g, (MOD - 1) / (1 << LOGN));
	
	for(int st = 0; st < LOGN; st++) 
	{
		w[st].assign(1 << st, 1);
		iw[st].assign(1 << st, 1);
		
		int bw = binPow(wb, 1 << (LOGN - st - 1));
		int ibw = inv(bw);
		
		int cw = 1;
		int icw = 1;
		
		for(int k = 0; k < (1 << st); k++) 
		{
			w[st][k] = cw;
			iw[st][k] = icw;
			
			cw = mul(cw, bw);
			icw = mul(icw, ibw);
		}
		
		rv[st].assign(1 << st, 0);
		
		if(st == 0) 
		{
			rv[st][0] = 0;
			continue;
		}
		int h = (1 << (st - 1));
		for(int k = 0; k < (1 << st); k++)
			rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
	}
}

inline void fft(int a[N], int n, int ln, bool inverse) 
{	
	for(int i = 0; i < n; i++) 
	{
		int ni = rv[ln][i];
		if(i < ni)
			swap(a[i], a[ni]);
	}
	
	for(int st = 0; (1 << st) < n; st++) 
	{
		int len = (1 << st);
		for(int k = 0; k < n; k += (len << 1)) 
		{
			for(int pos = k; pos < k + len; pos++) 
			{
				int l = a[pos];
				int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
				
				a[pos] = norm(l + r);
				a[pos + len] = norm(l - r);
			}
		}
	}
	
	if(inverse) 
	{
		int in = inv(n);
		for(int i = 0; i < n; i++)
			a[i] = mul(a[i], in);
	}
}

int aa[N], bb[N], cc[N];

inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 
{
	int n = 1, ln = 0;
	while(n < (sza + szb))
		n <<= 1, ln++;
	for(int i = 0; i < n; i++)
		aa[i] = (i < sza ? a[i] : 0);
	for(int i = 0; i < n; i++)
		bb[i] = (i < szb ? b[i] : 0);
		
	fft(aa, n, ln, false);
	fft(bb, n, ln, false);
	
	for(int i = 0; i < n; i++)
		cc[i] = mul(aa[i], bb[i]);
		
	fft(cc, n, ln, true);
	
	szc = n;
	for(int i = 0; i < n; i++)
		c[i] = cc[i];
}

vector<int> T[N];

int a[N];
int b[N];
int c[N];

#define sz(a) (int(a.size()))

int main()
{
	precalc();
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 0; i < k; i++)
	{
	    int x;
	    scanf("%d", &x);
	    a[x] = 1;
	}
	int nn = 1, ln = 0;
	int nw = (n * 5) + 1;
	while(nn < nw)
	{
		nn *= 2;
		ln++;
	}
	fft(a, nn, ln, false);
	forn(i, nn)
		a[i] = binPow(a[i], n / 2);
	fft(a, nn, ln, true);
	int ans = 0;
	forn(i, nn)
		ans = norm(ans + binPow(a[i], 2));
	printf("%d\n", ans);
	return 0;	
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int x;
		cin >> x;
		cout << x / 2 << endl;
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		if (s[0] == s.back()) cout << -1 << endl;
		else cout << s << endl;
	}
	return 0;
}

n = int(input())
l, r = 0, 10**18
b = list(map(int, input().split()))
a = [0 for i in range(n)]
for i in range(n // 2):
	a[i] = max(l, b[i] - r)
	a[-i - 1] = b[i] - a[i]
	l, r = a[i], a[-i - 1]
print(*a)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF64 = 1'000'000'000'000'000'000ll;
const int N = 200 * 1000 + 13;

int n;
long long a[N], b[N];

void brute(int x, long long l, long long r){
	if (x == n / 2){
		forn(i, n)
			printf("%lld ", a[i]);
		puts("");
		exit(0);
	}
	
	for (long long i = l; i <= b[x] / 2; ++i) if (b[x] - i <= r){
		a[x] = i;
		a[n - x - 1] = b[x] - i;
		brute(x + 1, i, b[x] - i);
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n / 2)
		scanf("%lld", &b[i]);
	brute(0, 0, INF64);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 999;
const int MOD = 998244353;

int n, m;
vector <int> g[N];
int p2[N];
int cnt[2];
int col[N];
bool bad;

void dfs(int v, int c){
	col[v] = c;
	++cnt[c];
	for(auto to : g[v]){
		if(col[to] == -1) dfs(to, 1 - c);
		if((col[v] ^ col[to]) == 0)
			bad = true;
	}
}

int main() {
    p2[0] = 1;
    for(int i = 1; i < N; ++i)
    	p2[i] = (2 * p2[i - 1]) % MOD;
    	
    int tc;
    scanf("%d", &tc);
    while(tc--){
    	scanf("%d%d", &n, &m);
    	for(int i = 0; i < n; ++i)
    	    g[i].clear();
    	
    	for(int i = 0; i < m; ++i){
    		int u, v;
    		scanf("%d %d", &u, &v);
    		--u, --v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	
    	int res = 1;
    	for(int i = 0; i < n; ++i) col[i] = -1;
    	for(int i = 0; i < n; ++i){
    	    if(col[i] != -1) continue;
            bad = false;
            cnt[0] = cnt[1] = 0;
            dfs(i, 0);
    	    if(bad){
    		    puts("0");
    		    break;
    	    }
    	    int cur = (p2[cnt[0]] + p2[cnt[1]]) % MOD;
    	    res = (res * 1LL * cur) % MOD;
    	}
    	
    	if(!bad) printf("%d\n", res);
    }
    
    return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n, m;
int a[N], b[N], pos[N];

vector<int> f[N];
vector<int> vals[N];

void addupd(int x, int y){
	for (int i = x; i < N; i |= i + 1)
		vals[i].push_back(y);
}

void addget(int x, int y){
	if (x < 0 || y < 0) return;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		vals[i].push_back(y);
}

void upd(int x, int y, int val){
	for (int i = x; i < N; i |= i + 1)
		for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < int(f[i].size()); j |= j + 1)
			f[i][j] += val;
}

int get(int x, int y){
	if (x < 0 || y < 0) return 0;
	int res = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j >= 0; j = (j & (j + 1)) - 1)
			res += f[i][j];
	return res;
}

struct query{
	int t, la, ra, lb, rb;
	query(){};
};

query q[N];

int main() {
	scanf("%d%d", &n, &m);
	
	forn(i, n){
		scanf("%d", &a[i]);
		--a[i];
		pos[a[i]] = i;
	}
	
	forn(i, n){
		scanf("%d", &b[i]);
		--b[i];
		b[i] = pos[b[i]];
	}
	
	forn(i, m){
		scanf("%d", &q[i].t);
		if (q[i].t == 1){
			scanf("%d%d%d%d", &q[i].la, &q[i].ra, &q[i].lb, &q[i].rb);
			--q[i].la, --q[i].ra, --q[i].lb, --q[i].rb;
		}
		else{
			scanf("%d%d", &q[i].lb, &q[i].rb);
			--q[i].lb, --q[i].rb;
		}
	}
	
	vector<int> tmp(b, b + n);
	
	forn(i, n) addupd(i, b[i]);
	forn(i, m){
		if (q[i].t == 1){
			addget(q[i].rb, q[i].ra);
			addget(q[i].lb - 1, q[i].ra);
			addget(q[i].rb, q[i].la - 1);
			addget(q[i].lb - 1, q[i].la - 1);
		}
		else{
			addupd(q[i].lb, b[q[i].lb]);
			addupd(q[i].rb, b[q[i].rb]);
			swap(b[q[i].lb], b[q[i].rb]);
			addupd(q[i].lb, b[q[i].lb]);
			addupd(q[i].rb, b[q[i].rb]);
		}
	}
	
	forn(i, n) b[i] = tmp[i];
	
	forn(i, N){
		sort(vals[i].begin(), vals[i].end());
		vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
		f[i].resize(vals[i].size(), 0);
	}
	
	forn(i, n)
		upd(i, b[i], 1);
	
	forn(i, m){
		if (q[i].t == 1){
			int res = 0;
			res += get(q[i].rb, q[i].ra);
			res -= get(q[i].lb - 1, q[i].ra);
			res -= get(q[i].rb, q[i].la - 1);
			res += get(q[i].lb - 1, q[i].la - 1);
			printf("%d\n", res);
		}
		else{
			upd(q[i].lb, b[q[i].lb], -1);
			upd(q[i].rb, b[q[i].rb], -1);
			swap(b[q[i].lb], b[q[i].rb]);
			upd(q[i].lb, b[q[i].lb], 1);
			upd(q[i].rb, b[q[i].rb], 1);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define forn(i, n) fore(i, 0, n)
#define nfor(i, n) for(int i = int(n) - 1; i >= 0; --i)
#define for1(i, n) for(int i = 1; i < int(n); ++i)

#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

#define correct(x, y, xmax, ymax) ((x) >= 0 && (x) < (xmax) && (y) >= 0 && (y) < (ymax))
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define abs(a) ((a < 0) ? -a : a)
#define sqr(a) (a * a)

using namespace std;

const int N = int(1e5);
const int M = 105;
const int MOD = 998244353;

int sum(int a, int b){
	return (a + b) % MOD;	
}

int n, k, len;
int a[N];
int dp[N][M];
int sumdp[N];
int cnt[M][N];

int main() {
	scanf("%d %d %d", &n, &k, &len);
	forn(i, n){ 	
		scanf("%d", a + i);
		if(a[i] != -1) --a[i];
	}
    forn(i, k) 
        forn(j, n)
            cnt[i][j + 1] = cnt[i][j] + (a[j] == i || a[j] == -1);
            
	forn(i, n){ 
		forn(j, k){
			if(!(a[i] == -1 || a[i] == j))
				continue;
			
			int add = 1;
			if(i > 0) add = sumdp[i - 1];
			dp[i][j] = add;
			
			bool ok = i + 1 >= len;
			int l = max(0, i - len + 1);
			int r = i + 1;
			ok &= (r - l == cnt[j][r] - cnt[j][l]); 
			if(!ok) continue;
			
			if(i + 1 == len){
				dp[i][j] = sum(dp[i][j], MOD - 1);
				continue;
			}
			
			add = sum(dp[i - len][j], MOD - sumdp[i - len]);
			dp[i][j] = sum(dp[i][j], add);
		}
		forn(j, k) sumdp[i] = sum(sumdp[i], dp[i][j]);
	}
	
	printf("%d\n", sumdp[n - 1]);

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int INF = int(1e9);

int T[4 * N][32];
int A[4 * N][5];
int n, k;

void build(int v, int l, int r)
{
	if(l == r - 1)
	{
		for(int i = 0; i < (1 << k); i++)
		{
			int cur = 0;
			for(int j = 0; j < k; j++)
				if(i & (1 << j))
					cur += A[l][j];
				else
					cur -= A[l][j];
			T[v][i] = cur;
		}
	}
	else
	{
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m, r);
		for(int i = 0; i < (1 << k); i++)
			T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]);
	}
}

int query(int v, int l, int r, int L, int R, int x)
{
	if(L >= R) return INF;
	if(L == l && R == r)
		return T[v][x];
	int m = (l + r) / 2;
	return min(query(v * 2 + 1, l, m, L, min(R, m), x), query(v * 2 + 2, m, r, max(L, m), R, x));
}

void upd(int v, int l, int r, int z)
{
	if(l == r - 1)
	{
		for(int i = 0; i < (1 << k); i++)
		{
			int cur = 0;
			for(int j = 0; j < k; j++)
				if(i & (1 << j))
					cur += A[l][j];
				else
					cur -= A[l][j];
			T[v][i] = cur;
		}
	}
	else
	{
		int m = (l + r) / 2;
		if(z < m)
			upd(v * 2 + 1, l, m, z);
		else
			upd(v * 2 + 2, m, r, z);
		for(int i = 0; i < (1 << k); i++)
			T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]);
	}
}

int main() 
{ 
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < k; j++)
		{
			scanf("%d", &A[i][j]);
		}
	}
	int q;
	scanf("%d", &q);
	build(0, 0, n);
	for(int i = 0; i < q; i++)
	{
		int t;
		scanf("%d", &t);
		if(t == 1)
		{
			int z;
			scanf("%d", &z);
			--z;
			for(int j = 0; j < k; j++)
				scanf("%d", &A[z][j]);
			upd(0, 0, n, z);
		}
		else
		{
			int ans = 0;
			int l, r;
			scanf("%d %d", &l, &r);
			--l;
			for(int i = 0; i < (1 << (k - 1)); i++)
			{
				int x = query(0, 0, n, l, r, i);
				int y = query(0, 0, n, l, r, ((1 << k) - 1) ^ i);
				ans = max(ans, abs(x + y));
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const int INF = 1e9;

struct point{
	int a[5];
	point(){};
	int& operator[](int x){
		return a[x];
	}
};

int n, k;
point a[N];

int t[32][4 * N];

int apply(point& p, int mask){
	int res = 0;
	forn(i, k){
		res += (mask & 1 ? p[i] : -p[i]);
		mask >>= 1;
	}
	return res;
}

void build(int v, int l, int r){
	if (l == r - 1){
		forn(mask, 1 << k)
			t[mask][v] = apply(a[l], mask);
		return;
	}
	
	int m = (l + r) / 2;
	
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	
	forn(mask, 1 << k)
		t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]);
}

void upd(int v, int l, int r, int pos, point& val){
	if (l == r - 1){
		forn(mask, 1 << k)
			t[mask][v] = apply(val, mask);
		return;
	}
	
	int m = (l + r) / 2;
	
	if (pos < m)
		upd(v * 2, l, m, pos, val);
	else
		upd(v * 2 + 1, m, r, pos, val);
	
	forn(mask, 1 << k)
		t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]);
}

int bst[32];

void get(int v, int l, int r, int L, int R){
	if (L >= R)
		return;
	
	if (l == L && r == R){
		forn(mask, 1 << k)
			bst[mask] = min(bst[mask], t[mask][v]);
		return;
	}
	
	int m = (l + r) / 2;
	
	get(v * 2, l, m, L, min(m, R));
	get(v * 2 + 1, m, r, max(m, L), R);
}

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) forn(j, k)
		scanf("%d", &a[i][j]);
	build(1, 0, n);
	
	int m;
	scanf("%d", &m);
	forn(_, m){
		int t;
		scanf("%d", &t);
		if (t == 1){
			int i;
			scanf("%d", &i);
			--i;
			point tmp;
			forn(j, k)
				scanf("%d", &tmp[j]);
			upd(1, 0, n, i, tmp);
		}
		else{
			int l, r;
			scanf("%d%d", &l, &r);
			--l, --r;
			forn(mask, 1 << k)
				bst[mask] = INF;
			get(1, 0, n, l, r + 1);
			
			int ans = 0;
			forn(mask, 1 << k)
				ans = max(ans, abs(bst[(1 << k) - 1 - mask] + bst[mask]));
			printf("%d\n", ans);
		}
	}
	return 0;
}