#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;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = int(2e9) + 99;

int n, x, y, d;

int dist(int x, int y){
	return (abs(x - y) + (d - 1)) / d;
}

int main() {
	
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
    	cin >> n >> x >> y >> d;
    	
    	int len = abs(x - y);
    	int res = INF;
    	
    	if(len % d == 0) 
    		res = min(res, dist(x, y));
    	
    	len = y - 1;
    	if(len % d == 0)
    		res = min(res, dist(x, 1) + dist(1, y));
    	
    	len = n - y;
    	if(len % d == 0)
    		res = min(res, dist(x, n) + dist(n, y));
    		
    	if(res == INF)
    		res = -1;
    	
    	cout << res << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
	
	cin >> n >> s;
	
	vector <int> l(n), r(n);
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G'){
			l[i] = 1;
			if(i > 0) l[i] += l[i - 1];
		}
	}
	for(int i = n - 1; i >= 0; --i){
		if(s[i] == 'G'){
			r[i] = 1;
			if(i + 1 < n) r[i] += r[i + 1];
		}
	}
	
	
	int res = 0;
	int cntG = 0;
	for(int i = 0; i < n; ++i)
			cntG += s[i] == 'G';
			
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G') continue;
		int nres = 1;
		if(i > 0) nres += l[i - 1];
		if(i + 1 < n) nres += r[i + 1];
		res = max(res, nres);
	}
	
	res = min(res, cntG);
	if(cntG == n) res = cntG;
	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())

int n, m;
vector<int> s, r;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	s.assign(n, 0);
	r.assign(n, 0);
	
	fore(i, 0, n) {
		assert(cin >> s[i] >> r[i]);
		s[i]--;
	}
	return true;
}

vector< vector<int> > subs;

inline void solve() {
	subs.assign(m + 1, vector<int>());
	
	fore(i, 0, n)
		subs[s[i]].push_back(r[i]);
		
	fore(id, 0, sz(subs)) {
		sort(subs[id].begin(), subs[id].end());
		reverse(subs[id].begin(), subs[id].end());
	}
	
	vector<int> mx(n + 5, 0);
	fore(id, 0, sz(subs)) {
		int curSum = 0;
		fore(i, 0, sz(subs[id])) {
			curSum += subs[id][i];
			if(curSum < 0)
				break;
				
			mx[i + 1] += curSum;
		}
	}
	
	cout << *max_element(mx.begin(), mx.end()) << 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>

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

using namespace std;

const int N = 1000 + 7;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d", &a[i]);
	
	int sum = 0;
	forn(i, n)
		sum += a[i];
	
	if (sum < 2 * n - 2){
		puts("NO");
		return 0;
	}
	
	vector<int> ones;
	forn(i, n) if (a[i] == 1){
		a[i] = 0;
		ones.push_back(i);
	}
	
	int t = ones.size();
	int dm = (n - t) - 1 + min(2, t);
	printf("YES %d\n%d\n", dm, n - 1);
	
	int lst = -1;
	if (!ones.empty()){
		lst = ones.back();
		ones.pop_back();
	}
	
	forn(i, n){
		if (a[i] > 1){
			if (lst != -1){
				--a[lst];
				--a[i];
				printf("%d %d\n", lst + 1, i + 1);
			}
			lst = i;
		}
	}
	
	for (int i = n - 1; i >= 0; --i){
		while (!ones.empty() && a[i] > 0){
			--a[i];
			printf("%d %d\n", i + 1, ones.back() + 1);
			ones.pop_back();
		}
	}
	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())

const int INF = int(1e9);

int n, c;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> c))
		return false;
	a.assign(n, 0);
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	return true;
}

vector<int> cntC;

int getCnt(int l, int r) {
	return cntC[r] - cntC[l];
}

vector< vector<int> > segs;
vector<int> lst;

int maxSegment(const vector<int> &s) {
	int mx = -INF;
	
	int bal = 0;
	fore(i, 0, sz(s)) {
		bal = max(0, bal + s[i]);
		mx = max(mx, bal);
	}
	return mx;
}

inline void solve() {
	cntC.assign(n + 1, 0);
	fore(i, 0, n)
		cntC[i + 1] = cntC[i] + (a[i] == c);
	
	int cntDif = *max_element(a.begin(), a.end()) + 1;
	segs.assign(cntDif, vector<int>());
	lst.assign(cntDif, -1);
	
	fore(i, 0, n) {
		segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
		lst[a[i]] = i;
		segs[a[i]].push_back(1);
	}
	fore(v, 0, cntDif)
		segs[v].push_back(-getCnt(lst[v] + 1, n));
		
	int ans = 0;
	fore(v, 0, cntDif) {
		if(v == c) continue;
		ans = max(ans, maxSegment(segs[v]));
	}
	
	cout << getCnt(0, n) + ans << 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>

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

using namespace std;

const int N = 500 + 7;
const int M = 11;
const int INF = 1e9;

struct node{
	int nxt[10];
	int cnt;
	node(){
		memset(nxt, -1, sizeof(nxt));
		cnt = 0;
	}
};

node trie[N];
int cnt;
int h[N];

void add(string s, int m){
	int cur = 0;
	forn(i, s.size()){
		int c = s[i] - '0';
		if (trie[cur].nxt[c] == -1){
			trie[cur].nxt[c] = cnt;
			h[cnt] = h[cur] + 1;
			++cnt;
		}
		cur = trie[cur].nxt[c];
	}
	trie[cur].cnt += m;
}

int n, k;

int dp[N][M][N];
int dp2[N][M][N][M];

int calc(int x, int rem, int k){
	if (dp[x][rem][k] != -1)
		return dp[x][rem][k];
	
	vector<int> ch;
	forn(i, 10) if (trie[x].nxt[i] != -1)
		ch.push_back(trie[x].nxt[i]);
	
	dp[x][rem][k] = INF;
	if (rem > 0)
		dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x));
	
	dp2[x][rem][k][ch.size()] = 0;
	for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1)
		dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]);
	
	dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt);
	
	return dp[x][rem][k];
}

