#include<bits/stdc++.h>

using namespace std;

int n;
string s;

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;

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

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

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

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

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

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

int n;
string s;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

typedef long long li;

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

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

int n;
vector<int> a;

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

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

vector<int> S[2];

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

typedef long long li;

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

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

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

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

using namespace std;

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

#include <bits/stdc++.h>

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

using namespace std;

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

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

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int n, z;
int a[N];

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

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

Solution described in a tutorial.

Jury's solution:

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

using namespace std;


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

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

map<string,expr*> var;

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

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

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

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

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

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

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

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

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

}

#include <bits/stdc++.h>

using namespace std;

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

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

typedef long long li;

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

int n, x;
int a[N];

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

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

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

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

#define x first
#define y second

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

const int MOD = 1000 * 1000 + 3;

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

int k = 10;
vector<int> f;

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

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

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

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

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

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

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

int n;
vector<int> a;

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

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

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

#include <bits/stdc++.h>

using namespace std;

int t, n;
string s;

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

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n, k;
vector<int> a;

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

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

vector<int> curArray;

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

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

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

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

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

    if(read()) {
        solve();

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

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

#define x first
#define y second

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

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

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

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

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

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

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

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

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

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

li res[N];

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

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

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

#define x first
#define y second

const int N = 600043;

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

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

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

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

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

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

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

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

cnt = []

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

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

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

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

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

#include <bits/stdc++.h>

using namespace std;

const int N = 5043;

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

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

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

#include <bits/stdc++.h>

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

using namespace std;

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

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

vector<int> qr[N];

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

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

#include <bits/stdc++.h>

using namespace std;

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

typedef long long li;

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

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

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

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

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

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

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

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

#define x first
#define y second

int n, k;
vector<int> a;

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

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

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

vector<int> Tmax, Tadd;

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

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

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

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

#include<iostream>
using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 100009;

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

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

pair<int, int> d[N];

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

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

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

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

	return 0;
}

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

ll bin[103][103];

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

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

using namespace std;

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

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

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

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

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

#define x first
#define y second

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

const int N = 5200;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

	return res;
}

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

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

	return res;
}

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

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

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

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int, int> pt;

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

mt19937 rnd(time(NULL));

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

const int N = 200 * 1000 + 13;

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

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

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

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

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

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

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

	}
}

#include <bits/stdc++.h>

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

using namespace std;

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

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

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

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

#define mp make_pair
#define pb push_back

#define x first
#define y second

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

const int INF = int(1e9);
const 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>
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>

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