#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) {
		long long a, b, c;
		cin >> a >> b >> c;
		cout << (a + b + c) / 2 << 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		int cntodd = 0;
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
			cntodd += a[j] % 2;
		}
		if (cntodd < k || cntodd % 2 != k % 2) {
			cout << "NO" << endl;
			continue;
		}
		cout << "YES" << endl;
		for (int j = 0; j < n; ++j) {
			if (k == 1) break;
			if (a[j] % 2 == 1) {
				cout << j + 1 << " ";
				--k;
			}
		}
		cout << n << endl;
	}
	return 0;
}

#include <algorithm>
#include <iostream>

using namespace std;

const int MAXC = 1e5;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int mnx = -MAXC, mxx = MAXC;
        int mny = -MAXC, mxy = MAXC;
        while (n--) {
            int x, y, f1, f2, f3, f4;
            cin >> x >> y >> f1 >> f2 >> f3 >> f4;
            if (!f1) mnx = max(mnx, x);
            if (!f2) mxy = min(mxy, y);
            if (!f3) mxx = min(mxx, x);
            if (!f4) mny = max(mny, y);
        }
        if (mnx <= mxx && mny <= mxy)
            cout << "1 " << mnx << " " << mny << "\n";
        else
            cout << "0\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
	
	const string t = "RGB";

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		int ans = 1e9;
		for (int j = 0; j < n - k + 1; ++j) {
			for (int offset = 0; offset < 3; ++offset) {
				int cur = 0;
				for (int pos = 0; pos < k; ++pos) {
					if (s[j + pos] != t[(pos + offset) % 3]) {
						++cur;
					}
				}
				ans = min(ans, cur);
			}
		}
		cout << ans << 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
	
	const string t = "RGB";

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		int ans = 1e9;
		for (int offset = 0; offset < 3; ++offset) {
			vector<int> res(n);
			int cur = 0;
			for (int j = 0; j < n; ++j) {
				res[j] = (s[j] != t[(j + offset) % 3]);
				cur += res[j];
				if (j >= k) cur -= res[j - k];
				if (j >= k - 1) ans = min(ans, cur);
			}
		}
		cout << ans << 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int b, w;
		cin >> b >> w;
		vector<pair<int, int>> res;
		bool need = b < w;
		if (need) swap(w, b);
		int x = 2, y = 2;
		while (w > 0) {
			if ((x + y) % 2 == 1) {
				res.push_back({x, y});
				--b;
			} else {
				res.push_back({x, y});
				--w;
			}
			++y;
		}
		int cx = 1, cy = 2;
		while (b > 0 && cy <= y) {
			res.push_back({cx, cy});
			--b;
			cy += 2;
		}
		cx = 3, cy = 2;
		while (b > 0 && cy <= y) {
			res.push_back({cx, cy});
			--b;
			cy += 2;
		}
		if (b > 0) {
			res.push_back({2, 1});
			--b;
		}
		if (b > 0) {
			res.push_back({2, y});
			--b;
		}
		if (b > 0) {
			cout << "NO" << endl;
		} else {
			assert(w == 0);
			cout << "YES" << endl;
			for (auto it : res) cout << it.first << " " << it.second + need << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	vector<pair<int, pair<int, int>>> e;
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		--x, --y;
		e.push_back(make_pair(w, make_pair(x, y)));
	}
	sort(e.begin(), e.end());
	
	vector<int> vert;
	for (int i = 0; i < min(m, k); ++i) {
		vert.push_back(e[i].second.first);
		vert.push_back(e[i].second.second);
	}
	sort(vert.begin(), vert.end());
	vert.resize(unique(vert.begin(), vert.end()) - vert.begin());
	int cntv = vert.size();
	vector<vector<long long>> dist(cntv, vector<long long>(cntv, INF64));
	for (int i = 0; i < cntv; ++i) dist[i][i] = 0;
	
	for (int i = 0; i < min(m, k); ++i) {
		int x = lower_bound(vert.begin(), vert.end(), e[i].second.first) - vert.begin();
		int y = lower_bound(vert.begin(), vert.end(), e[i].second.second) - vert.begin();
		dist[x][y] = dist[y][x] = min(dist[x][y], (long long)e[i].first);
	}
	
	for (int z = 0; z < cntv; ++z) {
		for (int x = 0; x < cntv; ++x) {
			for (int y = 0; y < cntv; ++y) {
				dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
			}
		}
	}
	
	vector<long long> res;
	for (int i = 0; i < cntv; ++i) {
		for (int j = 0; j < i; ++j) {
			res.push_back(dist[i][j]);
		}
	}
	
	sort(res.begin(), res.end());
	cout << res[k - 1] << endl;
	
	return 0;
}

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n, k;
	cin >> n >> k;
	map<int, int> have;
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		have[num]++;
	}
	int cnt = 0;
	int ans = 0;
	for (pii p : have) {
		cnt += p.ss % 2;
		ans += p.ss / 2 * 2;
	}
	ans += (cnt + 1) / 2;
	cout << ans << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

#include <iostream>
#include <cmath>

int main() {
    long long n, k;
    std::cin >> n >> k;
    long long l = -1, r = n + 1;
    while (r - l > 1) {
        long long m = (l + r) / 2;
        if ((n - m) * (n - m + 1) / 2 - m > k)
            l = m;
        else
            r = m;
    }
    std::cout << r;
    return 0;
}

#include <iostream>
#include <cmath>

int main() {
    long long n, k;
    std::cin >> n >> k;
    std::cout << static_cast<long long>(round(n + 1.5 - sqrt(2 * (n + k) + 2.75)));
    return 0;
}

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n;
	cin >> n;
	vector<vector<int>> inp;
	for (int i = 0; i < 2; ++i) {
		inp.push_back(vector<int>());
		for (int j = 0; j < n; ++j) {
			int num;
			cin >> num;
			inp[i].push_back(num);
		}
	}

	pll d = {0, 0};

	for (int i = 0; i < n; ++i) {
		pll next = {max(d.ff, d.ss + inp[0][i]), max(d.ss, d.ff + inp[1][i])};
		d = next;
	}

	cout << max(d.ff, d.ss) << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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 len;
vector<int> pw10;

int f(int a) {
	int pos = 0;
	int res = 0;
	while (a > 0) {
		int cur = a % 10;
		a /= 10;
		res = add(res, mul(cur, pw10[2 * pos]));
		res = add(res, mul(cur, pw10[2 * pos + 1]));
		++pos;
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	pw10 = vector<int>(30);
	pw10[0] = 1;
	for (int i = 1; i < 30; ++i) {
		pw10[i] = mul(pw10[i - 1], 10);
	}
	
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		len = to_string(a).size();
		ans = add(ans, mul(n, f(a)));
	}
	
	cout << ans << endl;
	
	return 0;
}

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

const int MOD = 998244353;

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

int sum(int a, int b) {
	add(a, b);
	return a;
}

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

int f(vector<int> const& a, int l) {
	int res = 0;
	int p = 1;
	for (int i = 0; i < max(szof(a), l); ++i) {
		if (i < l) {
			p = mult(p, 10);
		}
		if (i < szof(a)) {
			add(res, mult(a[i], p));
			p = mult(p, 10);
		}
	}
	return res;
}

int f(int l, vector<int> const& b) {
	int res = 0;
	int p = 1;
	for (int i = 0; i < max(l, szof(b)); ++i) {
		if (i < szof(b)) {
			add(res, mult(b[i], p));
			p = mult(p, 10);
		}
		if (i < l) {
			p = mult(p, 10);
		}
	}
	return res;
}

void solve() {
	int n;
	cin >> n;
	vector<int> arr;
	const int MAXL = 11;
	vector<int> of_len(MAXL);
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		arr.push_back(num);
		int l = 0;
		int tmp = num;
		while (tmp) {
			++l;
			tmp /= 10;
		}
		of_len[l]++;
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		vector<int> digits;
		int tmp = arr[i];
		while (tmp) {
			digits.push_back(tmp % 10);
			tmp /= 10;
		}
		for (int l = 1; l < MAXL; ++l) {
			int sum = f(digits, l);
			add(ans, mult(sum, of_len[l]));


			sum = f(l, digits);
			add(ans, mult(sum, of_len[l]));
		}
	}

	cout << ans << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

#include <bits/stdc++.h>

using namespace std;

long long n, m, a, b, g, x, y, z;
vector<deque<long long> > deq;
vector<vector<long long> > mi;
vector<int> power;
const long long MAX_V = 1000000000000000ll;

void ins(deque<long long>& de, long long val) {
    while(!de.empty() && de.back() > val) {
        de.pop_back();
    }
    de.push_back(val);
}

void del(deque<long long>& de, long long val) {
    if (!de.empty() && de.front() == val) {
        de.pop_front();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin >> a >> b;
    cin >> g >> x >> y >> z;
    mi.resize(n);
    deq.resize(m);
    for (int i = 0; i < n; i++) {
        mi[i].resize(m);
        for (int j = 0; j < m; j++) {
            mi[i][j] = g;
            g = (g * x + y) % z;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < a; j++) {
            ins(deq[i], mi[j][i]);
        }
    }
    deque<long long> real_deq;
    for (int i = 0; i < b; i++) {
        ins(real_deq, deq[i].front());
    }
    long long ans = 0;
    ans += real_deq.front();
    for (int i = b; i < m; i++) {
        del(real_deq, deq[i - b].front());
        ins(real_deq, deq[i].front());
        ans += real_deq.front();
    }
    for (int i = a; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            ins(deq[j], mi[i][j]);
            del(deq[j], mi[i - a][j]);
        }
        deque<long long> real_d;
        for (int j = 0; j < b; j++) {
            ins(real_d, deq[j].front());
        }
        ans += real_d.front();
        for (int j = b; j < m; j++) {
            del(real_d, deq[j - b].front());
            ins(real_d, deq[j].front());
            ans += real_d.front();
        }
    }
    cout << ans << "\n";
}

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