int main() {
	trie[0] = node();
	cnt = 1;
	
	cin >> n >> k;
	forn(i, n){
		string s;
		int m;
		cin >> s >> m;
		add(s, m);
	}
	
	memset(dp, -1, sizeof(dp));
	
	forn(i, N) forn(j, M) forn(l, N) forn(t, M)
		dp2[i][j][l][t] = INF;
	
	int ans = calc(0, k, 0);
	
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 2009;
const int INF = int(1e9) + 777;

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

int n, m;
int s, t;
vector<edge> edges;
vector <int> g[N];
int u[N], cu;

void addEdge(int v, int to, int cap){

	g[v].push_back(edges.size());
	edges.push_back(edge(to, 0, cap));

	g[to].push_back(edges.size());
	edges.push_back(edge(v, 0, 0));
}

int dfs(int v, int need){
	if(v == t) return need;
	u[v] = cu;
	for(auto to : g[v]){
		edge &e = edges[to];
		if(u[e.to] != cu && e.c - e.f >= need){
			int add = dfs(e.to, need);
			if(add > 0){
				edges[to].f += add;
				edges[to ^ 1].f -= add;
				return add;
			}
		}
	}
	return 0;
}

li enlarge(int k){
	li res = 0;
	while(true){
		++cu;
		int add = dfs(s, k);
		res += add;
		if(add == 0) break;
	}
	return res;
}

li maxFlow(){
	li flow = 0;
	for(int k = (1 << 29); k > 0; k >>= 1){
		flow += enlarge(k);
	}
	return flow;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int nn, mm;
	cin >> nn >> mm;
	n = nn + mm + 5;
	m = nn + mm + mm + mm + 5;
	s = n - 1, t = n - 2;
	
	for(int i = 0; i < nn; ++i){
		int a;
		cin >> a;
		addEdge(i + mm, t, a);
	}

	li sum = 0;
	for(int i = 0; i < mm; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		sum += w;
		
		addEdge(s, i, w);
		addEdge(i, u + mm, INF);
		addEdge(i, v + mm, INF);
	}
	
	li fl = maxFlow();
	cout << sum - fl << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	string s;
	cin >> n >> s;
	int pos = n - 1;
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] > s[i + 1]) {
			pos = i;
			break;
		}
	}
	cout << s.substr(0, pos) + s.substr(pos + 1) << endl;
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

long long get(long long n){
	for (long long i = 2; i * i <= n; ++i)
		if (n % i == 0)
			return i;
	return n;
}

int main() {
	long long n;
	scanf("%lld", &n);
	long long cnt = 0;
	if (n % 2 != 0){
		n -= get(n);
		++cnt;
	}
	printf("%lld\n", cnt + n / 2);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

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

li d;

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

inline void solve() {
	if(d == 0) {
		cout << "Y " << 0.0 << " " << 0.0 << endl;
		return;
	}
	if(d < 4) {
		cout << "N" << endl;
		return;
	}
	
	ld D = sqrt(d * li(d - 4));
	ld a = (d + D) / 2.0;
	ld b = (d - D) / 2.0;
	
	cout << "Y " << a << " " << b << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(9);
	
	int tc = 1;
	assert(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;

vector<pair<int, pair<int, int> > > g[300043];

int main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < m; i++)
	{
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		--x;
		--y;
		g[x].push_back(make_pair(y, make_pair(w, i)));
		g[y].push_back(make_pair(x, make_pair(w, i)));
	}
	set<pair<long long, int> > q;
	vector<long long> d(n, (long long)(1e18));
	d[0] = 0;
	q.insert(make_pair(0, 0));
	vector<int> last(n, -1);
	int cnt = 0;
	vector<int> ans;
	while(!q.empty() && cnt < k)
	{
		auto z = *q.begin();
		q.erase(q.begin());
		int k = z.second;
		if(last[k] != -1)
		{
			cnt++;
			ans.push_back(last[k]);
		}
		for(auto y : g[k])
		{
			int to = y.first;
			int w = y.second.first;
			int idx = y.second.second;
			if(d[to] > d[k] + w)
			{
				q.erase(make_pair(d[to], to));
				d[to] = d[k] + w;
				last[to] = idx;
				q.insert(make_pair(d[to], to));
			}
		}
	}		
	printf("%d\n", ans.size());
	for(auto x : ans) printf("%d ", x + 1);
}	

#include <bits/stdc++.h>

using namespace std;

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

int n, m;	
vector <int> g[N];
vector <pair<int, int> > q[N];
long long add[N];
long long res[N];

void dfs(int v, int pr, int h, long long sum){
	for(auto p : q[v]){
		int l = h, r = h + p.first;
		add[l] += p.second;
		if(r + 1 < N) add[r + 1] -= p.second;
	}
	sum += add[h];
	res[v] = sum;	
	for(auto to : g[v])
		if(to != pr)
			dfs(to, v, h + 1, sum);
			
	for(auto p : q[v]){
		int l = h, r = h + p.first;
		add[l] -= p.second;
		if(r + 1 < N) add[r + 1] += p.second;
	}
}

int main() {	
//	freopen("input.txt", "r", stdin);
	
	scanf("%d", &n);
	for(int i = 0; i < n - 1; ++i){
		int u, v;
		scanf("%d %d", &u, &v);
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	scanf("%d", &m);
	for(int i = 0; i < m; ++i){
		int v, h, d;
		scanf("%d %d %d", &v, &h, &d);
		--v;
		q[v].push_back(make_pair(h, d));
	}
	
	dfs(0, 0, 0, 0);
	for(int i = 0; i < n; ++i)
		printf("%lld ", res[i]);
	puts("");
	
	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 = 300 * 1000 + 13;
const int INF = 1e9;

int dp[N][2];

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

int get(int pa, int pb, int a, int b){
	int ans = INF;
	
	if (pa <= k){
		int tot = pa + a;
		int cnt = (tot + k - 1) / k - 1;
		if (b == cnt)
			ans = min(ans, tot - cnt * k);
		else if (b > cnt && b <= a * li(k))
			ans = min(ans, 1);
	}
	
	if (pb <= k){
		int cnt = (a + k - 1) / k - 1;
		if (b == cnt)
			ans = min(ans, a - cnt * k);
		else if (b > cnt && b <= (a - 1) * li(k) + (k - pb))
			ans = min(ans, 1);
	}
	
	return ans;
}

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, n) scanf("%d", &b[i]);
	
	forn(i, N) forn(j, 2) dp[i][j] = INF;
	dp[0][0] = 0;
	dp[0][1] = 0;
	forn(i, n){
		dp[i + 1][0] = get(dp[i][0], dp[i][1], a[i], b[i]);
		dp[i + 1][1] = get(dp[i][1], dp[i][0], b[i], a[i]);
	}
	
	puts(dp[n][0] <= k || dp[n][1] <= k ? "YES" : "NO");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;

typedef long long li;

int n, m;
li a[N];
int q;
int f[N * 4];
vector<int> T[4 * N];
vector<int> T2[4 * N];
int mask;
int cur;

vector<int> combine(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(1 << m);
	for(int i = 0; i < (1 << m); i++)
		c[i] = b[a[i]];
	return c;
}

vector<int> init(li x)
{
	vector<int> ans(1 << m);
	for(int i = 0; i < (1 << m); i++)
	{
		if(i != mask || (x & 1) == 0)
			ans[i] = ((i << 1) & mask) ^ 1;
		else
			ans[i] = ((i << 1) & mask);
	}	
	return ans;
}

void upd(int v)
{
	T[v] = combine(T[v * 2 + 2], T[v * 2 + 1]);
	T2[v] = combine(T2[v * 2 + 2], T2[v * 2 + 1]);
}

void build(int v, int l, int r)
{
	if(l == r - 1)
	{
		T[v] = init(a[l]);
		T2[v] = init(a[l] ^ 1);
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2 + 1, l, m);
	build(v * 2 + 2, m, r);
	upd(v);
}

void push(int v, int l, int r)
{
	if(f[v])
	{
		swap(T[v], T2[v]);
		if(l != r - 1)
		{
			f[v * 2 + 1] ^= 1;
			f[v * 2 + 2] ^= 1;
		}
		f[v] = 0;
	}
}

vector<int> id;

void get(int v, int l, int r, int L, int R)
{
	push(v, l, r);
	if(L >= R)
		return;
	if(l == L && r == R)
	{
		cur = T[v][cur];
	}
	else
	{
		int m = (l + r) >> 1;
		get(v * 2 + 2, m, r, max(L, m), R);
		get(v * 2 + 1, l, m, L, min(R, m));
		upd(v);	
	}
}

void add(int v, int l, int r, int L, int R)
{
	push(v, l, r);
	if(L >= R)
		return;
	if(l == L && r == R)
	{
		f[v] ^= 1;
		push(v, l, r);
		return;
	}
	else
	{
		int m = (l + r) >> 1;
		add(v * 2 + 1, l, m, L, min(R, m));
		add(v * 2 + 2, m, r, max(L, m), R);
		upd(v);
	}
}

int main() 
{ 
	scanf("%d %d %d", &n, &m, &q);
	mask = (1 << m) - 1;
	for(int i = 0; i < (1 << m); i++)
		id.push_back(i);
	for(int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	build(0, 0, n);
	for(int i = 0; i < q; i++)
	{
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);
		--l;
		if(t == 1)
		{
			li d;
			scanf("%lld", &d);
			if(d & 1)
				add(0, 0, n, l, r);
		}
		else
		{
			cur = mask;
			get(0, 0, n, l, r);
			
			if((cur & 1) == 1)
				puts("1");
			else
				puts("2");
		}
	}
}

n = int(input())
s = input()
for i in range(n - 1):
	if (s[i] != s[i + 1]):
		print("YES")
		print(s[i], s[i + 1], sep="")
		exit(0)
print("NO")

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

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

int main() {
//	freopen("input.txt", "r", stdin);
	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 pos = 0;
	for(int i = 0; i < n; ++i){
		int x = b[i];
		if(u[x]){
			printf("0 ");
			continue;
		}
		
		int cnt = 0;
		while(true){
			++cnt;
			u[a[pos]] = true;
			if(a[pos] == x) break;
			++pos;
		} 
		
		++pos;
		printf("%d ", cnt);
	}    
	
	puts("");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e5) + 9;

string s;
int n;
int x, y;

void upd(pair<int, int> &pos, char mv, int d){
	if(mv == 'U')
		pos.second += d;
	if(mv == 'D')
		pos.second -= d;
	if(mv == 'L')
		pos.first -= d;
	if(mv == 'R')
		pos.first += d;
}

bool can(pair<int, int> u, pair<int, int> v, int len){
	int d = abs(u.first - v.first) + abs(u.second - v.second);
	if(d % 2 != len % 2) return false;
	return len >= d;
}

bool ok(int len){
	pair<int, int> pos = make_pair(0, 0);
	for(int i = len; i < n; ++i)
		upd(pos, s[i], 1);

	int l = 0, r = len;
	while(true){
		if(can(pos, make_pair(x, y), len))
			return true;
		
		if(r == n) break;
		upd(pos, s[l++], 1);
		upd(pos, s[r++], -1);		
	}
	
	return false;
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	cin >> n;
	cin >> s;
	cin >> x >> y;
	
	if(!ok(n)){
		puts("-1");
		return 0;
	}
	
	int l = -1, r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(ok(mid)) r = mid;
		else l = mid;
	}
	
	cout << r << 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 = 200 * 1000 + 13;

typedef long long li;

int n;
int a[N];

void get(li T, li& pr, li& cnt){
	pr = 0, cnt = 0;
	forn(i, n){
		if (T >= a[i]){
			T -= a[i];
			pr += a[i];
			++cnt;
		}
	}
}

int main() {
	li T;
	scanf("%d%lld", &n, &T);
	forn(i, n)
		scanf("%d", &a[i]);
	
	int mn = *min_element(a, a + n);
	li ans = 0;
	while (T >= mn){
		li pr, cnt;
		get(T, pr, cnt);
		ans += cnt * (T / pr);
		T %= pr;
	}
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<long long, int> pt;

const int N = 20;
const int M = 1 << 10;
const int MOD = 998244353;

int k;
int pw10[N];
int bitCnt[M];

pt dp[N][M][2];

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 calc(const string &s) {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			dp[i][j][0] = dp[i][j][1] = { 0ll, 0 };
		}
	}
	
	int len = s.size();
	dp[0][0][1] = { 1ll, 0 };
	for (int i = 0; i < len; ++i) {
		int cdig = s[i] - '0';
		for (int mask = 0; mask < M; ++mask) {
			if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue;
			for (int dig = (i == 0); dig <= 9; ++dig) {
				int nmask = mask | (1 << dig);
				long long cnt = dp[i][mask][0].x;
				int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
				dp[i + 1][nmask][0].x += cnt;
				dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum);
			}
			
			for (int dig = (i == 0); dig <= cdig; ++dig) {
				int nmask = mask | (1 << dig);
				long long cnt = dp[i][mask][1].x;
				int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
				dp[i + 1][nmask][dig == cdig].x += cnt;
				dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum);
			}
		}
	}
	
	int ans = 0;
	for (int mask = 0; mask < M; ++mask) {
		if (bitCnt[mask] > k) continue;
		ans = add(ans, dp[len][mask][0].y);
		ans = add(ans, dp[len][mask][1].y);
	}
	return ans;
}