struct point {
	int x, y;
	point(int _x, int _y) : x(_x), y(_y) {}

	point operator-(point const& other) const {
		return point(x - other.x, y - other.y);
	}

	point& operator/=(int num) {
		x /= num;
		y /= num;
		return *this;
	}

	bool operator<(point const& other) const {
		return x < other.x || (x == other.x && y < other.y);
	}
};

void solve() {
	int n;
	cin >> n;
	vector<vector<point>> polys;
	vector<point> vecs;
	vector<int> borders;
	borders.push_back(0);
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		borders.push_back(borders.back() + k);
		polys.push_back({});
		for (int j = 0; j < k; ++j) {
			int x, y;
			cin >> x >> y;
			polys.back().push_back(point(x, y));
		}

		for (int j = 0; j < k; ++j) {
			int next = (j + 1) % k;
			point v = polys[i][next] - polys[i][j];
			int tmp = __gcd(abs(v.x), abs(v.y));
			v /= tmp;
			vecs.push_back(v);
		}
	}

	vector<int> arr;
	map<point, int> inds;
	for (auto v : vecs) {
		if (!inds.count(v)) {
			int tmp = szof(inds);
			inds[v] = tmp;
		}
		arr.push_back(inds[v]);
	}

	vector<int> next(szof(vecs));
	vector<int> last(szof(inds), INF);
	for (int i = szof(vecs) - 1; i >= 0; --i) {
		next[i] = last[arr[i]];
		last[arr[i]] = i;
	}


	vector<vector<pii>> here(szof(vecs));
	int q;
	cin >> q;
	vector<int> ans(q);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		--l;
		l = borders[l];
		r = borders[r];
		here[l].push_back({r, i});
	}

	int bpv = 1;
	while (bpv < szof(vecs)) {
		bpv *= 2;
	}

	vector<int> segtree(bpv * 2);

	function<void(int, int)> segtree_set = [&](int pos, int val) {
		pos += bpv;
		segtree[pos] = val;
		pos /= 2;
		while (pos) {
			segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
			pos /= 2;
		}
	};

	function<int(int, int, int, int, int)> segtree_get = [&](int v, int vl, int vr, int l, int r) {
		if (vr <= l || r <= vl) {
			return 0;
		}
		if (l <= vl && vr <= r) {
			return segtree[v];
		}
		int vm = (vl + vr) / 2;
		return segtree_get(v * 2, vl, vm, l, r) + segtree_get(v * 2 + 1, vm, vr, l, r);
	};

	for (int i = 0; i < szof(inds); ++i) {
		segtree_set(last[i], 1);
	}

	for (int i = 0; i < szof(vecs); ++i) {
		for (auto p : here[i]) {
			ans[p.ss] = segtree_get(1, 0, bpv, i, p.ff);
		}
		segtree_set(i, 0);
		if (next[i] != INF) {
			segtree_set(next[i], 1);
		}
	}

	for (int num : ans) {
		cout << num << "\n";
	}
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

#include <bits/stdc++.h>

using namespace std;

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

int sum(int a) {
    int result = 0;
    while (a > 0) {
        result += a % 10;
        a /= 10;
    }
    return result;
}

int main() {
    int a;
    cin >> a;
    while (sum(a) % 4 != 0) {
        a++;
    }
    cout << a << endl;
}

#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, k;
		cin >> n >> k;
		vector<int> a(n);
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
		}
		int mn = *min_element(a.begin(), a.end());
		int mx = *max_element(a.begin(), a.end());
		if (mx - mn > 2 * k) cout << -1 << endl;
		else cout << mn + k << 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		long long k, n, a, b;
		cin >> k >> n >> a >> b;
		k -= n * a;
		if (k > 0) {
			cout << n << endl;
		} else {
			k = -k;
			++k;
			long long diff = a - b;
			long long turns = (k + diff - 1) / diff;
			if (turns > n) {
				cout << -1 << '\n';
			} else {
				cout << n - turns << '\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 q;
	cin >> q;
	for (int t = 0; t < q; ++t) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
		}
		sort(cnt.rbegin(), cnt.rend());
		int ans = cnt[0];
		int lst = cnt[0];
		for (int i = 1; i <= n; ++i) {
			if (lst == 0) break;
			if (cnt[i] >= lst) {
				ans += lst - 1;
				lst -= 1;
			} else {
				ans += cnt[i];
				lst = cnt[i];
			}
		}
		cout << ans << 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, k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	int ans = 0;
	queue<string> q;
	set<string> st;
	q.push(s);
	st.insert(s);
	while (!q.empty() && int(st.size()) < k) {
		string v = q.front();
		q.pop();
		for (int i = 0; i < int(v.size()); ++i) {
			string nv = v;
			nv.erase(i, 1);
			if (!st.count(nv) && int(st.size()) + 1 <= k) {
				q.push(nv);
				st.insert(nv);
				ans += n - nv.size();
			}
		}
	}
	
	if (int(st.size()) < k) cout << -1 << endl;
	else cout << ans << 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		set<int> st;
		for (int j = 0; j < n; ++j) {
			int x;
			cin >> x;
			st.insert(x);
		}
		
		int ans = 0;
		int mx = *st.rbegin();
		if (mx % 2 == 0 && mx % 3 == 0 && mx % 5 == 0) {
			if (st.count(mx / 2) && st.count(mx / 3) && st.count(mx / 5)) {
				ans = max(ans, mx / 2 + mx / 3 + mx / 5);
			}
		}
		
		vector<int> res;
		while (!st.empty() && int(res.size()) < 3) {
			int x = *st.rbegin();
			st.erase(prev(st.end()));
			bool ok = true;
			for (auto it : res) ok &= (it % x != 0);
			if (ok) res.push_back(x);
		}
		
		ans = max(ans, accumulate(res.begin(), res.end(), 0));
		
		cout << ans << endl;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> cnt(n);
	vector<int> cnt_good(n);
	for(int i = 0; i < n; i++)
	{
		int a, f;
		scanf("%d %d", &a, &f);
		--a;
		cnt[a]++;
		if(f) cnt_good[a]++;
	}
	vector<vector<int> > types(n + 1);
	for(int i = 0; i < n; i++)
		types[cnt[i]].push_back(cnt_good[i]);
	int ans1 = 0;
	int ans2 = 0;
	multiset<int> cur;
	for(int i = n; i > 0; i--)
	{
		for(auto x : types[i]) cur.insert(x);
		if(!cur.empty())
		{
			int z = *cur.rbegin();
			ans1 += i;
			ans2 += min(i, z);
			cur.erase(cur.find(z));
		}
	}
	printf("%d %d\n", ans1, ans2);
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
		solve();
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e12;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	long long k;
	cin >> n >> k;
	--k; // the whole string costs nothing
	string s;
	cin >> s;
	
	vector<vector<int>> lst(n, vector<int>(26, -1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 26; ++j) {
			if (i > 0) lst[i][j] = lst[i - 1][j];
		}
		lst[i][s[i] - 'a'] = i;
	}
	
	vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
	for (int i = 0; i < n; ++i) {
		dp[i][1] = 1;
	}
	
	for (int len = 2; len < n; ++len) {
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < 26; ++j) {
				if (lst[i - 1][j] != -1) {
					dp[i][len] = min(INF64, dp[i][len] + dp[lst[i - 1][j]][len - 1]);
				}
			}
		}
	}
	
	long long ans = 0;
	for (int len = n - 1; len >= 1; --len) {
		long long cnt = 0;
		for (int j = 0; j < 26; ++j) {
			if (lst[n - 1][j] != -1) {
				cnt += dp[lst[n - 1][j]][len];
			}
		}
		if (cnt >= k) {
			ans += k * (n - len);
			k = 0;
			break;
		} else {
			ans += cnt * (n - len);
			k -= cnt;
		}
	}
	
	if (k == 1) {
		ans += n;
		--k;
	}
	
	if (k > 0) cout << -1 << endl;
	else cout << ans << 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		long long n;
		cin >> n;
		int cnt2 = 0, cnt3 = 0, cnt5 = 0;
		while (n % 2 == 0) {
			n /= 2;
			++cnt2;
		}
		while (n % 3 == 0) {
			n /= 3;
			++cnt3;
		}
		while (n % 5 == 0) {
			n /= 5;
			++cnt5;
		}
		if (n != 1) {
			cout << -1 << endl;
		} else {
			cout << cnt2 + cnt3 * 2 + cnt5 * 3 << endl;
		}
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int t, n;
int cnt[3];