int calc(long long n) {
	int len = to_string(n).size();
	int ans = 0;
	for (int l = 1; l < len; ++l) {
		ans = add(ans, calc(string(l, '9')));
	}
	ans = add(ans, calc(to_string(n)));
	return ans;
}

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

	pw10[0] = 1;
	for (int i = 1; i < N; ++i) {
		pw10[i] = mul(pw10[i - 1], 10);
	}
	for (int i = 0; i < M; ++i) {
		bitCnt[i] = __builtin_popcount(i);
	}
	
	long long l, r;
	cin >> l >> r >> k;
	int ans = add(calc(r), -calc(l - 1));
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define size(a) int((a).size())

typedef pair<int, int> pt;

const int N = 200 * 1000 + 11;

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

int p[N];
int dist[N];

bool bad[N];
int value[N];
pt res[N];
vector<pt> best[N];

void dfs(int v, int par = -1, int d = 0) {
	p[v] = par;
	dist[v] = d;
	for (auto to : g[v]) {
		if (to == par) {
			continue;
		}
		dfs(to, v, d + 1);
	}
}

int getFarthest(int v) {
	dfs(v);
	int res = v;
	for (int i = 0; i < n; ++i) {
		if (bad[i]) {
			continue;
		}
		if (dist[res] < dist[i]) {
			res = i;
		}
	}
	return res;
}

pt get(int v) {
	return { dist[v], value[v] };
}

int getBetter(int v, int u) {
	if (get(v) > get(u)) {
		return v;
	}
	return u;
}

int getBest(int v, int par) {
	int res = v;
	for (auto to : g[v]) {
		if (to == par || bad[to]) {
			continue;
		}
		res = getBetter(res, getBest(to, v));
	}
	return res;
}

pt calc(int v) {
	dfs(v);
	
	vector<int> ch;
	for (auto to : g[v]) {
		if (!bad[to]) {
			ch.push_back(to);
		}
	}
	if (size(ch) == 1) {
		return { v, ch[0] };
	}
	
	vector<int> pref(size(ch));
	vector<int> suf(size(ch));
	vector<int> best(size(ch));
	for (int i = 0; i < size(ch); ++i) {
		int to = ch[i];
		best[i] = pref[i] = suf[i] = getBest(to, v);
	}
	for (int i = 1; i < size(ch); ++i) {
		pref[i] = getBetter(pref[i], pref[i - 1]);
		suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]);
	}
	
	pt ans = { -1, -1 };
	pt res = { 0, 0 };
	for (int i = 0; i < size(ch); ++i) {
		int bst = -1;
		if (i == 0) {
			bst = suf[i + 1];
		} else if (i + 1 == size(ch)) {
			bst = pref[i - 1];
		} else {
			bst = getBetter(pref[i - 1], suf[i + 1]);
		}
		pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] };
		if (res < curRes) {
			res = curRes;
			ans = { best[i], bst };
		}
	}
	
	return ans;
}

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

	cin >> 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);
	}
	
	int root = -1;
	for (int i = 0; i < n; ++i) {
		if (size(g[i]) > 2) {
			root = i;
			dfs(i);
			break;
		}
	}
	
	for (int i = 0; i < n; ++i) {
		if (size(g[i]) != 1) {
			continue;
		}
		int v = i;
		while (size(g[v]) < 3) {
			bad[v] = true;
			v = p[v];
		}
		best[v].push_back({dist[i] - dist[v], i});
	}
	
	for (int i = 0; i < n; ++i) {
		if (size(best[i]) >= 2) {
			sort(best[i].rbegin(), best[i].rend());
			value[i] = best[i][0].first + best[i][1].first;
			res[i] = { best[i][0].second, best[i][1].second };
		}
	}
	
	int u = getFarthest(root);
	int v = getFarthest(u);
	vector<int> path;
	while (v != u) {
		path.push_back(v);
		v = p[v];
	}
	path.push_back(u);
	
	pt ans = calc(path[size(path) / 2]);
	
	printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1);
	printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 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

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) {
	out << "[";
	fore(i, 0, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int N = 200 * 1000 + 555;
const int LOGN = 18;

int n, q;
char s[N];

bool read() {
	if(!(cin >> n >> q))
		return false;
	assert(scanf("%s", s) == 1);
	return true;
}

int c[N], id[N], lcp[N];
int mn[LOGN][N];
int lg2[N];

void buildSuffArray() {
	s[n++] = '$';
	
	for(int l = 1; l < 2 * n; l <<= 1) {
		vector< pair<pt, int> > d;
		fore(i, 0, n)
			d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i);
		stable_sort(d.begin(), d.end());
		
		c[d[0].y] = 0;
		fore(i, 1, n)
			c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x);
		if(c[d.back().y] == n - 1)
			break;
	}
	
	fore(i, 0, n)
		id[c[i]] = i;
		
	int l = 0;
	fore(i, 0, n) {
		if(c[i] == n - 1)
			continue;
		l = max(0, l - 1);
		int j = id[c[i] + 1];
		
		while(i + l < n && j + l < n && s[i + l] == s[j + l])
			l++;
		lcp[c[i]] = l;
	}
	
	n--;
	lg2[0] = lg2[1] = 0;
	fore(i, 2, N) {
		lg2[i] = lg2[i - 1];
		if((1 << (lg2[i] + 1)) <= i)
			lg2[i]++;
	}
	
	fore(i, 0, n)
		mn[0][i] = lcp[i];
	fore(pw, 1, LOGN) fore(i, 0, n) {
		mn[pw][i] = mn[pw - 1][i];
		if(i + (1 << (pw - 1)) < n)
			mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]);
	}
}

int getMin(int l, int r) {
	int ln = lg2[r - l];
	return min(mn[ln][l], mn[ln][r - (1 << ln)]);
}

int getLCP(int i, int j) {
	if(i == j) return n - i;
	i = c[i], j = c[j];
	return getMin(min(i, j), max(i, j));
}

bool cmp(const pt &a, const pt &b) {
	if(a.x == b.x)
		return a.y < b.y;
	int l = getLCP(a.x, b.x);
	return s[a.x + l] < s[b.x + l];
}