int main(){
    cin >> t;
    for(int tc = 0; tc < t; ++tc){
        memset(cnt, 0, sizeof cnt);
        cin >> n;
        for(int i = 0; i < n; ++i){
            int x;
            cin >> x;
            ++cnt[x % 3];
        }
    	
    	int res = cnt[0];
        int mn = min(cnt[1], cnt[2]);
        res += mn;
        cnt[1] -= mn, cnt[2] -= mn;
        res += (cnt[1] + cnt[2]) / 3;
        cout << res << 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
	
	vector<int> p({4, 8, 15, 16, 23, 42});

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		a[i] = lower_bound(p.begin(), p.end(), a[i]) - p.begin();
	}
	
	vector<int> seq(6);
	for (int i = 0; i < n; ++i) {
		if (a[i] == 0) {
			++seq[0];
		} else {
			if (seq[a[i] - 1] > 0) {
				--seq[a[i] - 1];
				++seq[a[i]];
			}
		}
	}
	
	cout << n - seq[5] * 6 << 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 = 3 * 1000 * 1000 + 13;

int lst[N];
int num[N];

void sieve(){
	forn(i, N) lst[i] = i;
	for (int i = 2; i < N; ++i){
		if (lst[i] != i){
			lst[i] = i / lst[i];
			continue;
		}
		for (long long j = i * 1ll * i; j < N; j += i)
			lst[j] = min(lst[j], i);
	}
	int cur = 0;
	for (int i = 2; i < N; ++i) if (lst[i] == i)
		num[i] = ++cur;
}

int cnt[N];

int main() {
	int n;
	scanf("%d", &n);
	forn(i, 2 * n){
		int x;
		scanf("%d", &x);
		++cnt[x];
	}
	
	sieve();
	
	vector<int> res;
	for (int i = N - 1; i >= 0; --i){
		while (cnt[i] > 0){
			if (lst[i] == i){
				--cnt[num[i]];
				res.push_back(num[i]);
			}
			else{
				--cnt[lst[i]];
				res.push_back(i);
			}
			--cnt[i];
		}
	}
	
	for (auto it : res)
		printf("%d ", it);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n, m;
vector<int> d;
vector<vector<int>> g;

void bfs(int s) {
	d = vector<int>(n, INF);
	d[s] = 0;
	
	queue<int> q;
	q.push(s);
	
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		
		for (auto to : g[v]) {
			if (d[to] == INF) {
				d[to] = d[v] + 1;
				q.push(to);
			}
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	
	for (int tc = 0; tc < t; ++tc){
		cin >> n >> m;
		g = vector<vector<int>>(n);
		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);
		}
	
		bfs(0);
		vector<int> even, odd;
		for (int i = 0; i < n; ++i) {
			if (d[i] & 1) odd.push_back(i);
			else even.push_back(i);
		}
	
		if (even.size() < odd.size()) {
			cout << even.size() << endl;
			for (auto v : even) cout << v + 1 << " ";
		} else {
			cout << odd.size() << endl;
			for (auto v : odd) cout << v + 1 << " ";
		}
		cout << endl;
	}
	
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long li;

const li INF64 = li(1e18);

const int N = 200043;
vector<int> cards[N][4];
li dp[N][10];
int n;
li dp2[4][2];

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	for(int i = 0; i < N; i++)
		for(int j = 0; j < 10; j++)
			dp[i][j] = -INF64;
	dp[0][0] = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int k;
		scanf("%d", &k);
		for (int j = 0; j < k; j++)
		{
			int c, d;
			scanf("%d %d", &c, &d);
			cards[i][c].push_back(d);
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			int s = (j == 1 ? 3 : 1);
			sort(cards[i][j].begin(), cards[i][j].end());
			reverse(cards[i][j].begin(), cards[i][j].end());
			while (cards[i][j].size() > s)
				cards[i][j].pop_back();
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 2; k++)
				dp2[j][k] = -INF64;
		dp2[0][0] = 0;
		vector<pair<int, int> > cur;
		for (int j = 1; j <= 3; j++)
			for (auto x : cards[i][j])
				cur.push_back(make_pair(j, x));
		sort(cur.begin(), cur.end());
		do
		{
			int mana = 3;
			li score = 0;
			li mx = 0;
			int cnt = 0;
			for (auto x : cur)
			{
				cnt++;
				if (mana < x.first)
					break;
				mana -= x.first;
				mx = max(mx, li(x.second));
				score += x.second;
				dp2[cnt][0] = max(dp2[cnt][0], score);
				dp2[cnt][1] = max(dp2[cnt][1], score + mx);
			}
		} while (next_permutation(cur.begin(), cur.end()));
		for(int j = 0; j < 10; j++)
			for (int k = 0; k <= 3; k++)
			{
				int nxt = (j + k) % 10;
				int f = (j + k >= 10 ? 1 : 0);
				dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + dp2[k][f]);
			}
	}
	li ans = 0;
	for (int i = 0; i <= 9; i++)
		ans = max(ans, dp[n][i]);
	printf("%lld\n", ans);
	return 0;
}

fun main() {
    val q = readLine()!!.toInt()
    repeat(q) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() }.sorted()
        println("1 $$${x - 1} $$${y - x + 1}")
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    var m1 = 0
    var m2 = 0
    var c = 0
    for (x in a) {
        if (m2 > x) {
            c++
        }
        when {
            x > m1 -> {
                m2 = m1
                m1 = x
            }
            x > m2 -> {
                m2 = x
            }
        }
    }
    println(c)
}

fun main() {
    val k = readLine()!!.toInt()
    repeat(k) {
        val s = readLine()!!
        val t = readLine()!!
        println(if (solve(s, t)) "YES" else "NO")
    }
}

private fun solve(s: String, t: String): Boolean {
    var i = 0
    var j = 0
    while (i < s.length && j < t.length) {
        when (s[i]) {
            t[j] -> {}
            '+' -> return false
            else -> { // '-' -> '+'
                i++
                if (i >= s.length || s[i] != '-') return false
            }
        }
        i++
        j++
    }
    return i == s.length && j == t.length
}

import java.util.*

fun main() {
    val m = readLine()!!.toInt()
    val b = readLine()!!.split(" ").map { it.toInt() }
    val n = b.count { it == -1 }
    val a = Array(n) { ArrayList<Int>() }
    val ix = LinkedList<Int>((0 until n).toList())
    var iter = ix.iterator()
    for (x in b) {
        if (!iter.hasNext()) iter = ix.iterator()
        val i = iter.next()
        if (x == -1) {
            iter.remove()
        } else {
            a[i].add(x)
        }
    }
    println(n)
    println(a.joinToString("\n") {
        "$$${it.size} $$${it.joinToString(" ")}"
    })
}

fun main() {
    val (n, m) = readInts()
    val a = readInts().toIntArray()
    val q = readInt()
    val b = IntArray(4 * a.size)

    fun buildTree(il: Int, ir: Int, p: Int): Int {
        val s = if (il == ir) {
            a[il]
        } else {
            val im = (il + ir) / 2
            buildTree(il, im, 2 * p + 1) + buildTree(im + 1, ir, 2 * p + 2)
        }
        b[p] = s
        return s
    }

    buildTree(0, n - 1, 0)
    val ans = List(q) {
        val w = readInts().drop(1) + (m + 1) // sentinel
        if (solveDoors(n, m, b, w)) "YES" else "NO"
    }.joinToString("\n")
    println(ans)
}

private fun solveDoors(n: Int, m: Int, b: IntArray, w: List<Int>): Boolean {
    var pp = 0
    var i = 0
    var rem = 0

    fun queryTree(il: Int, ir: Int, p: Int, i: Int): Int {
        if (il == i && rem >= b[p]) {
            rem -= b[p]
            return ir + 1
        }
        if (il == ir) return i
        val im = (il + ir) / 2
        if (i > im) return queryTree(im + 1, ir, 2 * p + 2, i)
        val j = queryTree(il, im,2 * p + 1, i)
        if (j <= im) return j
        return queryTree(im + 1, ir,2 * p + 2, im + 1)
    }

    for (cp in w) {
        rem = cp - pp - 1
        i = queryTree(0, n - 1, 0, i)
        if (i >= n) return true
        pp = cp
    }
    return false
}

private fun readInt() = readLine()!!.toInt()
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

import java.util.*

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextInts() = next().split(" ").map { it.toInt() }
fun nextLongs() = next().split(" ").map { it.toLong() }

fun solve() {
    val (n,m,k) = nextInts()
    var A = nextLongs()
    var a = arrayListOf<Long>()
    a.addAll(A)
    a.sort()
    var ans = (1e18).toLong()
    var ind = 0
    var above:Long = 0
    var below:Long = 0
    for (i in 0..m-1) above += a[i]-a[0]
    for (i in 0..n-m) {
        val des = i+(m-1)/2
        while (ind < des) { // try to get closer to median if possible
            if (below+(a[ind+1]-a[ind])*(ind+1-i) <= k) {
                below += (a[ind+1]-a[ind])*(ind+1-i)
                above -= (a[ind+1]-a[ind])*(i+m-1-ind) // ind+1 to i+m-1
                ind ++
            } else break
        }
        assert (k >= below)
        if (ind < des) {
            var oops: Long = (k-below)/(ind+1-i)
            ans = minOf(ans,below+above-(i+m-1-ind)*oops+(ind+1-i)*oops)
            assert(i+m-1-ind >= ind+1-i)
        } else ans = minOf(ans,above+below)
        if (i < n-m) {
            below -= a[ind]-a[i]
            above += a[i+m]-a[ind]
        }
    }
    print(ans)
}

fun main(args: Array<String>) {
    val t = 1
    for (i in 0..t-1) solve()
}

fun main() {
    solveEuler()
}

class E(
    val y: Int,
    var c: Int = 0
)

class Edges {
    private val e = HashMap<Int, E>(2)
    private val c = ArrayList<E>(2)
    private var first = 0

    fun degree() = c.sumBy { it.c }

    fun add(y: Int) {
        val cur = e.getOrPut(y) { E(y) }
        if (cur.c == 0) c.add(cur)
        cur.c++
    }

    fun first() = c[first].y

    fun hasNext() = first < c.size

    fun rem(y: Int) {
        val cur = e.getValue(y)
        if (--cur.c == 0) {
            while (first < c.size && c[first].c == 0) first++
        }
    }
}

private fun solveEuler() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val g = Array(n) { Edges() }
    repeat(m) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
        g[x].add(y)
        g[y].add(x)
    }
    if (!g.all { it.degree() % 2 == 0 }) {
        println("NO")
    } else {
        val c = ArrayList<List<Int>>()
        var start = 0
        val v = IntArray(n) { -1 }
        while (true) {
            while (start < n && !g[start].hasNext()) start++
            if (start >= n) break
            val list = ArrayList<Int>()
            var x = start
            while (true) {
                v[x] = list.size
                list.add(x)
                val y = g[x].first()
                g[x].rem(y)
                g[y].rem(x)
                if (y == start) break
                if (v[y] >= 0) {
                    val d = list.subList(v[y], list.size)
                    c.add(d.toList())
                    for (z in d) v[z] = -1
                    d.clear()
                }
                x = y
            }
            c.add(list)
            for (z in list) v[z] = -1
        }
        println("YES")
        println(c.size)
        val ans = c.joinToString("\n") { list ->
            "$$${list.size + 1} $$${list.joinToString(" ") { (it + 1).toString() }} ${list[0] + 1}"
        }
        println(ans)
    }
}

import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

/**
 * @author: pashka
 */

fun solve(a: IntArray): IntArray {
    val n = a.size
    var l = 0
    var r = a.size + 1
    var best = IntArray(0)
    while (r > l + 1) {
        var m = (l + r) / 2
        val c = IntArray(m)
        for (i in 0 until m) {
            if (i % 2 == 0) {
                c[i] = a[i / 2]
            } else {
                c[i] = a[n - m / 2 + i / 2]
            }
        }
        var ok = true
        for (i in 0 until m - 1) {
            if (c[i] == c[i + 1]) {
                ok = false
            }
        }
        if (!ok && m % 2 == 0) {
            for (i in 0 until m step 2) {
                val t = c[i]
                c[i] = c[i + 1]
                c[i + 1] = t
            }
            ok = true
            for (i in 0 until m - 1) {
                if (c[i] == c[i + 1]) {
                    ok = false
                }
            }
        }
        if (ok) {
            l = m
            best = c
        } else {
            r = m
        }
    }
    return best
}

private fun solveTest() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    a.sort()
    val best1 = solve(a)
    a.reverse()
    val best2 = solve(a)
    val best = if (best1.size > best2.size) best1 else best2
    println(best.size)
    println(best.joinToString(" "))
}

fun main() {
    val n = readLine()!!.toInt()
    for (i in 0 until n) {
        solveTest()
    }
}

import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

/**
 * @author: pashka
 */

val MOD = 998244353L

internal class SegmentTree(private val size: Int) {

    private val sum = LongArray(4 * size)
    private val add = LongArray(4 * size)
    private val mult = LongArray(4 * size)

    public fun add(l: Int, r: Int, c: Long) {
        add(0, 0, size, l, r, c)
    }

    private fun add(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) {
        push(n, ll, rr)
        if (ll >= l && rr <= r) {
            add[n] += c
            sum[n] += c * (rr - ll)
            add[n] %= MOD
            sum[n] %= MOD
        } else if (ll >= r || l >= rr) {
            return
        } else {
            val m = (ll + rr) / 2
            add(n * 2 + 1, ll, m, l, r, c)
            add(n * 2 + 2, m, rr, l, r, c)
            sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD
        }
    }

    public fun mult(l: Int, r: Int, c: Long) {
        mult(0, 0, size, l, r, c)
    }

    private fun mult(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) {
        push(n, ll, rr)
        if (ll >= l && rr <= r) {
            mult[n] *= c
            add[n] *= c
            sum[n] *= c
            mult[n] %= MOD
            add[n] %= MOD
            sum[n] %= MOD
        } else if (ll >= r || l >= rr) {
            return
        } else {
            val m = (ll + rr) / 2
            mult(n * 2 + 1, ll, m, l, r, c)
            mult(n * 2 + 2, m, rr, l, r, c)
            sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD
        }
    }

    private fun push(n: Int, ll: Int, rr: Int) {
        if (rr - ll > 1) {
            val m = ll + rr shr 1
            for (i in 1..2) {
                mult[2 * n + i] *= mult[n]
                add[2 * n + i] *= mult[n]
                sum[2 * n + i] *= mult[n]
                add[2 * n + i] += add[n]
                sum[2 * n + i] += add[n] * (if (i == 1) (m - ll) else (rr - m))
                mult[2 * n + i] %= MOD
                add[2 * n + i] %= MOD
                sum[2 * n + i] %= MOD
            }
        }
        add[n] = 0
        mult[n] = 1
    }

    public fun sum(l: Int, r: Int): Long {
        return sum(0, 0, size, l, r)
    }

    private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Long {
        push(n, ll, rr)
        if (ll >= l && rr <= r) {
            return sum[n]
        } else if (ll >= r || l >= rr) {
            return 0
        } else {
            val m = (ll + rr) / 2
            return (sum(n * 2 + 1, ll, m, l, r) + sum(n * 2 + 2, m, rr, l, r)) % MOD
        }
    }
}

private fun solve() {
    val n = nextInt()
    val l = IntArray(n)
    val r = IntArray(n)
    for (i in 0 until n) {
        l[i] = nextInt()
        r[i] = nextInt()
    }
    var all = l + r
    all.sort()
    var m = 1
    for (i in 1 until all.size) {
        if (all[i] != all[m - 1]) {
            all[m] = all[i]
            m++
        }
    }
    all = all.copyOf(m)
    for (i in 0 until n) {
        l[i] = all.binarySearch(l[i])
        r[i] = all.binarySearch(r[i])
    }
    val c = IntArray(2 * m)
    for (i in 0 until n) {
        c[l[i] * 2]++
        c[r[i] * 2 + 1]--
    }
    for (i in 1 until 2 * m) {
        c[i] += c[i - 1]
    }
    val q = IntArray(2 * m)
    var mm = 0
    for (i in 0 until 2 * m) {
        if (c[i] > 0) {
            q[i] = mm
            mm++
        }
    }
    m = mm
    for (i in 0 until n) {
        l[i] = q[2 * l[i]]
        r[i] = q[2 * r[i]]
    }
    var p = List(n) { x: Int -> x }.sortedBy { x: Int -> r[x] }
    val st = SegmentTree(m + 1)
    st.add(0, 1, 1)
    for (i in p) {
        st.mult(0, l[i], 2)
        val x = st.sum(l[i], r[i] + 2)
        st.add(r[i] + 1, r[i] + 2, x)
    }
    out.println(st.sum(m, m + 1))
}

fun main() {
    solve()
    out.close()
}

private var br = BufferedReader(InputStreamReader(System.`in`))
private var st: StringTokenizer? = null
private var out = PrintWriter(System.out)

@Throws(IOException::class)
private fun next(): String {
    while (st == null || !st!!.hasMoreTokens()) {
        st = StringTokenizer(br.readLine())
    }
    return st!!.nextToken()
}