void solve() {
	buildSuffArray();
	
	fore(_, 0, q) {
		int k, l;
		assert(scanf("%d%d", &k, &l) == 2);
		vector<int> a(k), b(l);
		fore(i, 0, k)
			assert(scanf("%d", &a[i]) == 1), a[i]--;
		fore(j, 0, l)
			assert(scanf("%d", &b[j]) == 1), b[j]--;
			
		li ans = 0;
		vector<pt> c;
		for(auto v : a)
			c.emplace_back(v, 1);
		for(auto v : b)
			c.emplace_back(v, 0);
		sort(c.begin(), c.end(), cmp);
		
		fore(k, 0, 2) {
			li sum = 0;
			map<int, int> cnt;
			
			fore(i, 0, sz(c)) {
				int id = c[i].x, tp = c[i].y;
				if(tp == 0)
					ans += sum;
				else {
					cnt[n - id]++;
					sum += (n - id);
				}
				if(i + 1 < sz(c)) {
					int len = getLCP(c[i].x, c[i + 1].x);
					while(!cnt.empty()) {
						auto it = --cnt.end();
						if(it->x <= len)
							break;
						
						sum -= it->x * 1ll * it->y;
						cnt[len] += it->y;
						sum += it->y * 1ll * len;
						cnt.erase(it);
					}
				}
			}
			reverse(c.begin(), c.end());
		}
		printf("%lld\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;
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int s, a, b, c;
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i){
        cin >> s >> a >> b >> c;
        
        s /= c;
        int x = s / a;
        s %= a;
        long long res = x * 1LL * (a + b);
        res += s;
        
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    long long m;
    cin >> n >> m;
    long long cur = 1;
    long long rem = m;
    while(rem > 0){
        long long d = min(cur, rem);
        rem -= d;
        ++cur;
    }
    assert(rem == 0);
    
    long long res = n;
    if(cur > 1) res = n - cur;
    
    cout << max(0ll, n - m * 2) << ' ' << res << endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

int n, k, h;
int need = int(1e9);
int cnt[N];

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        h = max(h, x);
        need = min(need, x);
        ++cnt[x];
    }
    
    int pos = N - 1;
    int res = 0;
    long long sum = 0;
    int c = 0;
    while(true){
        long long x = sum - c * 1LL * (pos - 1);
        if(x > k){
            ++res;
            h = pos;
            sum = pos * 1LL * c;
        }   
    
        --pos;
        if(pos == need) break;
        c += cnt[pos];
        sum += cnt[pos] * 1LL * pos;
    }
    
    if(h != need) ++res;
    
    cout << res << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> pt;

const int N = 12;
const int M = 305;
const int INF = 1e9;

int n;
int a[N][N];
pt pos[N * N];
pt dist[M][M];

pt operator +(const pt &a, const pt &b){
    return mp(a.x + b.x, a.y + b.y);
}

int dx[] = {-2, -1, 1, 2,  2,  1, -1, -2};
int dy[] = { 1,  2, 2, 1, -1, -2, -2, -1};

bool in(int x, int y){
    return (0 <= x && x < n && 0 <= y && y < n);
}

int get(int x, int y, int p){
    return x * n * 3 + y * 3 + p;
}

pt dp[N * N][3];

int main() {
    scanf("%d", &n);
    forn(i, n) forn(j, n){
        scanf("%d", &a[i][j]);
        --a[i][j];
        pos[a[i][j]] = mp(i, j);
    }
    
    forn(i, M) forn(j, M) dist[i][j] = mp(INF, INF);
    forn(i, M) dist[i][i] = mp(0, 0);
    
    forn(x, n) forn(y, n){
        forn(i, 8){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (in(nx, ny))
                dist[get(x, y, 0)][get(nx, ny, 0)] = mp(1, 0);
        }
        
        for (int i = -n + 1; i <= n - 1; ++i){
            int nx = x + i;
            int ny = y + i;
            if (in(nx, ny))
                dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
            ny = y - i;
            if (in(nx, ny))
                dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
        }
        
        forn(i, n){
            int nx = x;
            int ny = i;
            dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
            nx = i;
            ny = y;
            dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
        }
        
        forn(i, 3) forn(j, 3){
            if (i != j){
                dist[get(x, y, i)][get(x, y, j)] = mp(1, 1);
            }
        }
    }
    
    forn(k, M) forn(i, M) forn(j, M)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    
    forn(i, N * N) forn(j, 3) dp[i][j] = mp(INF, INF);
    dp[0][0] = dp[0][1] = dp[0][2] = mp(0, 0);
    forn(i, n * n - 1) forn(j, 3) forn(k, 3)
        dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + dist[get(pos[i].x, pos[i].y, j)][get(pos[i + 1].x, pos[i + 1].y, k)]);
    
    pt ans = mp(INF, INF);
    ans = min(ans, dp[n * n - 1][0]);
    ans = min(ans, dp[n * n - 1][1]);
    ans = min(ans, dp[n * n - 1][2]);
    
    printf("%d %d\n", ans.x, ans.y);
    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, m, A;
int b[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 cnt(int x){
    int base = binpow(A, x);
    return mul(add(mul(base, base), base), (MOD + 1) / 2);
}

int main() {
    scanf("%d%d%d", &n, &m, &A);
    forn(i, m)
        scanf("%d", &b[i]);
    
    int ans = binpow(A, n - b[m - 1] * 2);
    ans = mul(ans, cnt(b[0]));
    forn(i, m - 1)
        ans = mul(ans, cnt(b[i + 1] - b[i]));
    
    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;

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 << "[";
    fore(i, 0, v.size()) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

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

const int N = 1000 * 1000 + 555;

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

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    fore(i, 1, n) {
        int p; assert(scanf("%d", &p) == 1);
        p--;
        
        g[p].push_back(i);
        g[i].push_back(p);
    }
    return true;
}

int h[N];
pt drev[N];

void calcRev(int v, int p) {
    drev[v] = pt(INF, 0);
    for(int to : g[v]) {
        if(to == p) continue;
        
        h[to] = h[v] + 1;
        calcRev(to, v);
        
        if(drev[to].x <= h[v]) {
            drev[v].x = min(drev[v].x, drev[to].x);
            drev[v].y += drev[to].y;
        }
    }
    
    if(p >= 0 && g[v].size() == 1)
        drev[v] = pt(h[v] - k, 1);
}

int d[N];

void calcAns(int v, int p) {
    d[v] = (p >= 0 && g[v].size() == 1);
    for(int to : g[v]) {
        if(to == p) continue;
        calcAns(to, v);
        
        int tmp = drev[v].y;
        if(drev[to].x <= h[v])
            tmp -= drev[to].y;
        
        d[v] = max(d[v], tmp + d[to]);
    }
}

inline void solve() {
    h[0] = 0;
    calcRev(0, -1);
    calcAns(0, -1);
    cout << d[0] << 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;

typedef long long li;

const li INF64 = li(1e18);

li add(li x, li y)
{
    return min(x + y, INF64);
}

const int N = 243;

int A1[N][2];
li A2[N][N];
int A3[N][N];
int n, m;
li k;
int z;
int p[N];

void build(const string& s)
{
    z = (int)(s.size());
    p[0] = 0;
    for(int i = 1; i < z; i++)
    {
        int j = p[i - 1];
        while(j > 0 && s[j] != s[i])
            j = p[j - 1];
        if(s[j] == s[i])
            j++;
        p[i] = j;
    }
    for(int i = 0; i <= z; i++)
        for(int j = 0; j < 2; j++)
        {
            if(i < z && s[i] == char('0' + j))
                A1[i][j] = i + 1;
            else if(i == 0)
                A1[i][j] = 0;
            else
                A1[i][j] = A1[p[i - 1]][j];
        }
    for(int i = 0; i <= z; i++)
        for(int j = 0; j < 2; j++)
        {
            A3[i][j] = A1[i][j];
            A2[i][j] = (A3[i][j] == z ? 1 : 0);
        }
    for(int i = 2; i <= n; i++)
        for(int j = 0; j <= z; j++)
        {
            A3[j][i] = A3[A3[j][i - 2]][i - 1];
            A2[j][i] = add(A2[j][i - 2], A2[A3[j][i - 2]][i - 1]);
        }
}

int main()
{
    cin >> n >> k >> m;
    string cur = "";
    for(int i = 0; i < m; i++)
    {
        if(cur != "") build(cur);
        li x = 0;
        if(cur != "" && A3[0][n] == i)
            x = 1;
        if(k == 1 && x == 1)
            break;
        k -= x;
        build(cur + '0');
        li x1 = A2[0][n];
        if(k > x1)
        {
            cur += '1';
            k -= x1;
        }
        else
            cur += '0';
    }
    cout << cur << endl;
    return 0;
}

n, k = map(int, input().split())
print((k + n - 1) // n)

q = int(input())

for i in range(q):
    n, m, k = map(int, input().split())
    if (n < m): n, m = m, n
    if (n % 2 != m % 2):
        k -= 1
        n -= 1
    elif (n % 2 != k % 2):
        k -= 2
        n -= 1
        m -= 1
    print(-1 if k < n else k)

#include <bits/stdc++.h>

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

using namespace std;

long long C[20][20];
long long pw[4];

long long cnk(int n, int k){
    if (k < 0 || k > n) return 0;
    return C[n][k];
}

long long get(int n, int lft){
    long long tot = 0;
    forn(i, lft + 1)
        tot += cnk(n, i) * pw[i];
    return tot;
}

long long calc(long long x){
    string s = to_string(x);
    
    long long res = 0;
    int cur = 3;
    int n = s.size();
    
    forn(i, n){
        if (s[i] == '0') continue;
        res += get(n - i - 1, cur);
        --cur;
        if (cur == -1) break;
        res += get(n - i - 1, cur) * (s[i] - '1');
    }
    
    return res;
}

int main() {
    forn(i, 20){
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729;
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", calc(R + 1) - calc(L));
    }
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

vector<long long> res;

void brute(int pos, int cnt, long long cur){
    if (pos == 18){
        res.push_back(cur);
        return;
    }
    
    brute(pos + 1, cnt, cur * 10);
    
    if (cnt < 3)
        for (int i = 1; i <= 9; ++i)
            brute(pos + 1, cnt + 1, cur * 10 + i);
}

int main() {
    brute(0, 0, 0);
    res.push_back(1000000000000000000);
    
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L)));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

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

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", a + i);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long sum = 0;
    for(int i = 0; i < n; ++i) sum += a[i];
    for(int i = 0; i < m; ++i) sum -= b[i];
    if(sum != 0){
        puts("-1");
        return 0;
    }
    
    int posa = 0, posb = 0;
    int res = 0;
    while(posa < n){
        ++res;
        long long suma = a[posa++], sumb = b[posb++];
                
        while(suma != sumb){
            if(suma < sumb) suma += a[posa++];
            else sumb += b[posb++];
        }
    }
    
    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 = 1000 + 7;

struct seg{
    int x1, y1, x2, y2;
    seg(){};
};

struct line{
    long long A, B, C;
    line(){};
    line(seg a){
        A = a.y1 - a.y2;
        B = a.x2 - a.x1;
        C = -A * a.x1 - B * a.y1;
    };
};

int n;
seg a[N];

int get(seg a){
    int dx = a.x1 - a.x2;
    int dy = a.y1 - a.y2;
    return __gcd(abs(dx), abs(dy)) + 1;
}

long long det(long long a, long long b, long long c, long long d){
    return a * d - b * c;
}

bool in(int x, int l, int r){
    if (l > r) swap(l, r);
    return (l <= x && x <= r);
}

bool inter(seg a, seg b, int& x, int& y){
    line l1(a), l2(b);
    long long dx = det(l1.C, l1.B, l2.C, l2.B);
    long long dy = det(l1.A, l1.C, l2.A, l2.C);
    long long d = det(l1.A, l1.B, l2.A, l2.B);
    if (d == 0)
        return false;
    if (dx % d != 0 || dy % d != 0)
        return false;
    x = -dx / d;
    y = -dy / d;
    if (!in(x, a.x1, a.x2) || !in(y, a.y1, a.y2))
        return false;
    if (!in(x, b.x1, b.x2) || !in(y, b.y1, b.y2))
        return false;
    return true;
}

int main() {
    scanf("%d", &n);
    forn(i, n)
        scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
    
    int ans = 0;
    int x, y;
    forn(i, n){
        ans += get(a[i]);
        set<pair<int, int>> pts;
        forn(j, i)
            if (inter(a[i], a[j], x, y))
                pts.insert({x, y});
        ans -= pts.size();
    }
    
    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 K = 100;
const int N = 100 * 1000 + 13;
const long long INF64 = 3e18;

int mu[K];

void precalc(){
    static bool prime[K];
    static int lst[K];
    
    memset(prime, false, sizeof(prime));
    forn(i, K) lst[i] = i;
    
    for (int i = 2; i < K; ++i){
        if (lst[i] == i) mu[i] = 1;
        for (int j = 2 * i; j < K; j += i){
            lst[j] = min(lst[j], lst[i]);
            if (lst[j] == lst[i])
                mu[j] = 0;
            else
                mu[j] = -mu[i];
        }
    }
}

int mx[K];

long long binpow(long long a, int b){
    long long res = 1;
    while (b){
        if (b & 1){
            if (res < INF64 / a) res *= a;
            else return INF64;
        }
        if (b > 1){
            if (a < INF64 / a) a *= a;
            else return INF64;
        }
        b >>= 1;
    }
    return res;
}

long long calc(long long n){
    int pw = 63 - __builtin_clzll(n);
    for (int i = 3; i <= pw; ++i){
        if (mu[i] == 0) continue;
        while (binpow(mx[i], i) > n)
            --mx[i];
    }
    
    long long res = n - 1;
    for (int i = 2; i <= pw; ++i)
        res -= mu[i] * (mx[i] - 1);
    
    return res;
}

int get_sqrt(long long n){
    int l = 1, r = 1000000000;
    while (l < r - 1){
        int m = (l + r) / 2;
        if (m * 1ll * m <= n)
            l = m;
        else
            r = m;
    }
    return (r * 1ll * r <= n ? r : l);
}

long long ans[N];

int main() {
    precalc();
    int T;
    scanf("%d", &T);
    vector<pair<long long, int>> q;
    
    forn(i, T){
        long long n;
        scanf("%lld", &n);
        q.push_back({n, i});
    }
    
    sort(q.begin(), q.end(), greater<pair<long long, int>>());
    mx[3] = 1000000;
    mx[4] = 31622;
    mx[5] = 3981;
    for (int i = 6; i < K; ++i)
        mx[i] = 1000;
    
    forn(z, T){
        long long n = q[z].first;
        mx[2] = get_sqrt(n);
        ans[q[z].second] = calc(n);
    }
    
    forn(i, T)
        printf("%lld\n", ans[i]);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000043;

vector<int> g[N];
vector<int> gt[N];
vector<int> src;
vector<int> snk;
int reach[20];
int used[N];

void dfs(int x)
{
    if(used[x]) return;
    used[x] = 1;
    for(auto y : g[x]) dfs(y);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 0; i < n; i++)
    {
        if(g[i].empty())
            snk.push_back(i);
        if(gt[i].empty())
            src.push_back(i);
    }
    int cnt = src.size();
    for(int i = 0; i < cnt; i++)
    {
        memset(used, 0, sizeof used);
        dfs(src[i]);
        for(int j = 0; j < cnt; j++)
            if(used[snk[j]])
                reach[i] ^= (1 << j);
    }
    bool ok = true;
    for(int mask = 0; mask < (1 << cnt); mask++)
    {
        int res = 0;
        for(int j = 0; j < cnt; j++)
            if(mask & (1 << j))
                res |= reach[j];
        int cnt1 = __builtin_popcount(mask);
        int cnt2 = __builtin_popcount(res);
        if(cnt2 < cnt1 || (cnt2 == cnt1 && cnt1 != 0 && cnt1 != cnt))
            ok = false;
    }
    if(!ok)
        puts("NO");
    else
        puts("YES");
}