@Throws(IOException::class)
private fun nextInt(): Int {
    return Integer.parseInt(next())
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, x, y;
	string s;
	cin >> n >> x >> y >> s;
	
	int ans = 0;
	for (int i = n - x; i < n; ++i) {
		if (i == n - y - 1) ans += s[i] != '1';
		else ans += s[i] != '0';
	}
	
	cout << ans << 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;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	
	int pos = 1;
	for (int i = 0; i < n; ++i) {
		if (a[i] >= pos) ++pos;
	}
	
	cout << pos - 1 << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

string s;
int n;
string res;

int main()
{
	cin >> n >> s;
	for(int i = 0; i < n; i++)
	{
		if(res.size() % 2 == 0 || res.back() != s[i])
			res.push_back(s[i]);
	}
	if(res.size() % 2 == 1) res.pop_back();
	cout << n - int(res.size()) << endl << res << 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 t;
	cin >> t;
	for (int i = 0; i < t; ++i) {

		int n;
		cin >> n;
		vector<long long> d(n);
		for (int i = 0; i < n; ++i) {
			cin >> d[i];
		}
		sort(d.begin(), d.end());
		long long x = d[0] * d[n - 1];
		
		vector<long long> dd;
		for (int i = 2; i * 1ll * i <= x; ++i) {
			if (x % i == 0) {
				dd.push_back(i);
				if (i != x / i) {
					dd.push_back(x / i);
				}
			}
		}
		sort(dd.begin(), dd.end());
		
		if (dd == d) {
			cout << x << endl;
		} else {
			cout << -1 << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	
	sort(b.begin(), b.end());
	vector<pair<long long, int>> val(n);
	for (int i = 0; i < n; ++i) {
		val[i].first = (i + 1) * 1ll * (n - i) * a[i];
		val[i].second = i;
	}
	sort(val.rbegin(), val.rend());
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = (ans + (val[i].first % MOD * 1ll * b[i]) % MOD) % MOD;
	}
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<pair<int, int>> q(1001);

bool can(int day) {
	vector<int> lst(n, -1);
	for (int i = 0; i < m; ++i) {
		if (q[i].first <= day) {
			lst[q[i].second] = max(lst[q[i].second], q[i].first);
		}
	}
	vector<vector<int>> off(1001);
	for (int i = 0; i < n; ++i) {
		if (lst[i] != -1) {
			off[lst[i]].push_back(i);
		}
	}
	vector<int> need = k;
	int cur_money = 0;
	for (int i = 0; i <= day; ++i) {
		++cur_money;
		if (i > 1000) continue;
		for (auto it : off[i]) {
			if (cur_money >= need[it]) {
				cur_money -= need[it];
				need[it] = 0;
			} else {
				need[it] -= cur_money;
				cur_money = 0;
				break;
			}
		}
	}
	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	k = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first >> q[i].second;
		--q[i].first;
		--q[i].second;
	}
	
	for (int l = 0; l <= 2000; ++l) {
		if (can(l)) {
			cout << l + 1 << endl;
			return 0;
		}
	}
	
	assert(false);
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<pair<int, int>> q(200001);

bool can(int day) {
	vector<int> lst(n, -1);
	for (int i = 0; i < m; ++i) {
		if (q[i].first <= day) {
			lst[q[i].second] = max(lst[q[i].second], q[i].first);
		}
	}
	vector<vector<int>> off(200001);
	for (int i = 0; i < n; ++i) {
		if (lst[i] != -1) {
			off[lst[i]].push_back(i);
		}
	}
	vector<int> need = k;
	int cur_money = 0;
	for (int i = 0; i <= day; ++i) {
		++cur_money;
		if (i > 200000) continue;
		for (auto it : off[i]) {
			if (cur_money >= need[it]) {
				cur_money -= need[it];
				need[it] = 0;
			} else {
				need[it] -= cur_money;
				cur_money = 0;
				break;
			}
		}
	}
	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	k = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first >> q[i].second;
		--q[i].first;
		--q[i].second;
	}
	
	int l = 0, r = 400000;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) r = mid;
		else l = mid;
	}
	
	for (int i = l; i <= r; ++i) {
		if (can(i)) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	
	assert(false);
	
	return 0;
}

def f(x):
	x += 1
	while(x % 10 == 0):
		x //= 10
	return x

a = set()
n = int(input())

while(not(n in a)):
	a.add(n)
	n = f(n)

print(len(a))

#include<bits/stdc++.h>

using namespace std;

int f[10];
string s;

int main()
{
	int n;
	cin >> n;
	cin >> s;
	for(int i = 1; i <= 9; i++)
		cin >> f[i];
	vector<int> diff;
	for(int i = 0; i < n; i++)
		diff.push_back(f[s[i] - '0'] - (s[i] - '0'));
	for(int i = 0; i < n; i++)
		if(diff[i] > 0)
		{
			while(i < n && diff[i] >= 0)
			{
				s[i] = char(f[s[i] - '0'] + '0');
				i++;
			}
			break;
		}
	cout << s << 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;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << 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;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2 && cur[0].first != cur[1].first) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else if (int(cur.size()) == 2) {
			int cl = 1, cr = 1;
			while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl;
			while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr;
			if (cl > cr) {
				res += string(cl, 'L');
			} else {
				res += string(cr, 'R');
			}
			break;
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << 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, k;
	cin >> n >> k;
	if (n < k * 1ll * (k + 1) / 2) {
		cout << "NO" << endl;
		return 0;
	}
	
	int nn = n - k * (k + 1) / 2;
	vector<int> a(k);
	for (int i = 0; i < k; ++i) {
		a[i] = i + 1 + (nn / k) + (i >= k - nn % k);
	}
	
	if (nn != k - 1) {
		cout << "YES" << endl;
		for (int i = 0; i < k; ++i) cout << a[i] << " ";
		cout << endl;
	} else {
		if (k > 3) {
			--a[1];
			++a[k - 1];
		}
		if (k == 2 || k == 3) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			for (int i = 0; i < k; ++i) cout << a[i] << " ";
			cout << 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;
	cin >> n;
	vector<int> a(n);
	multiset<int> b;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		b.insert(x);
	}
	
	for (int i = 0; i < n; ++i) {
		auto it = b.lower_bound(n - a[i]);
		if (it == b.end()) it = b.begin();
		cout << (a[i] + *it) % n << " ";
		b.erase(it);
	}
	cout << 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;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(200 * 1000 + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	
	int l = 0, r = 0;
	int ans = cnt[a[0]];
	for (int i = 0; i < int(a.size()); ++i) {
		int j = i + 1;
		int sum = cnt[a[i]];
		while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) {
			sum += cnt[a[j]];
			++j;
		}
		int cr = j - 1;
		if (j < n && a[j] - a[j - 1] == 1) {
			sum += cnt[a[j]];
			cr = j;
		}
		if (ans < sum) {
			ans = sum;
			l = i;
			r = cr;
		}
		i = j - 1;
	}
	
	cout << ans << endl;
	for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " ";
	for (int i = l + 1; i < r; ++i) {
		for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " ";
	}
	for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " ";
	for (int i = r - 1; i > l; --i) cout << a[i] << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;

void invRow(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < m; ++pos) {
		a[idx][pos] ^= 1;
	}
}

void invCol(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < n; ++pos) {
		a[pos][idx] ^= 1;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	
	for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
		string r(n, '0');
		string c(m, '0');
		vector<vector<int>> b = a;
		for (int j = 0; j < m; ++j) {
			if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) {
				invCol(b, j);
				c[j] = '1';
			}
		}
		bool ok = true;
		if (cnt0 < m) {
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					ok = false;
				} else if (sum == 0) {
					invRow(b, i);
					r[i] = '1';
				}
			}
		} else {
			int idx = -1;
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					if (idx != -1) ok = false;
					else idx = i;
				}
			}
			if (idx == -1) {
				for (int i = 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			} else {
				for (int i = 1; i < idx; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == m) {
						invRow(b, i);
						r[i] = '1';
					}
				}
				if (b[idx][0] == 1) {
					invRow(b, idx);
					r[idx] = '1';
				}
				for (int j = 1; j < m; ++j) {
					if (b[idx][j] < b[idx][j - 1]) {
						ok = false;
					}
				}
				for (int i = idx + 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			}
		}
		if (ok) {
			cout << "YES" << endl << r << endl << c << endl;
			return 0;
		}
	}
	
	cout << "NO" << 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
	
	vector<int> a(4);
	for (int i = 0; i < 4; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	cout << a[3] - a[0] << " " << a[3] - a[1] << " " << a[3] - a[2] << 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;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	if (a.size() > 3) {
		cout << -1 << endl;
	} else {
		if (a.size() == 1) {
			cout << 0 << endl;
		} else if (a.size() == 2) {
			if ((a[1] - a[0]) % 2 == 0) {
				cout << (a[1] - a[0]) / 2 << endl;
			} else {
				cout << a[1] - a[0] << endl;
			}
		} else {
			if (a[1] - a[0] != a[2] - a[1]) {
				cout << -1 << endl;
			} else {
				cout << a[1] - a[0] << 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
	
	vector<int> a(3);
	cin >> a[0] >> a[1] >> a[2];
	
	vector<int> idx({0, 1, 2, 0, 2, 1, 0});
	
	int full = min({a[0] / 3, a[1] / 2, a[2] / 2});
	a[0] -= full * 3;
	a[1] -= full * 2;
	a[2] -= full * 2;
	
	int ans = 0;
	for (int start = 0; start < 7; ++start) {
		int day = start;
		vector<int> b = a;
		int cur = 0;
		while (b[idx[day]] > 0) {
			--b[idx[day]];
			day = (day + 1) % 7;
			++cur;
		}
		ans = max(ans, full * 7 + cur);
	}
	
	cout << ans << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int a, b, maxa;

void use_battery(int s)
{
	if(s == 1) a = min(a + 1, maxa);
	--b;	
}

void use_accum()
{
	--a;
}

int main()
{
	int ans = 0;
	int n;
	cin >> n >> b >> a;
	maxa = a;
	vector<int> s(n);
	for(int i = 0; i < n; i++) cin >> s[i];
	for(int i = 0; i < n; i++)
	{
		if(a == 0 && b == 0)
			break;
		else if(a == 0)
			use_battery(s[i]);
		else if(b == 0)
			use_accum();
		else if(s[i] == 1 && a < maxa)
			use_battery(s[i]);
		else use_accum();
		ans++;
	}
	cout << ans << 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<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first;
		a[i].second = i;
	}
	
	sort(a.rbegin(), a.rend());
	queue<int> q;
	for (int i = 0; i < n; ++i) {
		q.push(a[i].second);
	}
	
	set<int> idx;
	for (int i = 0; i < n; ++i) {
		idx.insert(i);
	}
	string ans(n, '0');
	int who = 0;
	while (!idx.empty()) {
		while (!idx.count(q.front())) {
			q.pop();
		}
		int pos = q.front();
		q.pop();
		
		vector<int> add;
		auto it = idx.find(pos);
		for (int i = 0; i <= k; ++i) {
			add.push_back(*it);
			if (it == idx.begin()) break;
			--it;
		}
		it = next(idx.find(pos));
		for (int i = 0; i < k; ++i) {
			if (it == idx.end()) break;
			add.push_back(*it);
			++it;
		}
		for (auto it : add) {
			idx.erase(it);
			ans[it] = '1' + who;
		}
		who ^= 1;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

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.begin(), a.end());
	a.resize(k);
	reverse(a.begin(), a.end());
	
	vector<int> offers(k + 1);
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		if (x <= k) {
			offers[x] = max(offers[x], y);
		}
	}
	
	vector<int> pref(k + 1);
	for (int i = 0; i < k; ++i) {
		pref[i + 1] = pref[i] + a[i];
	}
	
	vector<int> dp(k + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < k; ++i) {
		dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
		for (int j = 1; j <= k; ++j) {
			if (offers[j] == 0) continue;
			if (i + j > k) break;
			dp[i + j] = min(dp[i + j], dp[i] + pref[i + j - offers[j]] - pref[i]);
		}
	}
	
	cout << dp[k] << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 10 * 1000 * 1000 + 11;

int n;
vector<int> a;

int mind[N];

pair<int, int> mins[N];
vector<pair<int, int>> divs;

void build_sieve() {
	vector<int> pr;
	mind[0] = mind[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (mind[i] == 0) {
			pr.push_back(i);
			mind[i] = i;
		}
		for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) {
			mind[i * pr[j]] = pr[j];
		}
	}
}


void add_to_mins(int curd, int idx) {
    if(mins[curd].first == -1)
        mins[curd].first = idx;
    else if(mins[curd].second == -1)
        mins[curd].second = idx;
}

void rec(int pos, int curd, int idx) {
	if (pos == int(divs.size())) {
		add_to_mins(curd, idx);
		return;
	}
	int curm = 1;
	for (int i = 0; i <= divs[pos].second; ++i) {
		rec(pos + 1, curd * curm, idx);
		curm *= divs[pos].first;
	}
}

void add(int idx) {
	int value = a[idx];
	divs.clear();
	while (value > 1) {
		int d = mind[value];
		if (!divs.empty() && divs.back().first == d) {
			++divs.back().second;
		} else {
			divs.push_back(make_pair(d, 1));
		}
		value /= d;
	}
	rec(0, 1, idx);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for(int i = 0; i < N; i++)
	    mins[i] = make_pair(-1, -1);
	build_sieve();
	
	vector<pair<int, int> > vals;
	for(int i = 0; i < n; i++)
	    vals.push_back(make_pair(a[i], i));
	sort(vals.begin(), vals.end());
	for (int i = 0; i < n; ++i) {
	    if(i > 1 && vals[i].first == vals[i - 2].first) continue;
		add(vals[i].second);
	}
	
	long long l = INF * 1ll * INF;
	int ansi = -1, ansj = -1;
	for (int i = 1; i < N; ++i) {
		pair<int, int> idxs = mins[i];
		if (idxs.second == -1) continue;
		long long curl = a[idxs.first] * 1ll * a[idxs.second] / i;
		if (l > curl) {
			l = curl;
			ansi = min(idxs.first, idxs.second);
			ansj = max(idxs.first, idxs.second);
		}
	}
	
	cout << ansi + 1 << " " << ansj + 1 << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int n;
    cin >> n;
    forn(i, n) {
        string s;
        cin >> s;
        if (set<char>(s.begin(), s.end()).size() == s.length()
                && *max_element(s.begin(), s.end()) == char(*min_element(s.begin(), s.end()) + (s.length() - 1)))
            cout << "Yes" << endl;
        else
            cout << "No" << 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;
	cin >> n;
	int sum = 0;
	vector<int> even, odd;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		sum += x;
		if (x & 1) odd.push_back(x);
		else even.push_back(x);
	}
	
	sort(odd.rbegin(), odd.rend());
	sort(even.rbegin(), even.rend());
	int k = min(odd.size(), even.size());
	int rem = sum;
	rem -= accumulate(odd.begin(), odd.begin() + k, 0);
	rem -= accumulate(even.begin(), even.begin() + k, 0);
	if (int(odd.size()) > k) {
		rem -= odd[k];
	}
	if (int(even.size()) > k) {
		rem -= even[k];
	}
	
	cout << rem << 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;
	cin >> n;
	vector<int> cnt(200 * 1000 + 1);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
		if (cnt[x] > 2) {
			cout << "NO" << endl;
			return 0;
		}
	}
	
	cout << "YES" << endl << count(cnt.begin(), cnt.end(), 2) << endl;
	for (int i = 0; i <= 200 * 1000; ++i) {
		if (cnt[i] == 2) {
			cout << i << " ";
			--cnt[i];
		}
	}
	cout << endl << count(cnt.begin(), cnt.end(), 1) << endl;
	for (int i = 200 * 1000; i >= 0; --i) {
		if (cnt[i] == 1) {
			cout << i << " ";
			--cnt[i];
		}
	}
	cout << endl;
	
	assert(count(cnt.begin(), cnt.end(), 0) == 200 * 1000 + 1);
	
	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;
	cin >> n;
	
	vector<int> a(n), cnt(200 * 1000 + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	
	int val = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	int pos = find(a.begin(), a.end(), val) - a.begin();
	
	cout << n - cnt[val] << endl;
	int siz = 0;
	for (int i = pos - 1; i >= 0; --i) {
		cout << 1 + (a[i] > a[i + 1]) << " " << i + 1 << " " << i + 2 << " " << endl;
		a[i] = a[i + 1];
		++siz;
	}
	for (int i = 0; i < n - 1; ++i) {
		if (a[i + 1] != val) {
			assert(a[i] == val);
			cout << 1 + (a[i + 1] > a[i]) << " " << i + 2 << " " << i + 1 << " " << endl;
			a[i + 1] = a[i];
			++siz;
		}
	}
	
	assert(siz == n - cnt[val]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<int> get(const string &s) {
	vector<int> res(s.size() + 1);
	for (int i = 0; i < int(s.size()); ++i) {
		res[i + 1] = s[i] - 'a';
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int k;
	string s, t;
	cin >> k >> s >> t;
	vector<int> a = get(s), b = get(t);
	
	for (int i = k; i >= 0; --i) {
		a[i] += b[i];
		if (i) {
			a[i - 1] += a[i] / 26;
			a[i] %= 26;
		}
	}
	
	for (int i = 0; i <= k; ++i) {
		int rem = a[i] % 2;
		a[i] /= 2;
		if (i + 1 <= k) {
			a[i + 1] += rem * 26;
		} else {
			assert(rem == 0);
		}
	}
	
	for (int i = 1; i <= k; ++i) {
		cout << char('a' + a[i]);
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 11;

int n, m;
vector<int> g[N];
vector<pair<int, int>> e;

bool bipartite;
vector<int> color;

void dfs(int v, int c) {
	color[v] = c;
	for (auto to : g[v]) {
		if (color[to] == -1) {
			dfs(to, c ^ 1);
		} else {
			if (color[to] == color[v]) {
				bipartite = false;
			}
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	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);
		e.push_back(make_pair(x, y));
	}
	
	bipartite = true;
	color = vector<int>(n, -1);
	dfs(0, 0);
	
	if (!bipartite) {
		cout << "NO" << endl;
		return 0;
	}
	
	cout << "YES" << endl;
	for (int i = 0; i < m; ++i) {
		cout << (color[e[i].first] < color[e[i].second]);
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	vector<vector<int>> dp(n, vector<int>({-INF, INF}));
	vector<vector<int>> p(n, vector<int>(2, -1));
	dp[0][0] = INF;
	dp[0][1] = -INF;
	
	for (int i = 1; i < n; ++i) {
		{
			if (a[i] > a[i - 1] && dp[i][0] < dp[i - 1][0]) {
				dp[i][0] = dp[i - 1][0];
				p[i][0] = 0;
			}
			if (a[i] < dp[i - 1][0] && dp[i][1] > a[i - 1]) {
				dp[i][1] = a[i - 1];
				p[i][1] = 0;
			}
		}
		{
			if (a[i] < a[i - 1] && dp[i][1] > dp[i - 1][1]) {
				dp[i][1] = dp[i - 1][1];
				p[i][1] = 1;
			}
			if (a[i] > dp[i - 1][1] && dp[i][0] < a[i - 1]) {
				dp[i][0] = a[i - 1];
				p[i][0] = 1;
			}
		}
	}
	
	int pos = -1;
	if (dp[n - 1][0] != -INF) {
		pos = 0;
	}
	if (dp[n - 1][1] != INF) {
		pos = 1;
	}
	
	if (pos == -1) {
		cout << "NO" << endl;
		return 0;
	}
	
	vector<int> inInc(n);
	for (int i = n - 1; i >= 0; --i) {
		if (pos == 0) {
			inInc[i] = 1;
		}
		pos = p[i][pos];
	}
	
	cout << "YES" << endl;
	for (int i = 0; i < n; ++i) {
		cout << !inInc[i] << " ";
	}
	cout << 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 h1, m1;
	scanf("%d:%d", &h1, &m1);
	int h2, m2;
	scanf("%d:%d", &h2, &m2);
	int t1 = h1 * 60 + m1;
	int t2 = h2 * 60 + m2;
	int t3 = (t1 + t2) / 2;
	printf("%02d:%02d\n", t3 / 60, t3 % 60);
	
	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, k;
	cin >> n >> k;
	vector<int> cnt(k);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x % k];
	}
	int ans = cnt[0] / 2;
	if (k % 2 == 0) ans += cnt[k / 2] / 2;
	for (int i = 1; i < (k + 1) / 2; ++i) {
		int j = k - i;
		ans += min(cnt[i], cnt[j]);
	}
	
	cout << ans * 2 << 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;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int ans = 0;
	int j = 0;
	for (int i = 0; i < n; ++i) {
		while (j < n && a[j] - a[i] <= 5) {
			++j;
			ans = max(ans, j - i);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 200043;

void norm(pair<int, int>& p)
{
	if(p.x < 0)
	{
		p.x *= -1;
		p.y *= -1;
	}
	else if (p.x == 0 && p.y < 0)
	{
		p.y *= -1;
	}
	int d = __gcd(abs(p.x), abs(p.y));
	p.x /= d;
	p.y /= d;
}

map<pair<int, int>, int> m;

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

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < n; i++)
		scanf("%d", &b[i]);
	int ans = 0;
	int cnt0 = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			if(b[i] == 0)
				cnt0++;
		}
		else
		{
			pair<int, int> p = make_pair(-b[i], a[i]);
			norm(p);
			m[p]++;
			ans = max(ans, m[p]);
		}
	}
	cout << cnt0 + ans << 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];
	}
	sort(a.begin(), a.end());
	vector<int> cnt(n);
	for (int i = 0; i < n; ++i) {
		while (i + cnt[i] < n && a[i + cnt[i]] - a[i] <= 5) {
			++cnt[i];
		}
	}
	
	vector<vector<int>> dp(n + 1, vector<int>(k + 1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= k; ++j) {
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
			if (j + 1 <= k) {
				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]);
			}
		}
	}
	
	cout << dp[n][k] << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int>> g;
vector<int> deg, used;
vector<pair<int, int>> ans;

mt19937 rnd(time(NULL));

void bfs(int s) {
	used = vector<int>(n);
	used[s] = 1;
	queue<int> q;
	q.push(s);
	
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto to : g[v]) {
			if (used[to]) continue;
			if (rnd() & 1) ans.push_back(make_pair(v, to));
			else ans.push_back(make_pair(to, v));
			used[to] = 1;
			q.push(to);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	g = vector<vector<int>>(n);
	deg = vector<int>(n);
	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);
		++deg[x];
		++deg[y];
	}
	
	int pos = 0;
	for (int i = 0; i < n; ++i) {
		if (deg[pos] < deg[i]) {
			pos = i;
		}
	}
	
	bfs(pos);
	shuffle(ans.begin(), ans.end(), rnd);
	for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m, D;
vector<vector<int>> g;

int cnt;
vector<int> p, color;
vector<pair<int, int>> ans;

mt19937 rnd(time(NULL));

void bfs(int s, int bad) {
	queue<int> q;
	q.push(s);
	color[s] = cnt;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		if (p[v] != -1) {
			if (rnd() & 1) ans.push_back(make_pair(p[v], v));
			else ans.push_back(make_pair(v, p[v]));
		}
		for (auto to : g[v]) {
			if (to == bad || color[to] != -1) continue;
			p[to] = v;
			color[to] = cnt;
			q.push(to);
		}
	}
	++cnt;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> D;
	g = vector<vector<int>>(n);
	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);
	}
	
	p = color = vector<int>(n, -1);
	cnt = 0;
	for (int i = 1; i < n; ++i) {
		if (color[i] == -1) {
			bfs(i, 0);
		}
	}
	
	if (cnt > D || D > int(g[0].size())) {
		cout << "NO" << endl;
		return 0;
	}
	
	sort(g[0].begin(), g[0].end(), [](int a, int b) {
		return color[a] < color[b];
	});
	
	for (int i = 0; i < int(g[0].size()); ++i) {
		if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
			ans.push_back(make_pair(0, g[0][i]));
		}
	}
	D -= cnt;
	for (int i = 1; i < int(g[0].size()); ++i) {
		if (D == 0) break;
		if (color[g[0][i]] == color[g[0][i - 1]]) {
			ans.push_back(make_pair(0, g[0][i]));
			--D;
		}
	}
	
	g = vector<vector<int>>(n);
	for (auto it : ans) {
		g[it.first].push_back(it.second);
		g[it.second].push_back(it.first);
	}
	ans.clear();
	p = color = vector<int>(n, -1);
	cnt = 0;
	bfs(0, -1);
	
	shuffle(ans.begin(), ans.end(), rnd);
	cout << "YES" << endl;
	for (auto it : ans) {
		cout << it.first + 1 << " " << it.second + 1 << 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 q;
	cin >> q;
	
	for (int i = 0; i < q; ++i) {
		long long n;
		int a, b;
		cin >> n >> a >> b;
		cout << (n / 2) * min(2 * a, b) + (n % 2) * a << 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;
	cin >> n;
	
	vector<int> a(n);
	
	int ePref = 0, oPref = 0, eSuf = 0, oSuf = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (i & 1) eSuf += a[i];
		else oSuf += a[i];
	}
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (i & 1) eSuf -= a[i];
		else oSuf -= a[i];
		if (ePref + oSuf == oPref + eSuf) {
			++ans;
		}
		if (i & 1) ePref += a[i];
		else oPref += a[i];
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> pt;

const int N = 1000 + 7;

int cnt[N];
int a[20][20];

int main() {
	int n;
	scanf("%d", &n);
	forn(i, n * n){
		int x;
		scanf("%d", &x);
		++cnt[x];
	}
	
	vector<pair<int, pt>> cells;
	forn(i, (n + 1) / 2) forn(j, (n + 1) / 2){
		if (i != n - i - 1 && j != n - j - 1)
			cells.push_back({4, {i, j}});
		else if ((i != n - i - 1) ^ (j != n - j - 1))
			cells.push_back({2, {i, j}});
		else
			cells.push_back({1, {i, j}});
	}
	
	for (auto cur : {4, 2, 1}){
		int lst = 1;
		for (auto it : cells){
			if (it.first != cur) continue;
			int i = it.second.first;
			int j = it.second.second;
			while (lst < N && cnt[lst] < cur)
				++lst;
			if (lst == N){
				puts("NO");
				return 0;
			}
			a[i][j] = a[n - i - 1][j] = a[i][n - j - 1] = a[n - i - 1][n - j - 1] = lst;
			cnt[lst] -= cur;
		}
	}
	
	puts("YES");
	forn(i, n){
		forn(j, n)
			printf("%d ", a[i][j]);
		puts("");
	}
	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<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	for (int i = 1; i <= n; ++i) {
		int sum = 0;
		for (int j = 0; j < n; ++j) {
			sum += max(a[j] - j / i, 0);
		}
		if (sum >= m) {
			cout << i << endl;
			return 0;
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> a;

bool can(int i) {
	long long sum = 0; // there can be a bug
	for (int j = 0; j < n; ++j) {
		sum += max(a[j] - j / i, 0);
	}
	return sum >= m;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	int l = 1, r = n;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) r = mid;
		else l = mid;
	}
	
	if (can(l)) cout << l << endl;
	else if (can(r)) cout << r << endl;
	else cout << -1 << 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, k;
	cin >> n >> k;
	
	if (n > k * 1ll * (k - 1)) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
		int cur = 0;
		for (int i = 0; i < n; ++i) {
			cur += (i % k == 0);
			cout << i % k + 1 << " " << (cur + i % k) % k + 1 << 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 = 300 * 1000 + 13;

int n;
int a[N];
vector<int> g[N];
int red, blue;
int ans;

pair<int, int> dfs(int v, int p = -1){
	int r = (a[v] == 1), b = (a[v] == 2);
	for (auto u : g[v]) if (u != p){
		auto tmp = dfs(u, v);
		ans += (tmp.first == red && tmp.second == 0);
		ans += (tmp.first == 0 && tmp.second == blue);
		r += tmp.first;
		b += tmp.second;
	}
	return make_pair(r, b);
}

int main() {
	int n;
	scanf("%d", &n);
	
	forn(i, n){
		scanf("%d", &a[i]);
		red += (a[i] == 1);
		blue += (a[i] == 2);
	}
	
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	ans = 0;
	dfs(0);
	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 = 300 * 1000 + 13;
const int LOGN = 19;
const int MOD = 998244353;

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 a[N];
vector<int> g[N];
int up[N][LOGN];
int d[N];

void init(int v, int p = -1){
	for (auto u : g[v]) if (u != p){
		up[u][0] = v;
		for (int i = 1; i < LOGN; ++i)
			up[u][i] = up[up[u][i - 1]][i - 1];
		d[u] = d[v] + 1;
		init(u, v);
	}
}

int lca(int v, int u){
	if (d[v] < d[u]) swap(v, u);
	for (int i = LOGN - 1; i >= 0; --i)
		if (d[up[v][i]] >= d[u])
			v = up[v][i];
	if (v == u) return v;
	for (int i = LOGN - 1; i >= 0; --i)
		if (up[v][i] != up[u][i]){
			v = up[v][i];
			u = up[u][i];
		}
	return up[v][0];
}

int l[N];
int dp[N][2];

int dfs(int v, int p = -1){
	vector<pair<int, int>> cur;
	for (auto u : g[v]) if (u != p){
		int c = dfs(u, v);
		if (c != 0)
			cur.push_back(make_pair(c, u));
	}
	
	vector<int> vals;
	forn(i, cur.size()) if (cur[i].first > 0)
		vals.push_back(cur[i].first);
	
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	
	if (int(vals.size()) > 1){
		puts("0");
		exit(0);
	}
	
	if (a[v] != 0 && !vals.empty() && vals[0] != a[v]){
		puts("0");
		exit(0);
	}
	
	if (a[v] == 0 && cur.empty())
		return 0;
	
	if (a[v] == 0 && vals.empty()){		
		vector<int> pr(1, 1), su(1, 1);
		forn(i, cur.size())
			pr.push_back(mul(pr.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
		for (int i = int(cur.size()) - 1; i >= 0; --i)
			su.push_back(mul(su.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
		reverse(su.begin(), su.end());
		dp[v][1] = 0;
		forn(i, cur.size())
			dp[v][1] = add(dp[v][1], mul(mul(pr[i], su[i + 1]), dp[cur[i].second][1]));
		dp[v][0] = add(dp[v][0], pr[cur.size()]);
		return -1;
	}
	
	dp[v][1] = 1;
	for (auto it : cur){
		if (it.first == -1)
			dp[v][1] = mul(dp[v][1], add(dp[it.second][0], dp[it.second][1]));	
		else
			dp[v][1] = mul(dp[v][1], dp[it.second][1]);
	}
	
	if (a[v] == 0)
		return vals[0];
	
	return (l[a[v]] == v ? -1 : a[v]);
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	forn(i, n)
		scanf("%d", &a[i]);
	
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	init(0);
	
	memset(l, -1, sizeof(l));
	forn(i, n) if (a[i] != 0)
		l[a[i]] = (l[a[i]] == -1 ? i : lca(l[a[i]], i));
	
	for (int i = 1; i <= k; ++i){
		if (a[l[i]] != 0 && a[l[i]] != i){
			puts("0");
			exit(0);
		}
		a[l[i]] = i;
	}
	
	dfs(0);
	
	printf("%d\n", dp[0][1]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		vector<int>a({l1, r1, l2, r2});
		int ans1 = 0, ans2 = 0;
		for (auto it : a) for (auto jt : a) {
			if (l1 <= it && it <= r1 && l2 <= jt && jt <= r2 && it != jt) {
				ans1 = it;
				ans2 = jt;
			}
		}
		cout << ans1 << " " << ans2 << 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;
	cin >> n;
	multiset<int> a;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		a.insert(x);
	}
	
	int x = *prev(a.end());
	for (int i = 1; i <= x; ++i) {
		if (x % i == 0) {
			a.erase(a.find(i));
		}
	}
	
	cout << x << " " << *prev(a.end()) << 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;
	string s;
	cin >> n >> s;
	
	vector<int> p(3);
	iota(p.begin(), p.end(), 0);
	
	string colors = "RGB";
	string res = "";
	int ans = 1e9;
	
	do {
		string t;
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			t += colors[p[i % 3]];
			cnt += t[i] != s[i];
		}
		if (ans > cnt) {
			ans = cnt;
			res = t;
		}
	} while (next_permutation(p.begin(), p.end()));
	
	cout << ans << endl << res << 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;
	string s;
	cin >> n >> s;
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int j = i;
		while (j < n && s[i] == s[j]) {
			++j;
		}
		string q = "RGB";
		q.erase(q.find(s[i]), 1);
		if (j < n) q.erase(q.find(s[j]), 1);
		for (int k = i + 1; k < j; k += 2) {
			++ans;
			s[k] = q[0];
		}
		i = j - 1;
	}
	
	cout << ans << endl << s << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(time(NULL));

const int INF = 1e9;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<pair<int, int>> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> b[i].first >> b[i].second;
		--b[i].first;
		--b[i].second;
	}
	
	int ans = *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end());
	vector<int> res;
	for (int i = 0; i < n; ++i) {
		vector<int> add(n + 1);
		vector<int> cur;
		for (int j = 0; j < m; ++j) {
			if (!(b[j].first <= i && i <= b[j].second)) {
				cur.push_back(j);
				for (int k = b[j].first; k <= b[j].second; ++k) {
					--add[k];
				}
			}
		}
		int mn = INF, mx = -INF;
		for (int j = 0; j < n; ++j) {
			mn = min(mn, a[j] + add[j]);
			mx = max(mx, a[j] + add[j]);
		}
		if (ans < mx - mn) {
			ans = mx - mn;
			res = cur;
		}
	}
	
	cout << ans << endl << res.size() << endl;
	shuffle(res.begin(), res.end(), rnd);
	for (auto it : res) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(time(NULL));

const int INF = 1e9;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<pair<int, int>> b(m);
	vector<vector<int>> lf(n), rg(n);
	for (int i = 0; i < m; ++i) {
		cin >> b[i].first >> b[i].second;
		--b[i].first;
		--b[i].second;
		lf[b[i].second].push_back(b[i].first);
		rg[b[i].first].push_back(b[i].second);
		}
	
	vector<int> ansv(n, -INF);
	
	vector<int> add(n + 1 , 0);
	int mn = a[0];
	
	for (int i = 0; i < n; ++i) {
		ansv[i] = max(ansv[i], a[i] - mn);
		for (auto l : lf[i]) {
			for (int j = l; j <= i; ++j) {
				--add[j];
				mn = min(mn, a[j] + add[j]);
			}
		}
		mn = min(mn, a[i] + add[i]);
	}
	
	add = vector<int>(n + 1, 0);
	mn = a[n - 1];
	
	for (int i = n - 1; i >= 0; --i) {
		ansv[i] = max(ansv[i], a[i] - mn);
		for (auto r : rg[i]) {
			for (int j = i; j <= r; ++j) {
				--add[j];
				mn = min(mn, a[j] + add[j]);
			}
		}
		mn = min(mn, a[i] + add[i]);
	}
	
	int ans = *max_element(ansv.begin(), ansv.end());
	vector<int> res;
	
	for (int i = 0; i < n; ++i) {
		if (ansv[i] == ans) {
			for (int j = 0; j < m; ++j) {
				if (!(b[j].first <= i && i <= b[j].second)) {
					res.push_back(j);
				}
			}
			break;
		}
	}
	
	cout << ans << endl << res.size() << endl;
	shuffle(res.begin(), res.end(), rnd);
	for (auto it : res) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

vector<int> p, rk;

int getp(int v) {
	if (v == p[v]) return v;
	return p[v] = getp(p[v]);
}

bool merge(int v, int u) {
	u = getp(u);
	v = getp(v);
	
	if (u == v) return false;
	
	if (rk[u] < rk[v]) swap(u, v);
	
	rk[u] += rk[v];
	p[v] = u;
	
	return true;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	ios_base::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	
	p = vector<int>(n);
	iota(p.begin(), p.end(), 0);
	rk = vector<int>(n, 1);
	
	vector<pair<pair<int, int>, int>> e(m);
	for (int i = 0; i < m; ++i) {
		cin >> e[i].x.x >> e[i].x.y >> e[i].y;
		--e[i].x.x;
		--e[i].x.y;
	}
	
	sort(e.begin(), e.end(), [](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
		return a.y < b.y;
	});
	
	int ans = 0;
	for (int i = 0; i < m; ++i) {
		int j = i;
		while (j < m && e[i].y == e[j].y) {
			++j;
		}
		int cnt = j - i;
		for (int k = i; k < j; ++k) {
			if (getp(e[k].x.x) == getp(e[k].x.y)) {
				--cnt;
			}
		}
		for (int k = i; k < j; ++k) {
			cnt -= merge(e[k].x.x, e[k].x.y);
		}
		ans += cnt;
		i = j - 1;
	}
	
	cout << ans << 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;
	cin >> n;
	n %= 4;
	if (n == 0 || n == 3) {
		cout << 0 << endl;
	} else {
		cout << 1 << 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;
	cin >> n;
	long long sum = n * 1ll * (n + 1) / 2;
	cout << (sum & 1) << 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, k;
	cin >> n >> k;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first;
		a[i].second = i;	
	}
	
	sort(a.begin(), a.end());
	
	vector<vector<int>> buckets(k);
	vector<int> res(n);
	for (int i = 0; i < n; ++i) {
		buckets[i % k].push_back(a[i].first);
		res[a[i].second] = i % k;
	}
	
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < int(buckets[i].size()) - 1; ++j) {
			if (buckets[i][j] == buckets[i][j + 1]) {
				cout << "NO" << endl;
				return 0;
			}
		}
	}
	
	cout << "YES" << endl;
	for (int i = 0; i < n; ++i) {
		cout << res[i] + 1 << " ";
	}
	cout << 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, x, y;
	cin >> n >> x >> y;
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		int cur;
		cin >> cur;
		if (cur <= x) {
			++cnt;
		}
	}
	
	if (x > y) {
		cout << n << endl;
	} else {
		cout << (cnt + 1) / 2 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;

int needRep(const vector<int> &cnt, const vector<int> &need) {
	int res = 0;
	for (int i = 0; i < 3; ++i) {
		res += abs(cnt[i] - need[i]);
	}
	assert(res % 2 == 0);
	return res / 2;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> n >> s;
	
	vector<int> cnt(3), cur(3, n / 3);
	for (auto c : s) {
		++cnt[c - '0'];
	}
	
	int need = needRep(cnt, cur);
		
	int curRep = 0;
	for (int i = 0; i < n; ++i) {
		--cnt[s[i] - '0'];
		for (int j = 0; j < 3; ++j) {
			if (cur[j] == 0) continue;
			int rep = j != s[i] - '0';
			--cur[j];
			if (curRep + rep + needRep(cnt, cur) == need) {
				s[i] = j + '0';
				curRep += rep;
				break;
			}
			++cur[j];
		}
	}
	
	cout << s << endl;
	
	return 0;
}

n = int(input())
s = [ord(x) - ord('0') for x in input()]
cnt = [s.count(x) for x in [0, 1, 2]]
def forw(x):
	for i in range(n):
		if (cnt[x] < n // 3 and s[i] > x and cnt[s[i]] > n // 3):
			cnt[x] += 1
			cnt[s[i]] -= 1
			s[i] = x
def back(x):
	for i in range(n - 1, -1, -1):
		if (cnt[x] < n // 3 and s[i] < x and cnt[s[i]] > n // 3):
			cnt[x] += 1
			cnt[s[i]] -= 1
			s[i] = x
forw(0)
forw(1)
back(2)
back(1)
print(''.join([str(x) for x in s]))

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main()
{
 	int n;
 	scanf("%d", &n);
 	vector<int> a(n);
 	for(int i = 0; i < n; i++)
 		scanf("%d", &a[i]);
 	map<int, int> lst;
 	vector<int> last_pos(n);
 	for(int i = n - 1; i >= 0; i--)
 	{
 		if(!lst.count(a[i]))
 			lst[a[i]] = i;
 		last_pos[i] = lst[a[i]];
 	}
 	int ans = 1;
 	int cur_max = -1;
 	for(int i = 0; i < n - 1; i++)
 	{
 		cur_max = max(cur_max, last_pos[i]);
 		if(cur_max == i)
 			ans = (2 * ans) % MOD;
 	}	
 	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;

typedef long long li;

const int N = 18;
const int M = 100 * 1000 + 13;
const int INF = 1e9;

int dp[1 << N][N];

int n, m;
int a[N][M];
int mn1[N][N], mn2[N][N];

int calc(int mask, int v){
	if (dp[mask][v] != -1)
		return dp[mask][v];
	dp[mask][v] = 0;
	forn(u, n) if (v != u && ((mask >> u) & 1))
		dp[mask][v] = max(dp[mask][v], min(mn1[u][v], calc(mask ^ (1 << v), u)));
	return dp[mask][v];
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, n) forn(j, m)
		scanf("%d", &a[i][j]);
	
	forn(i, n) forn(j, n){
		int val = INF;
		forn(k, m)
			val = min(val, abs(a[i][k] - a[j][k]));
		mn1[i][j] = val;
		val = INF;
		forn(k, m - 1)
			val = min(val, abs(a[i][k] - a[j][k + 1]));
		mn2[i][j] = val;
	}
	
	int ans = 0;
	forn(i, n){
		memset(dp, -1, sizeof(dp));
		forn(j, n)
			dp[1 << j][j] = (j == i ? INF : 0);
		forn(j, n)
			ans = max(ans, min(mn2[j][i], calc((1 << n) - 1, j)));
	}
	
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 18;
const int M = 100 * 1000 + 13;
const int INF = 1e9;

int used[1 << N];
char dp[1 << N];
int g[1 << N];

int n, m;
int a[N][M];
int mn1[N][N], mn2[N][N];

bool calc(int mask){
	if (dp[mask] != -1)
		return dp[mask];
	used[mask] = 0;
	dp[mask] = 0;
	forn(i, n){
		if (!((mask >> i) & 1))
			continue;
		if (!calc(mask ^ (1 << i)))
			continue;
		if (!(used[mask ^ (1 << i)] & g[i]))
			continue;
		used[mask] |= (1 << i);
		dp[mask] = 1;
	}
	return dp[mask];
}

bool check(int k){
	forn(i, n){
		g[i] = 0;
		forn(j, n)
			g[i] |= (1 << j) * (mn1[j][i] >= k);
	}
	forn(i, n){
		memset(dp, -1, sizeof(dp));
		forn(j, n){
			dp[1 << j] = (j == i);
			used[1 << j] = (1 << j);
		}
		calc((1 << n) - 1);
		forn(j, n) if (mn2[j][i] >= k && ((used[(1 << n) - 1] >> j) & 1))
			return true;
	}
	return false;
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, n) forn(j, m)
		scanf("%d", &a[i][j]);
	
	forn(i, n) forn(j, n){
		int val = INF;
		forn(k, m)
			val = min(val, abs(a[i][k] - a[j][k]));
		mn1[i][j] = val;
		val = INF;
		forn(k, m - 1)
			val = min(val, abs(a[i][k] - a[j][k + 1]));
		mn2[i][j] = val;
	}
	
	int l = 0, r = INF;
	while (l < r - 1){
		int m = (l + r) / 2;
		if (check(m))
			l = m;
		else
			r = m;
	}
	
	printf("%d\n", check(r) ? r : l);
}