#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int index = 0;
    int gap = 1;
    while (index < n)
        cout << s[index], index += gap, gap++;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	
	cout << min(a[n - 2] - a[0], a[n - 1] - a[1]) << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	map<int, int> ans;
	queue<int> q;
	for(int i = 0; i <= 30; i++)
		if(n & (1 << i))
		{
			if(i > 0) q.push(1 << i);
			ans[1 << i]++;
		}
	if(int(ans.size()) > k)
	{
		puts("NO");
		return 0;
	}
	int cnt = ans.size();
	while(cnt < k && !q.empty())
	{
		int z = q.front();
		q.pop();
		ans[z]--;
		ans[z / 2] += 2;
		if(z / 2 > 1)
		{
			q.push(z / 2);
			q.push(z / 2);
		}
		cnt++;
	}
	if(cnt < k)
	{
		puts("NO");
		return 0;
	}
	puts("YES");
	for(auto x : ans)
		for(int i = 0; i < x.second; i++)
			printf("%d ", x.first);
	puts("");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> a;

void check(int l, int r) {
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		int nxt = -1;
		if (a[l][0] == r) {
			nxt = a[l][1];
		} else if (a[l][1] == r) {
			nxt = a[l][0];
		} else {
			return;
		}
		ans.push_back(nxt);
		l = r;
		r = nxt;
	}
	for (auto it : ans) {
		cout << it + 1 << " ";
	}
	cout << endl;
	exit(0);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	a = vector<vector<int>> (n, vector<int>(2));
	for (int i = 0; i < n; ++i) {
		cin >> a[i][0] >> a[i][1];
		--a[i][0];
		--a[i][1];
	}
	
	check(0, a[0][0]);
	check(0, a[0][1]);
	
	assert(false);
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	
	string rs(s.rbegin(), s.rend());
	for (int i = 0; i < n; ++i) {
		if (rs[i] == '(') {
			rs[i] = ')';
		} else {
			rs[i] = '(';
		}
	}
	
	vector<int> pref(n + 1), suf(n + 1);
	vector<bool> okp(n + 1), oks(n + 1);
	okp[0] = oks[n] = true;
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
		okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
		suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
		oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
	}
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (!okp[i] || !oks[i + 1]) {
			continue;
		}
		if (s[i] == '(') {
			if (pref[i] > 0 && pref[i] - 1 - suf[i + 1] == 0) {
				++ans;
			}
		} else {
			if (pref[i] + 1 - suf[i + 1] == 0) {
				++ans;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair

typedef pair<long long, pair<int, int> > edge;

const int N = 200043;

int p[N];
long long a[N];

int get_leader(int x)
{
	return (x == p[x] ? x : (p[x] = get_leader(p[x])));
}

bool merge(int x, int y)
{
	x = get_leader(x);
	y = get_leader(y);
	if(x == y) return false;
	p[x] = y;
	return true;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	vector<edge> es(m);
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d %lld", &es[i].y.x, &es[i].y.y, &es[i].x);
		es[i].y.x--;
		es[i].y.y--;
	}
	int z = min_element(a, a + n) - a;
	for(int i = 0; i < n; i++)
		if(i != z)
			es.push_back(mp(a[i] + a[z], mp(i, z)));
	sort(es.begin(), es.end());
	long long ans = 0;
	for(int i = 0; i < n; i++)
		p[i] = i;
	for(auto e : es)
		if(merge(e.y.x, e.y.y))
			ans += e.x;
	printf("%lld\n", ans);
	return 0;		
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int n, k;
		cin >> n >> k;
		for (int j = 0; j < n; ++j) {
			cout << char('a' + j % k);
		}
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	sort(a.begin(), a.end());
	int res = 0;
	for (int i = 0; i < n; i += 2) {
		res += a[i + 1] - a[i];
	}
	
	cout << res << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
vector<string> v;

string res;

bool check(const string &pref, const string &suf) {
	string s = pref + suf.substr(n - 2);
	multiset<string> vv, sPref, sSuf;
	for (int i = 0; i < n - 1; ++i) {
		sPref.insert(s.substr(0, n - i - 1));
		vv.insert(s.substr(0, n - i - 1));
		sSuf.insert(s.substr(i + 1));
		vv.insert(s.substr(i + 1));
	}
	if (vv == multiset<string>(v.begin(), v.end())) {
		for (int i = 0; i < 2 * n - 2; ++i) {
			if (sPref.count(v[i])) {
				res += 'P';
				sPref.erase(sPref.find(v[i]));
			} else if (sSuf.count(v[i])) {
				res += 'S';
				sSuf.erase(sSuf.find(v[i]));
			} else {
				assert(false);
			}
		}
		return true;
	}
	return false;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	v = vector<string>(2 * n - 2);
	vector<string> big;
	for (int i = 0; i < 2 * n - 2; ++i) {
		cin >> v[i];
		if (int(v[i].size()) == n - 1) {
			big.push_back(v[i]);
		}
	}
	
	if (check(big[0], big[1])) {
		cout << res << endl;
	} else {
		check(big[1], big[0]);
		cout << res << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	vector<int> st;
	forn(i, n){
		if (!st.empty() && a[i] == st.back())
			st.pop_back();
		else
			st.push_back(a[i]);
	}
	
	puts(st.size() <= 1 ? "YES" : "NO");
	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;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	set<pair<int, int>> seg, even;
	forn(i, n){
		int j = i;
		while (j + 1 < n && a[j + 1] == a[i]) ++j;
		seg.insert({i, j});
		if ((j - i + 1) % 2 == 0)
			even.insert({i, j});
		i = j;
	}
	
	while (seg.size() > 1 && !even.empty()){
		auto cur = *even.begin();
		even.erase(cur);
		seg.erase(cur);
		auto it = seg.lower_bound(cur);
		if (it != seg.end()){
			cur.second = it->second;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		it = seg.lower_bound(cur);
		if (it != seg.begin()){
			--it;
			cur.first = it->first;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		seg.insert(cur);
		if ((cur.second - cur.first + 1) % 2 == 0)
			even.insert(cur);
	}
	
	puts(seg.size() == 1 ? "YES" : "NO");
	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 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> st;
	
	int mx = *max_element(a, a + n);
	
	forn(i, n){
		if (a[i] == mx) continue;
		
		int j = i - 1;
		while (j + 1 < n && a[j + 1] != mx){
			++j;
			if (!st.empty() && st.back() == a[j]){
				st.pop_back();
			}
			else if (st.empty() || st.back() > a[j]){
				st.push_back(a[j]);
			}
			else{
				puts("NO");
				return 0;
			}
		}
		
		if (!st.empty()){
			puts("NO");
			return 0;
		}
		
		i = j;
	}
	
	puts("YES");
	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 = 1000000000;

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

int bfs(int x, int dist[N]){
	queue<int> q;
	q.push(x);
	dist[x] = 0;
	int lst = -1;
	while (!q.empty()){
		int v = q.front();
		q.pop();
		lst = v;
		for (auto u : g[v]) if (dist[u] > dist[v] + 1){
			dist[u] = dist[v] + 1;
			q.push(u);
		}
	}
	return lst;
}

int distx[N], disty[N];
bool used[N];
vector<int> cur;

void dfs(int v){
	used[v] = true;
	cur.push_back(v);
	for (auto u : g[v]) if (!used[u])
		dfs(u);
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	
	vector<pair<int, int>> comps;
	forn(i, n) if (!used[i]){
		cur.clear();
		dfs(i);
		int x = bfs(i, distx);
		int y = bfs(x, disty);
		for (auto v : cur) distx[v] = INF;
		bfs(y, distx);
		int d = disty[y], center;
		for (auto v : cur) if (distx[v] == d / 2 && disty[v] == d - d / 2)
			center = v;
		comps.push_back({d, center});
	}
	
	vector<pair<int, int>> ans;
	nth_element(comp.begin(), comp.end() - 1, comp.end());
	forn(i, int(comps.size()) - 1){
		g[comps[i].second].push_back(comps.back().second);
		g[comps.back().second].push_back(comps[i].second);
		ans.push_back({comps[i].second, comps.back().second});
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	int y = bfs(bfs(comps.back().second, distx), disty);
	
	printf("%d\n", disty[y]);
	for (auto it : ans)
		printf("%d %d\n", it.first + 1, it.second + 1);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

long long res, ans;

vector<int> a;
vector<long long> sum;
vector<vector<int>> g;

void dfs(int v, int p = -1, int h = 0) {
	res += h * 1ll * a[v];
	sum[v] = a[v];
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs(to, v, h + 1);
		sum[v] += sum[to];
	}
}

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

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

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int a, b, k;
		cin >> a >> b >> k;
		cout << (a - b) * 1ll * (k / 2) + a * (k & 1) << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(MAX + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	long long sum = accumulate(a.begin(), a.end(), 0ll);
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		sum -= a[i];
		--cnt[a[i]];
		if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0) {
			ans.push_back(i);
		}
		sum += a[i];
		++cnt[a[i]];
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200 * 1000 + 1;

int n, k;
vector<int> s, t;
vector<int> cnts(MAX);

bool can(int cnt) {
	t.clear();
	for (int i = 0; i < MAX; ++i) {
		int need = min(cnts[i] / cnt, k - int(t.size()));
		for (int j = 0; j < need; ++j) {
			t.push_back(i);
		}
	}
	return int(t.size()) == k;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k;
	s = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (auto c : s) {
		++cnts[c];
	}
	
	int l = 0, r = n;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	if (!can(r)) can(l);
	for (auto it : t) cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	map<int, int> cnt;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	
	vector<int> cnts;
	for (auto it : cnt) {
		cnts.push_back(it.second);
	}
	sort(cnts.begin(), cnts.end());
	
	int ans = 0;
	for (int i = 1; i <= cnts.back(); ++i) {
		int pos = int(cnts.size()) - 1;
		int cur = i;
		int res = cur;
		while (cur % 2 == 0 && pos > 0) {
			cur /= 2;
			--pos;
			if (cnts[pos] < cur) break;
			res += cur;
		}
		ans = max(ans, res);
	}
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k, x;
	cin >> n >> k >> x;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, -INF64));
	
	dp[0][x] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < x; ++j) {
			for (int p = 1; p <= k; ++p) {
				if (i - p < 0) break;
				if (dp[i - p][j + 1] == -INF64) {
					continue;
				}
				dp[i][j] = max(dp[i][j], dp[i - p][j + 1] + a[i - 1]);
			}
		}
	}
	
	long long ans = -INF64;
	for (int i = n - k + 1; i <= n; ++i) {
		ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
	}
	if (ans == -INF64) ans = -1;
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair

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

const li INF64 = 1e18;

struct myQueue {
	stack<pll> s1, s2;
	
	int size() {
		return s1.size() + s2.size();
	}
	
	bool isEmpty() {
		return size() == 0;
	}
	
	long long getMax() {
		if (isEmpty()) {
			return -INF64;
		}
		if (!s1.empty() && !s2.empty()) {
			return max(s1.top().y, s2.top().y);
		}
		if (!s1.empty()) {
			return s1.top().y;
		}
		return s2.top().y;
	}
	
	void push(long long val) {
		if (s2.empty()) {
			s2.push(mp(val, val));
		} else {
			s2.push(mp(val, max(val, s2.top().y)));
		}
	}
	
	void pop() {
		if (s1.empty()) {
			while (!s2.empty()) {
				if (s1.empty()) {
					s1.push(mp(s2.top().x, s2.top().x));
				} else {
					s1.push(mp(s2.top().x, max(s2.top().x, s1.top().y)));	
				}
				s2.pop();
			}
		}
		assert(!s1.empty());
		s1.pop();
	}
};

int n, k, x;
vector<int> a;

vector<myQueue> q;
vector<queue<int>> pos;
vector<vector<long long>> dp;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k >> x;
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	q = vector<myQueue>(x + 1);
	pos = vector<queue<int>>(x + 1);
	dp = vector<vector<long long>>(n + 1, vector<long long>(x + 1, -INF64));
	
	dp[0][x] = 0;
	pos[x].push(-1);
	q[x].push(0ll);
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= x; ++j) {
			while (!pos[j].empty() && pos[j].front() < i - k - 1) {
				q[j].pop();
				pos[j].pop();
			}
		}
		for (int j = 0; j < x; ++j) {
			if (!q[j + 1].isEmpty()) {
				dp[i][j] = max(dp[i][j], q[j + 1].getMax() + a[i - 1]);
				q[j].push(dp[i][j]);
				pos[j].push(i - 1);
			}
		}
	}
	
	long long ans = -INF64;
	for (int i = n - k + 1; i <= n; ++i) {
		ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
	}
	if (ans == -INF64) ans = -1;
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	
	for (int i = 0; i < t; ++i) {	
		int L, v, l, r;
		cin >> L >> v >> l >> r;
		cout << L / v - r / v + (l - 1) / v << 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, r;
	cin >> n >> r;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	int ans = 0;
	int last = -1;
	while (last < n - 1) {
		int pos = -1;
		for (int i = n - 1; i > max(-1, last - r + 1); --i) {
			if (a[i] == 1 && i - r <= last) {
				pos = i;
				break;
			}
		}
		if (pos == -1) {
			cout << -1 << "\n";
			return 0;
		}
		++ans;
		last = pos + r - 1;
	}
	
	cout << ans << "\n";
	
	return 0;
}

#include <vector>
#include <iostream>

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

using namespace std;

const int N = 2e5;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, r; cin >> n >> r;
	vector<int> a(n);
	vector<int> cnt(n);
	int ans = 0;
	forn(i, n)
        {
            cin >> a[i];
            if (a[i])ans++;
            if (a[i])
                for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                    cnt[j]++;
        }
    forn(i, n)
        if (!cnt[i])
        {
            cout << -1;
            return 0;
        }
    forn(i, n)
    {
        bool fl = true;
        if (a[i])
            for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                if (cnt[j] == 1)
                {
                    fl = false;
                    break;
                }
        if (fl && a[i])
        {
            ans--;
            for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
                cnt[j]--;
        }
    }
    cout << ans;

}

#include <bits/stdc++.h>

using namespace std;

const int M = 200 * 1000 + 11;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	
	vector<int> pos(M);
	int curl = 0;
	int curr = 0;
	
	for (int i = 0; i < q; ++i) {
		string type;
		int id;
		cin >> type >> id;
		if (i == 0) {
			pos[id] = curl;
			--curl;
			++curr;
		} else {
			if (type == "L") {
				pos[id] = curl;
				--curl;
			} else if (type == "R") {
				pos[id] = curr;
				++curr;
			} else {
				cout << min(abs(pos[id] - curl), abs(pos[id] - curr)) - 1 << "\n";
			}
		}
	}
	
	return 0;
}

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

const int MAX = 2e5 + 10;

int ar[MAX];
int n, m, k;

int find(int pos){
    int ans = n - pos + 1;
    int used = 0;
    while(used < m && pos <= n){
        int t = k;
        while(pos <= n && ar[pos] <= t){
            t -= ar[pos++];
        }
        used++;
    }
    return pos == n + 1 ? ans : 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> ar[i];
    }
    int ans = 0;
    int l = 1, r = n;
    while(l <= r){
        int x = (l + r) >> 1;
        if(find(x)){
            ans = max(ans, n - x + 1);
            r = x - 1;
        }else{
            l = x + 1;
        }
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	reverse(a.begin(), a.end());
	int rem = 0;
	for (int i = 0; i < n; ++i) {
		if (rem - a[i] < 0) {
			if (m == 0) {
				cout << i << endl;
				return 0;
			} else {
				--m;
				rem = k - a[i];
			}
		} else {
			rem -= a[i];
		}
	}
	
	cout << n << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	string s, t;
	cin >> s >> t;
	
	int pw = 1;
	int res = 0;
	int ans = 0;
	
	for (int i = 0; i < m; ++i) {
		if (i < n && s[n - i - 1] == '1') {
			res = add(res, pw);
		}
		if (t[m - i - 1] == '1') {
			ans = add(ans, res);
		}
		pw = add(pw, pw);
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

long long dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	map<int, vector<pair<int, int>>> pts;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		pts[max(x, y)].push_back(make_pair(x, y));
	}
	pts[0].push_back(make_pair(0, 0));
	
	for (auto &it : pts) {
		sort(it.second.begin(), it.second.end(), [&](pair<int, int> a, pair<int, int> &b) {
			if (a.first == b.first)
				return a.second > b.second;
			return a.first < b.first;
		});
	}
	
	vector<vector<long long>> dp(int(pts.size()) + 1, vector<long long>(2, INF64));
	dp[0][0] = dp[0][1] = 0;
	
	int lvl = 0;
	int prv = 0;
	for (auto &it : pts) {
		++lvl;
		
		pair<int, int> curl = it.second[0];
		pair<int, int> curr = it.second.back();
		
		pair<int, int> prvl = pts[prv][0];
		pair<int, int> prvr = pts[prv].back();
		
		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][0] + dist(prvl, curr) + dist(curl, curr));
		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][1] + dist(prvr, curr) + dist(curl, curr));
		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][0] + dist(prvl, curl) + dist(curl, curr));
		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][1] + dist(prvr, curl) + dist(curl, curr));
		
		prv = it.first;
	}
	
	cout << min(dp[lvl][0], dp[lvl][1]) << endl;
	
	return 0;
}

#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

const int N = 100 + 13;

int n, m;
int a[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans2 = *max_element(a, a + n) + m;
    for (int it = 0; it < m; it++) {
        int pos = -1;
        for (int i = 0; i < n; i++) {
            if (pos == -1 || a[i] < a[pos]) {
                pos = i;
            }
        }
        assert(pos != -1);
        a[pos]++;
    }
    int ans1 = *max_element(a, a + n);
    cout << ans1 << ' ' << ans2 << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
map<string, int> was;

inline void read() {	
	cin >> n;
	for (int i = 0; i < n; i++) {
		int c;
		string s;
		cin >> c >> s;
		sort(s.begin(), s.end());
		if (was.count(s) == 0) {
			was[s] = c;
		} else {
			was[s] = min(was[s], c);
		}
	}
}

inline int getC(string a, string b) {
 	if (!was.count(a) || !was.count(b)) {
 		return INF;
 	}
 	return was[a] + was[b];
}

inline void solve() {
	int ans = INF;
	if (was.count("A") && was.count("B") && was.count("C")) {
		ans = was["A"] + was["B"] + was["C"];
	}
    if (was.count("ABC")) {
    	ans = min(ans, was["ABC"]);
    }
    ans = min(ans, getC("AB", "C"));
    ans = min(ans, getC("A", "BC"));
    ans = min(ans, getC("AC", "B"));
    ans = min(ans, getC("AB", "BC"));
    ans = min(ans, getC("AC", "BC"));
    ans = min(ans, getC("AC", "AB"));
    if (ans == INF) {
    	ans = -1;
    }
    cout << ans << endl;
}

int main () {
    read();
    solve();
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	
	int cntneg = 0;
	int cntzero = 0;
	vector<int> used(n);
	int pos = -1;
	for (int i = 0; i < n; ++i) {
		if (a[i] == 0) {
			used[i] = 1;
			++cntzero;
		}
		if (a[i] < 0) {
			++cntneg;
			if (pos == -1 || abs(a[pos]) > abs(a[i]))
				pos = i;
		}
	}
	if (cntneg & 1)
		used[pos] = 1;
		
	if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) {
		for (int i = 0; i < n - 1; ++i)
			printf("1 %d %d\n", i + 1, i + 2);
		return 0;
	}
	
	int lst = -1;
	for (int i = 0; i < n; ++i) {
		if (used[i]) {
			if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1);
			lst = i;
		}
	}
	if (lst != -1) printf("2 %d\n", lst + 1);
	
	lst = -1;
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1);
			lst = i;
		}
	}
	
	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;
long long T;
int a[N];
int f[N];

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

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

int main() {
	scanf("%d%lld", &n, &T);
	forn(i, n)
		scanf("%d", &a[i]);
	
	vector<long long> sums(1, 0ll);
	long long pr = 0;
	forn(i, n){
		pr += a[i];
		sums.push_back(pr);
	}
	
	sort(sums.begin(), sums.end());
	sums.resize(unique(sums.begin(), sums.end()) - sums.begin());
	
	long long ans = 0;
	pr = 0;
	upd(lower_bound(sums.begin(), sums.end(), 0ll) - sums.begin());
	
	forn(i, n){
		pr += a[i];
		
		int npos = upper_bound(sums.begin(), sums.end(), pr - T) - sums.begin();
		ans += (i + 1 - get(npos - 1));
		
		int k = lower_bound(sums.begin(), sums.end(), pr) - sums.begin();
		upd(k);
	}
	
	printf("%lld\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 1009;

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

void upd(int &a, int b){
	a += b;
	while(a >= MOD) a -= MOD;
	while(a < 0) a += 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 inv(int a){
	int ia = bp(a, MOD - 2);
	assert(mul(a, ia) == 1);
	return ia;
}

int n, m;
int a[N][N];
int dp[N][N];
int si, sj;

int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i) 
		for(int j = 0; j < m; ++j)
			scanf("%d", &a[i][j]);
	scanf("%d %d", &si, &sj);
	--si, --sj;
	
	vector <pair<int, pair<int, int> > > v;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			v.push_back(make_pair(a[i][j], make_pair(i, j)));

	sort(v.begin(), v.end());
	int l = 0;
	int sumDP = 0, sumX = 0, sumY = 0, sumX2 = 0, sumY2 = 0;
	while(l < int(v.size())){
		int r = l;
		while(r < int(v.size()) && v[r].first == v[l].first) ++r;
		
		int il = -1;
		if(l != 0) il = inv(l);
		for(int i = l; i < r; ++i){
			int x = v[i].second.first, y = v[i].second.second;
			if(il == -1){
				dp[x][y] = 0;
				continue;
			}
			
			
			upd(dp[x][y], mul(sumDP, il));
			
			upd(dp[x][y], mul(x, x));
			upd(dp[x][y], mul(y, y));
			
			upd(dp[x][y], mul(sumX2, il));
			upd(dp[x][y], mul(sumY2, il));
			
			upd(dp[x][y], mul(mul(-x - x, sumX), il));
			upd(dp[x][y], mul(mul(-y - y, sumY), il));		
		}
		
		for(int i = l; i < r; ++i){
			int x = v[i].second.first, y = v[i].second.second;
			
			upd(sumDP, dp[x][y]);
			
			upd(sumX2, mul(x, x));
			upd(sumY2, mul(y, y));
			
			upd(sumX, x);
			upd(sumY, y);
		}
		
		l = r;
		
	}
	
	printf("%d\n", dp[si][sj]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(a) int((a).size())

const int N = 1000 * 1000 + 13;

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

int dfs(int v, int p = -1){
	if (g[v].size() == 1)
		return 0;
	
	vector<int> cur;
	for (auto u : g[v]){
		if (u == p) continue;
		cur.push_back(dfs(u, v) + 1);
	}
	sort(cur.begin(), cur.end());
	
	while (sz(cur) >= 2){
		if (cur.back() + cur[sz(cur) - 2] <= k)
			break;
		++ans;
		cur.pop_back();
	}
	
	return cur.back();
}

int main(){
	scanf("%d%d", &n, &k);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n){
		if (sz(g[i]) > 1){
			dfs(i);
			break;
		}
	}
	
	printf("%d\n", ans + 1);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(a) int((a).size())

const int N = 1000 * 1000 + 13;

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

void dfs(int v, int d, int p){
	if (g[v].size() == 1){
		val[v].insert(d);
		return;
	}
	
	int bst = -1;
	for (auto u : g[v]){
		if (u == p) continue;
		dfs(u, d + 1, v);
		if (bst == -1 || sz(val[u]) > sz(val[bst]))
			bst = u;
	}
	swap(val[bst], val[v]);
	
	for (auto u : g[v]){
		if (u == p || u == bst) continue;
		for (auto it : val[u]){
			int dd = k + 2 * d - it;
			auto jt = val[v].upper_bound(dd);
			if (jt == val[v].begin()){
				val[v].insert(it);
			}
			else{
				--jt;
				int t = *jt;
				val[v].erase(jt);
				val[v].insert(max(it, t));
			}
		}
	}
}

int main(){
	scanf("%d%d", &n, &k);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n){
		if (sz(g[i]) > 1){
			dfs(i, 0, -1);
			printf("%d\n", sz(val[i]));
			break;
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(a) int((a).size())

const int N = 1000 * 1000 + 13;

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

int dfs(int v, int p = -1){
	if (g[v].size() == 1)
		return 0;
	
	vector<int> cur;
	for (auto u : g[v]){
		if (u == p) continue;
		cur.push_back(dfs(u, v) + 1);
	}
	
	int pos = -1;
	forn(i, sz(cur)) {
		if (cur[i] * 2 <= k && (pos == -1 || cur[pos] < cur[i]))
			pos = i;
	}
	
	if (pos == -1) {
		ans += sz(cur) - 1;
		return *min_element(cur.begin(), cur.end());
	}
	
	int res = -1;
	forn(i, sz(cur)) {
		if (cur[pos] >= cur[i]) continue;
		if (cur[i] + cur[pos] <= k && (res == -1 || cur[i] < cur[res]))
			res = i;
	}
	
	forn(i, sz(cur))
		ans += (cur[i] > cur[pos]);
	if (res != -1)
		--ans;
	
	return (res == -1 ? cur[pos] : cur[res]);
}

int main(){
	scanf("%d%d", &n, &k);
	forn(i, n - 1) {
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n) {
		if (sz(g[i]) > 1) {
			dfs(i);
			break;
		}
	}
	
	printf("%d\n", ans + 1);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	string t;
	cin >> n >> k >> t;
	
	int cnt = 1;
	int pos = 1;
	string ans = t;
	while (cnt < k) {
		if (pos >= sz(ans)) {
			ans += t;
			++cnt;
		} else {
			bool ok = true;
			int len = 0;
			for (int i = 0; i < sz(t); ++i) {
				if (pos + i >= sz(ans)) break;
				++len;
				if (ans[pos + i] != t[i]) ok = false;
			}
			if (ok) {
				ans += t.substr(len);
				++cnt;
			}
		}
		++pos;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	string t;
	cin >> n >> k >> t;
	
	vector<int> p(n);
	for (int i = 1; i < sz(t); ++i) {
		int j = p[i - 1];
		while (j > 0 && t[j] != t[i])
			j = p[j - 1];
		if (t[i] == t[j])
			++j;
		p[i] = j;
	}
	
	int len = sz(t) - p[n - 1];
	
	for (int i = 0; i < k - 1; ++i)
		cout << t.substr(0, len);
	cout << t << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
		
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int j = i;
		while (j + 1 < n && a[j + 1] <= a[j] * 2)
			++j;
		ans = max(ans, j - i + 1);
		i = j;
	}
	
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 300 * 1000 + 13;
const int INF = int(1e9);

int n;
int prl[N], prr[N], sul[N], sur[N];
int l[N], r[N];

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d%d", &l[i], &r[i]);
	
	prl[0] = sul[n] = 0;
	prr[0] = sur[n] = INF;
	
	forn(i, n){
		prl[i + 1] = max(prl[i], l[i]);
		prr[i + 1] = min(prr[i], r[i]);
	}
	
	for (int i = n - 1; i >= 0; --i){
		sul[i] = max(sul[i + 1], l[i]);
		sur[i] = min(sur[i + 1], r[i]);
	}
	
	int ans = 0;
	forn(i, n)
		ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1]));
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

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

typedef long long li;

using namespace std;

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

int n, k;
int a[N];
int len[N];
vector<int> rems[LOGN];
int pw[LOGN];

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i]);
	
	pw[0] = 1;
	forn(i, LOGN - 1)
		pw[i + 1] = pw[i] * 10 % k;
	
	forn(i, n){
		int x = a[i];
		while (x > 0){
			++len[i];
			x /= 10;
		}
		rems[len[i]].push_back(a[i] % k);
	}
	
	forn(i, LOGN)
		sort(rems[i].begin(), rems[i].end());
	
	li ans = 0;
	forn(i, n){
		for (int j = 1; j < LOGN; ++j){
			int rem = (a[i] * li(pw[j])) % k;
			int xrem = (k - rem) % k;
			auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem);
			auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem);
			ans += (r - l);
			if (len[i] == j && (rem + a[i] % k) % k == 0)
				--ans;
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 11;

int p[N];
int d[N];
vector<int> g[N];

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

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

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	set<pair<int, int>> st;
	for (int i = 0; i < n; ++i) {
		if (d[i] > 2) {
			st.insert(make_pair(-d[i], i));
		}
	}
	
	int ans = 0;
	while (!st.empty()) {
		int v = st.begin()->second;
		v = p[v];
		++ans;
		auto it = st.find(make_pair(-d[v], v));
		if (it != st.end()) {
			st.erase(it);
		}
		for (auto to : g[v]) {
			auto it = st.find(make_pair(-d[to], to));
			if (it != st.end()) {
				st.erase(it);
			}
		}
	}
	
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

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

typedef long long li;

using namespace std;

const int N = 1000 * 1000;

int lens[N];
int k;

li solve(li a, li b){
	k = 0;
	for (li i = 1; i * i <= b; ++i)
		if (b % i == 0)
			lens[k++] = i;
	
	li ans = 2 * (a + b) + 2;
	li x = a + b;
	int l = 0;
	for (li i = 1; i * i <= x; ++i){
		if (x % i == 0){
			while (l + 1 < k && lens[l + 1] <= i)
				++l;
			if (b / lens[l] <= x / i)
				ans = min(ans, (i + x / i) * 2);
		}
	}
	
	return ans;
}

int main() {
	li a, b;
	scanf("%lld%lld", &a, &b);
	printf("%lld\n", min(solve(a, b), solve(b, a)));
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m + 2);
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		++cnt[l];
		--cnt[r + 1];
	}
	for (int i = 1; i <= m; ++i)
		cnt[i] += cnt[i - 1];
	
	vector<int> ans;
	for (int i = 1; i <= m; ++i) {
		if (cnt[i] == 0)
			ans.push_back(i);
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it << " ";
	cout << endl;
	
	return 0;
}

n, m = map(int, input().split())
seg = [list(map(int, input().split())) for i in range(n)]
def bad(x):
	for i in range(n):
		if (seg[i][0] <= x and x <= seg[i][1]): return False
	return True
ans = list(filter(bad, [i for i in range(1, m + 1)]))
print(len(ans))
print(' '.join([str(x) for x in ans]))

#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, t;
	cin >> n >> s >> t;
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		if (s[i] == t[i]) continue;
		int pos = -1;
		for (int j = i + 1; j < n; ++j) {
			if (s[j] == t[i]) {
			        pos = j;
			        break;
			}
		}
		if (pos == -1) {
			cout << -1 << endl;
			return 0;
		}
		for (int j = pos - 1; j >= i; --j) {
			swap(s[j], s[j + 1]);
			ans.push_back(j);
		}
	}
	
	assert(s == t);
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a(n);
	long long sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first >> a[i].second;
		sum += a[i].first;
	}
	
	sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b) { return a.first - a.second > b.first - b.second; });
	
	for (int i = 0; i < n; ++i) {
		if (sum <= m) {
			cout << i << endl;
			return 0;
		}
		sum -= a[i].first - a[i].second;
	}
	
	if (sum <= m)
		cout << n << endl;
	else
		cout << -1 << endl;
	
	return 0;
}

def step(cur, x):
    if(cur - x > 0):
        return cur - x
    else:
        return cur + x



n, k, s = map(int, input().split())
cur = 1

if(k > s or k * (n - 1) < s):
    print('NO')
else:
    print('YES')
    while(k > 0):
        l = min(n - 1, s - (k - 1))
        cur = step(cur, l)
        print(cur, end = ' ')
        s -= l
        k -= 1

#include <bits/stdc++.h>

using namespace std;

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

const int dx[] = {1, 0, -1,  0};
const int dy[] = {0, 1,  0, -1};
const int N = 1001;

int n, m;
vector<string> f;
int d[N][N][4];
int r[N][N], a[N][N], b[N][N];

int getd(int i, int j, int k) {
    int dxk = dx[k];
    int dyk = dy[k];
    int result = 0;
    while (i >= 0 && i < n && j >= 0 && j < m && f[i][j] == '*')
        result++, i += dxk, j += dyk;
    return result;
}

int main() {
    cin >> n >> m;
    f = vector<string>(n);
    forn(i, n)
        cin >> f[i];
    
    memset(d, -1, sizeof(d));
    int result = 0;
    for (int i = 1; i + 1 < n; i++)
        for (int j = 1; j + 1 < m; j++)
            if (f[i][j] == '*') {
                bool around = true;
                forn(k, 4)
                    around = around && (f[i + dx[k]][j + dy[k]] == '*');
                if (around) {
                    r[i][j] = INT_MAX;
                    forn(k, 4)
                        r[i][j] = min(r[i][j], getd(i, j, k) - 1);
                    result++;
                    a[i][j - r[i][j]] = max(a[i][j - r[i][j]], 2 * r[i][j] + 1);
                    b[i - r[i][j]][j] = max(b[i - r[i][j]][j], 2 * r[i][j] + 1);
                }
            }

    vector<string> g(n, string(m, '.'));
    forn(i, n) {
        int v = 0;
        forn(j, m) {
            v = max(v - 1, a[i][j]);
            if (v > 0)
                g[i][j] = '*';
        }
    }
    forn(j, m) {
        int v = 0;
        forn(i, n) {
            v = max(v - 1, b[i][j]);
            if (v > 0)
                g[i][j] = '*';
        }
    }
    
    if (f == g) {
        cout << result << endl;
        forn(i, n)
            forn(j, m)
                if (r[i][j] > 0)
                    cout << i + 1 << " " << j + 1 << " " << r[i][j] << endl;
    } else
        cout << -1 << endl;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<string> s;

vector<string> draw(const vector<pair<pair<int, int>, int>> &r) {
	vector<string> f(n, string(m, '.'));
	vector<vector<int>> h(n, vector<int>(m));
	vector<vector<int>> v(n, vector<int>(m));
	for (auto it : r) {
		int x = it.first.first;
		int y = it.first.second;
		int len = it.second;
		++v[x - len][y];
		if (x + len + 1 < n)
			--v[x + len + 1][y];
		++h[x][y - len];
		if (y + len + 1 < m)
			--h[x][y + len + 1];	
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) v[i][j] += v[i - 1][j];
			if (j > 0) h[i][j] += h[i][j - 1];
			if (v[i][j] > 0 || h[i][j] > 0)
				f[i][j] = '*';
		}
	}
	return f;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	s = vector<string>(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	
	vector<vector<int>> l(n, vector<int>(m));
	vector<vector<int>> r(n, vector<int>(m));
	vector<vector<int>> u(n, vector<int>(m));
	vector<vector<int>> d(n, vector<int>(m));
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) {
				if (s[i][j] != '.')
					u[i][j] = u[i - 1][j] + 1;
			} else {
				u[i][j] = s[i][j] != '.';
			}
			if (j > 0) {
				if (s[i][j] != '.')
					l[i][j] = l[i][j - 1] + 1;
			} else {
				l[i][j] = s[i][j] != '.';
			}
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = m - 1; j >= 0; --j) {
			if (i < n - 1) {
				if (s[i][j] != '.')
					d[i][j] = d[i + 1][j] + 1;
			} else {
				d[i][j] = s[i][j] != '.';
			}
			if (j < m - 1) {
				if (s[i][j] != '.')
					r[i][j] = r[i][j + 1] + 1;
			} else {
				r[i][j] = s[i][j] != '.';
			}
		}
	}
	
	vector<pair<pair<int, int>, int>> ans;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (s[i][j] == '*') {
				int len = min(min(u[i][j], l[i][j]), min(d[i][j], r[i][j])) - 1;
				if (len != 0) {
					ans.push_back(make_pair(make_pair(i, j), len));
				}
			}
		}
	}
	
	if (draw(ans) != s) {
		cout << -1 << endl;
	} else {
		cout << ans.size() << endl;
		for (auto it : ans) {
			cout << it.first.first + 1 << " " << it.first.second + 1 << " " << it.second << endl; 
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 203;
const int MOD = 1e9 + 7;

int n, ssz;
string s;
int len[N][2];
int dp[N][N][N][2];

int calc(const string &t) {
	int tsz = t.size();
	for (int i = tsz; i > 0; --i) {
		if (s.substr(0, i) == t.substr(tsz - i, i))
			return i;
	}
	return 0;
}

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> s;
	ssz = s.size();
	
	if (s[0] == '(')
		len[0][0] = 1;
	else
		len[0][1] = 1;
	
	string pref;
	for (int i = 0; i < ssz; ++i) {
		pref += s[i];
		pref += '(';
		len[i + 1][0] = calc(pref);
		pref.pop_back();
		pref += ')';
		len[i + 1][1] = calc(pref);
		pref.pop_back();
	}
	
	dp[0][0][0][0] = 1;
	for (int i = 0; i < 2 * n; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int pos = 0; pos <= ssz; ++pos) {
				for (int f = 0; f < 2; ++f) {
					if (dp[i][j][pos][f] == 0) continue;
					if (j + 1 <= n)
						add(dp[i + 1][j + 1][len[pos][0]][f | (len[pos][0] == ssz)], dp[i][j][pos][f]);
					if (j > 0)
						add(dp[i + 1][j - 1][len[pos][1]][f | (len[pos][1] == ssz)], dp[i][j][pos][f]);
				}
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i <= ssz; ++i)
		add(ans, dp[2 * n][0][i][1]);
		
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		cout << x - !(x & 1) << " ";
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin); 
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> res(n);
	vector<int> a(n); 
	for (int i = 0; i < n; ++i) {
		cin >> res[i].first;
		a[i] = res[i].first;
		res[i].second = i + 1;
	}
	
	sort(res.begin(), res.end());
	reverse(res.begin(), res.end());
	sort(res.begin(), res.begin() + k, [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
	
	int lst = 0, sum = 0;
	for (int i = 0; i < k - 1; ++i) {
	    sum += *max_element(a.begin() + lst, a.begin() + res[i].second);
		lst = res[i].second;	
	}
	sum += *max_element(a.begin() + lst, a.end());
	cout << sum << endl;
	

	lst = 0;
	for (int i = 0; i < k - 1; ++i) {
		cout << res[i].second - lst << " ";
		lst = res[i].second;	
	}
	cout << n - lst << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
		
	set<long long> sum;
	long long l = 0;
	for (int i = 0; i < n; ++i) {
		l += a[i];
		sum.insert(l);
	}
	
	long long ans = 0;
	long long r = 0;
	for (int i = n - 1; i >= 0; --i) {
		sum.erase(l);
		l -= a[i];
		r += a[i];
		if (sum.count(r))
			ans = max(ans, r);
	}
	
	cout << ans << endl;
	
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int n;
int a[200005];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	cin >> n;
	for (int i=1; i<=n; i++)
		cin >> a[i];

	int i = 0, j = n+1;
	ll zi = 0, zj = 0, solidx = 0;
	while (i < j) {
		if (zi < zj)
			zi += a[++i];
		else if (zi > zj)
			zj += a[--j];
		else {
			solidx = i;
			zi += a[++i];
			zj += a[--j];
		}
	}
	
	cout << accumulate(a+1, a+solidx+1, 0ll); // here
}

#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);
 
int n;
string s, t;

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

void solve() {
	int ans = 0;
	forn(i, n / 2) {
		map<char, int> a;
		a[s[i]]++; a[s[n - i - 1]]++;
		a[t[i]]++; a[t[n - i - 1]]++;
		if (sz(a) == 4)
			ans += 2;
		else if (sz(a) == 3)
			ans += 1 + (s[i] == s[n - i - 1]);
		else if (sz(a) == 2)
			ans += a[s[i]] != 2;
	}
	
	if (n % 2 == 1 && s[n / 2] != t[n / 2])
		ans++;
		
	cout << ans << endl;
}
 
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>

using namespace std;

int n, q;
vector<vector<int>> tree;

int current_preorder;
vector<int> preorder, max_preorder;
vector<int> sorted_by_preorder;

void Dfs(int w) {
  sorted_by_preorder[current_preorder] = w;
  preorder[w] = current_preorder++;
  for (int c : tree[w]) {
    Dfs(c);
  }
  max_preorder[w] = current_preorder - 1;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  assert(2 <= n);
  assert(1 <= q);
  tree.resize(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p--;
    assert(0 <= p and p < n);
    tree[p].push_back(i);
  }

  preorder.resize(n);
  max_preorder.resize(n);
  sorted_by_preorder.resize(n);
  current_preorder = 0;
  Dfs(0);

  for (int i = 0; i < q; i++) {
    int u, k;
    cin >> u >> k;
    u--; k--;
    assert(0 <= u and u < n);
    assert(0 <= k and k < n);
    k += preorder[u];
    int answer = -1;
    if (k <= max_preorder[u]) {
      answer = sorted_by_preorder[k] + 1;
      assert(1 <= answer and answer <= n);
    }
    cout << answer << '\n';
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

map<long long, int> v[N][N];

int n, m;
int half;
long long k;
long long a[N][N];
long long ans;

void calclf(int x, int y, long long val, int cnt) {
	val ^= a[x][y];
	if (cnt == half) {
		++v[x][y][val];
		return;
	}
	if (x + 1 < n)
		calclf(x + 1, y, val, cnt + 1);
	if (y + 1 < m)
		calclf(x, y + 1, val, cnt + 1);
}

void calcrg(int x, int y, long long val, int cnt) {
	if (cnt == n + m - 2 - half) {
		if (v[x][y].count(k ^ val))
			ans += v[x][y][k ^ val];
		return;
	}
	if (x > 0)
		calcrg(x - 1, y, val ^ a[x][y], cnt + 1);
	if (y > 0)
		calcrg(x, y - 1, val ^ a[x][y], cnt + 1);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> k;
	half = (n + m - 2) / 2;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	
	calclf(0, 0, 0, 0);
	calcrg(n - 1, m - 1, 0, 0);
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	
	vector<int> cnt(101);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	
	cout << *max_element(cnt.begin(), cnt.end()) << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int a, b, x;
	cin >> a >> b >> x;
	
	if (x % 2 == 0) {
		if (a > b) {
			for (int i = 0; i < x / 2; ++i)
				cout << "01";
			cout << string(b - x / 2, '1');
			cout << string(a - x / 2, '0');
		} else {
			for (int i = 0; i < x / 2; ++i)
				cout << "10";
			cout << string(a - x / 2, '0');
			cout << string(b - x / 2, '1');
		}
	} else if (a > b) {
		for (int i = 0; i < x / 2; ++i)
			cout << "01";
		cout << string(a - x / 2, '0');
		cout << string(b - x / 2, '1');
	} else {
		for (int i = 0; i < x / 2; ++i)
			cout << "10";
		cout << string(b - x / 2, '1');
		cout << string(a - x / 2, '0');
	}
	cout << endl;
	
	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(2e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 10000 + 7;

int n, k;
int a[N];

bool read () {
	if (scanf("%d%d", &n, &k) != 2)
		return false;
	forn(i, n) scanf("%d", &a[i]);
	return true;
}

int pr[N];

void solve() {
	pr[0] = 0;
	forn(i, n) pr[i + 1] = pr[i] + a[i];
	
	ld ans = 0;
	forn(r, n) forn(l, r + 1){
		if (r - l + 1 >= k){
			ans = max(ans, (pr[r + 1] - pr[l]) / ld(r - l + 1));
		}
	}
	
	printf("%.15f\n", double(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;

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

	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, q;
	cin >> n >> q;
	
	vector<int> cnt(31);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[__builtin_ctz(x)];
	}
	
	while (q--) {
		int x;
		cin >> x;
		
		int ans = 0;
		for (int i = 30; i >= 0 && x > 0; --i) {
			int need = min(x >> i, cnt[i]);
			ans += need;
			x -= (1 << i) * need;
		}
		
		if (x > 0)
			ans = -1;
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, d, k;
	cin >> n >> d >> k;
	
	if (d >= n) {
		cout << "NO" << endl;
		return 0;
	}
	
	vector<int> deg(n);
	vector<pair<int, int>> ans;
	set<pair<int, int>> q;
	
	for (int i = 0; i < d; ++i) {
		++deg[i];
		++deg[i + 1];
		if (deg[i] > k || deg[i + 1] > k) {
			cout << "NO" << endl;
			return 0;
		}
		ans.push_back(make_pair(i, i + 1));
	}
	for (int i = 1; i < d; ++i)
		q.insert(make_pair(max(i, d - i), i));
	
	for (int i = d + 1; i < n; ++i) {
		while (!q.empty() && deg[q.begin()->second] == k)
			q.erase(q.begin());
		if (q.empty() || q.begin()->first == d) {
			cout << "NO" << endl;
			return 0;
		}
		++deg[i];
		++deg[q.begin()->second];
		ans.push_back(make_pair(i, q.begin()->second));
		q.insert(make_pair(q.begin()->first + 1, i));
	}
	
	assert(int(ans.size()) == n - 1);
	cout << "YES" << endl;
	vector<int> p(n);
	for (int i = 0; i < n; i++)
	    p[i] = i;
	random_shuffle(p.begin(), p.end());
	for (int i = 0; i < n - 1; ++i)
	    if (rand() % 2)
		    cout << p[ans[i].first] + 1 << " " << p[ans[i].second] + 1 << endl;
		else
		    cout << p[ans[i].second] + 1 << " " << p[ans[i].first] + 1 << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 303;

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

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

	cin >> n;
	int allsum = n - 1;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		allsum += s[i].size();
	}
	
	for (int i = 0; i < n; ++i) {
		eq[i][i] = true;
		for (int j = 0; j < i; ++j) {
			eq[i][j] = eq[j][i] = s[i] == s[j];
		}
	}
	
	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j >= 0; --j) {
			if (eq[i][j]) {
				if (i + 1 < n && j + 1 < n)
					dp[i][j] = dp[i + 1][j + 1] + 1;
				else
					dp[i][j] = 1;
			}
		}
	}
	
	int ans = allsum;
	for (int i = 0; i < n; ++i) {
		int sum = 0;
		for (int j = 0; i + j < n; ++j) {
			sum += s[i + j].size();
			int cnt = 1;
			for (int pos = i + j + 1; pos < n; ++pos) {
				if (dp[i][pos] > j) {
					++cnt;
					pos += j;
				}
			}
			int cur = allsum - sum * cnt + (j + 1) * cnt - j * cnt;
			if (cnt > 1 && ans > cur) {
				ans = cur;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	
	int ans = 0;
	while (!a.empty() && a.back() <= k) {
		++ans;
		a.pop_back();
	}
	reverse(a.begin(), a.end());
	while (!a.empty() && a.back() <= k) {
		++ans;
		a.pop_back();
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	vector<int> cnt(26);
	for (auto c : s) ++cnt[c - 'a'];

	int pos = 26;
	for (int i = 0; i < 26; ++i) {
		if (k >= cnt[i]) {
			k -= cnt[i];
		} else {
			pos = i;
			break;
		}
	}
	
	string ans;
	int rem = k;
	for (auto c : s) {
		int cur = c - 'a';
		if (cur > pos || (cur == pos && rem == 0)) {
			ans += c;
		} else if (cur == pos) {
			--rem;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;

	vector<pair<char, int>> c(n);
	for (int i = 0; i < n; ++i)
		c[i] = make_pair(s[i], i);
	sort(c.begin(), c.end());
	sort(c.begin() + k, c.end(), [&] (const pair<char, int> &a, const pair<char, int> &b) {
		return a.second < b.second;
	});
	
	for (int i = k; i < n; ++i)
		cout << c[i].first;
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	int k = n / m;
	vector<int> a(n);
	vector<vector<int>> val(m);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		val[a[i] % m].push_back(i);
	}
	
	long long ans = 0;
	vector<pair<int, int>> fre;
	for (int i = 0; i < 2 * m; ++i) {
		int cur = i % m;
		while (int(val[cur].size()) > k) {
			int elem = val[cur].back();
			val[cur].pop_back();
			fre.push_back(make_pair(elem, i));
		}
		while (int(val[cur].size()) < k && !fre.empty()) {
			int elem = fre.back().first;
			int mmod = fre.back().second;
			fre.pop_back();
			val[cur].push_back(elem);
			a[elem] += i - mmod;
			ans += i - mmod;
		}
	}
	
	cout << ans << endl;
	for (int i = 0; i < n; ++i)
		cout << a[i] << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

int n, m, s;
vector<int> g[N];
bool used[N];
bool ok[N];

int cnt;

void dfs1(int v) {
	ok[v] = true;
	for (auto to : g[v])
		if (!ok[to])
			dfs1(to);
}

void dfs2(int v) {
	used[v] = true;
	++cnt;
	for (auto to : g[v])
		if (!used[to] && !ok[to])
			dfs2(to);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> s;
	--s;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
	}
	
	dfs1(s);
	
	vector<pair<int, int>> val;
	for (int i = 0; i < n; ++i) {
		if (!ok[i]) {
			cnt = 0;
			memset(used, false, sizeof(used));
			dfs2(i);
			val.push_back(make_pair(cnt, i));
		}
	}
	sort(val.begin(), val.end());
	reverse(val.begin(), val.end());
	
	int ans = 0;
	for (auto it : val) {
		if (!ok[it.second]) {
			++ans;
			dfs1(it.second);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

int n, m, s;
vector<int> g[N];
vector<int> tg[N];
vector<int> cg[N];
vector<int> ord;
int indeg[N];
bool ucomp[N];
bool used[N];
int comp[N];
int cnt;

void dfs1(int v) {
	used[v] = true;
	for (auto to : g[v])
		if (!used[to])
			dfs1(to);
	ord.push_back(v);
}

void dfs2(int v) {
	comp[v] = cnt;
	for (auto to : tg[v])
		if (comp[to] == -1)
			dfs2(to);
}

void dfs3(int v) {
	ucomp[v] = true;
	for (auto to : cg[v])
		if (!ucomp[to])
			dfs3(to);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> s;
	--s;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		tg[y].push_back(x);
	}
	
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			dfs1(i);
		}
	}
	
	reverse(ord.begin(), ord.end());
	memset(comp, -1, sizeof(comp));
	for (int i = 0; i < n; ++i) {
		if (comp[ord[i]] == -1) {
			dfs2(ord[i]);
			++cnt;
		}
	}
	
	for (int v = 0; v < n; ++v) {
		for (auto to : g[v]) {
			if (comp[v] != comp[to]) {
				cg[comp[v]].push_back(comp[to]);
				++indeg[comp[to]];
			}
		}
	}
	
	dfs3(comp[s]);
	int ans = 0;
	for (int i = 0; i < cnt; ++i)
		if (!ucomp[i] && indeg[i] == 0)
			++ans;
			
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 520;
const int K = 12;
const int C = 100 * 1000 + 11;

int n, k;
int c[C];
int f[C];
vector<int> h;

int dp[N][K * N];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k;
	h = vector<int>(k + 1);
	for (int i = 0; i < n * k; ++i) {
		int x;
		cin >> x;
		++c[x];
	}
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++f[x];
	}
	for (int i = 1; i <= k; ++i)
		cin >> h[i];
		
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= n * k; ++j) {
			for (int cur = 0; cur <= k; ++cur) {
				dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]);
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < C; ++i) {
		if (f[i] != 0) ans += dp[f[i]][c[i]];
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	set<int> el;
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		if (!el.count(x)) {
			ans.push_back(i);
			el.insert(x);
		}
	}
	
	if (int(ans.size()) < k) {
		cout << "NO\n";
	} else {
		cout << "YES\n";
		for (int i = 0; i < k; ++i)
			cout << ans[i] + 1 << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; ++i)
		cin >> s[i];
		
	sort(s.begin(), s.end(), [&] (const string &s, const string &t) {
		return s.size() < t.size();
	});
	
	for (int i = 0; i < n - 1; ++i) {
		if (s[i + 1].find(s[i]) == string::npos) {
			cout << "NO\n";
			return 0;
		}
	}
	
	cout << "YES\n";
	for (auto it : s)
		cout << it << 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 k;
	cin >> k;
	vector<pair<int, pair<int, int>>> a;
	for (int i = 0; i < k; ++i) {
		int n;
		cin >> n;
		vector<int> x(n);
		for (int j = 0; j < n; ++j)
			cin >> x[j];
		int sum = accumulate(x.begin(), x.end(), 0);
		for (int j = 0; j < n; ++j)
			a.push_back(make_pair(sum - x[j], make_pair(i, j)));
	}
	
	stable_sort(a.begin(), a.end());
	for (int i = 0; i < int(a.size()) - 1; ++i) {
		if (a[i].first == a[i + 1].first && (a[i].second.first != a[i + 1].second.first)) {
			cout << "YES" << endl;
			cout << a[i + 1].second.first + 1 << " " << a[i + 1].second.second + 1 << endl;
			cout << a[i].second.first + 1 << " " << a[i].second.second + 1 << endl;
			return 0;
		}
	}
	
	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;
	cin >> n;
	vector<int> x(n);
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	
	sort(x.begin(), x.end());
	vector<int> res = { x[0] };
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 31; ++j) {
			int lx = x[i] - (1 << j);
			int rx = x[i] + (1 << j);
			bool isl = binary_search(x.begin(), x.end(), lx);
			bool isr = binary_search(x.begin(), x.end(), rx);
			if (isl && isr && int(res.size()) < 3) {
				res = { lx, x[i], rx };
			}
			if (isl && int(res.size()) < 2) {
				res = { lx, x[i] };
			}
			if (isr && int(res.size()) < 2) {
				res = { x[i], rx };
			}
		}
	}
	
	cout << int(res.size()) << endl;
	for (auto it : res)
		cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000 * 1000 * 1000;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	long long n;
	cin >> n;
	
	string s = to_string(n);
	
	int ans = INF;
	
	int len = s.size();
	for (int i = 0; i < len; ++i) {
		for (int j = 0; j < len; ++j) {
			if (i == j) continue;
			string t = s;
			int cur = 0;
			for (int k = i; k < len - 1; ++k) {
				swap(t[k], t[k + 1]);
				++cur;
			}
			
			for (int k = j - (j > i); k < len - 2; ++k) {
				swap(t[k], t[k + 1]);
				++cur;
			}
			
			int pos = -1;
			for (int k = 0; k < len; ++k) {
				if (t[k] != '0') {
					pos = k;
					break;
				}
			}
			
			for (int k = pos; k > 0; --k) {
				swap(t[k], t[k - 1]);
				++cur;
			}
			
			long long nn = atoll(t.c_str());
			if (nn % 25 == 0)
				ans = min(ans, cur);
		}
	}
	
	if (ans == INF)
		ans = -1;
		
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000 * 1000 * 1000;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int a, n, m;
	cin >> a >> n >> m;
	vector<int> rain(a + 1);
	vector<pair<int, int>> umb(a + 1, make_pair(INF, -1));
	vector<int> costs(m);
	
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		for (int j = l; j < r; ++j)
			rain[j] = 1;
	}
	
	for (int i = 0; i < m; ++i) {
		int x, p;
		cin >> x >> p;
		costs[i] = p;
		umb[x] = min(umb[x], make_pair(p, i));
	}
	
	vector<vector<int>> dp(a + 1, vector<int>(m + 1, INF));
	dp[0][m] = 0;
	for (int i = 0; i < a; ++i) {
		for (int j = 0; j <= m; ++j) {
			if (dp[i][j] == INF)
				continue;
			if (rain[i] == 0)
				dp[i + 1][m] = min(dp[i + 1][m], dp[i][j]);
			if (j < m)
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[j]);
			if (umb[i].first != INF)
				dp[i + 1][umb[i].second] = min(dp[i + 1][umb[i].second], dp[i][j] + umb[i].first);
		}
	}
	
	int ans = INF;
	for (int i = 0; i <= m; ++i)
		ans = min(ans, dp[a][i]);
	if (ans == INF)
		ans = -1;
	cout << ans << endl;
	
	return 0;
}

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
 
#include <stdio.h>
#include <bits/stdc++.h>
 
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
 
using namespace std;
 
inline void setmin(int &x, int y) { if (y < x) x = y; }
inline void setmax(int &x, int y) { if (y > x) x = y; }
inline void setmin(ll &x, ll y) { if (y < x) x = y; }
inline void setmax(ll &x, ll y) { if (y > x) x = y; }
 
const int N = 2001;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

struct Line
{
    ll k, b;
    Line() {}
    Line(ll k, ll b) : k(k), b(b) {}
    ll val(ll x) { return k * x + b; }
};

int cnt_v;
Line tree[N * 4];

void build(int n)
{
    cnt_v = 1;
    while (cnt_v < n)
        cnt_v <<= 1;
    rep(i, 0, cnt_v * 2 - 1)
        tree[i] = Line(0, inf);
}

void upd(int x, int lx, int rx, int l, int r, Line line)
{
    if (lx >= r || l >= rx)
        return;
    else if (lx >= l && rx <= r)
    {
        int m = (lx + rx) / 2;
        if (line.val(m) < tree[x].val(m))
            swap(tree[x], line);
        if (rx - lx == 1)
            return;
        if (line.val(lx) < tree[x].val(lx))
            upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
        else
            upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
    }
    else
    {
        upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
        upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
    }
}

ll get(ll p)
{
    int x = p + cnt_v - 1;
    ll res = tree[x].val(p);
    while (x > 0)
    {
        x = (x - 1) / 2;
        setmin(res, tree[x].val(p));
    }
    return res;
}

int add[N];
int best[N];

ll dp[N];

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 0.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int L, n, m;
    cin >> L >> n >> m;

    rep(i, 0, n)
    {
        int l, r;
        cin >> l >> r;
        add[l]++;
        add[r]--;
    }
    rep(i, 1, L + 1)
        add[i] += add[i - 1];

    fill(best, best + L + 1, inf);
    rep(i, 0, m)
    {
        int x, p;
        cin >> x >> p;
        setmin(best[x], p);
    }

    // dp[i] + best[i] * (j - i) = best[i] * j + (dp[i] - best[i] * i)
    build(L + 1);
    fill(dp, dp + L + 1, inf);
    dp[0] = 0;
    upd(0, 0, cnt_v, 0 + 1, cnt_v, Line(best[0], dp[0] - best[0] * 0));
    rep(i, 1, L + 1)
    {
        dp[i] = get(i);
        if (add[i - 1] == 0)
            setmin(dp[i], dp[i - 1]);
        upd(0, 0, cnt_v, i + 1, cnt_v, Line(best[i], dp[i] - best[i] * i));
    }
    cout << (dp[L] != inf ? dp[L] : -1) << "\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, k;
	cin >> n >> k;
	
	for (int i = 0; i < k; ++i) {
		if (n % 10 == 0) n /= 10;
		else n--;
	}
	
	cout << n << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;
	string s;
	cin >> s;
	
	int res = 0;
	string ans;
	for (int i = 0; i < n - 1; ++i) {
		int cur = 0;
		for (int j = 0; j < n - 1; ++j)
			if (s[j] == s[i] && s[j + 1] == s[i + 1])
				++cur;
		if (res < cur) {
			res = cur;
			ans = string(1, s[i]) + string(1, s[i + 1]);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	
	sort(a.begin(), a.end());
	
	int ans;
	
	if (k == 0) {
		ans = a[0] - 1;
	} else {
		ans = a[k - 1];
	}
	
	int cnt = 0;
	
	for (int i = 0; i < n; ++i)
		if (a[i] <= ans) ++cnt;
	
	if (cnt != k || !(1 <= ans && ans <= 1000 * 1000 * 1000)) {
		puts("-1");
		return 0;
	}
	
	printf("%d\n", ans);
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int count3(LL x){
  int ret=0;
  while(x % 3 == 0){
    ret++;
    x /= 3;
  }
  return ret;
}
int n;
vector<pair<int,LL>> v;
int main(){
  cin>>n;
  v.resize(n);
  for(int i=0; i<n; i++){
    cin>>v[i].second;
    v[i].first=-count3(v[i].second);
  }
  sort(v.begin(), v.end());
  for(int i=0; i<n; i++)
    printf("%lld%c", v[i].second, " \n"[i + 1 == n]);
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 11;

int n, m;
int deg[N];
bool used[N];
vector<int> comp;
vector<int> g[N];

void dfs(int v) {
	used[v] = true;
	comp.push_back(v);
	
	for (auto to : g[v])
		if (!used[to])
			dfs(to);
}

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

	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
		++deg[x];
		++deg[y];
	}
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			comp.clear();
			dfs(i);
			bool ok = true;
			for (auto v : comp) ok &= deg[v] == 2;
			if (ok) ++ans;
		}
	}
	
	printf("%d\n", ans);
	
	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;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	
	map<int, int> dp;
	
	int ans = 0;
	int lst = 0;
	for (int i = 0; i < n; ++i) {
		int x = a[i];
		dp[x] = dp[x - 1] + 1;
		if (ans < dp[x]) {
			ans = dp[x];
			lst = x;
		}
	}
	
	vector<int> res;
	for (int i = n - 1; i >= 0; --i) {
		if (a[i] == lst) {
			res.push_back(i);
			--lst;
		}
	}
	reverse(res.begin(), res.end());
	
	printf("%d\n", ans);
	for (auto it : res)
		printf("%d ", it + 1);
	puts("");
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	string s;
	cin >> n >> s;
	if (n == 1) {
		cout << s << endl;
	} else {
		int cnt0 = 0;
		for (int i = 0; i < n; ++i)
			cnt0 += s[i] == '0';
		cout << 1;
		for (int i = 0; i < cnt0; ++i)
			cout << 0;
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
long long k;

int main() {
	scanf("%d%d%lld", &n, &m, &k);
	if (k < n){
		printf("%lld 1\n", k + 1);
		return 0;
	}
	k -= n;
	long long row = k / (m - 1);
	printf("%lld ", n - row);
	if (row & 1)
		printf("%lld\n", m - k % (m - 1));
	else
		printf("%lld\n", k % (m - 1) + 2);
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> pt;

const int N = 300 * 1000 + 13;

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

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d%d", &a[i].x.x, &a[i].x.y);
		a[i].y = i + 1;
	}
	
	sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;});
	
	set<pt> cur;
	forn(i, n){
		while (!cur.empty() && cur.begin()->x < a[i].x.x)
			cur.erase(cur.begin());
		if (!cur.empty() && (--cur.end())->x >= a[i].x.y){
			printf("%d %d\n", a[i].y, (--cur.end())->y);
			return 0;
		}
		cur.insert({a[i].x.y, a[i].y});
	}
	
	puts("-1 -1");
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;

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

vector<pt> construct(int st, vector<int> d){
	if (d.empty())
		return vector<pt>();
	
	vector<pt> res;
	forn(i, d[0])
		for (int j = st + i + 1; j <= st + d.back(); ++j)
			res.push_back({st + i, j});
	
	int nxt = st + d[0];
	for (int i = 1; i < int(d.size()); ++i)
		d[i] -= d[0];
	d.erase(d.begin());
	if (!d.empty())
		d.pop_back();
	
	auto tmp = construct(nxt, d);
	for (auto it : tmp)
		res.push_back(it);
	
	return res;
}

int main() {
	scanf("%d", &n);
	d.resize(n);
	forn(i, n)
		scanf("%d", &d[i]);
	auto res = construct(0, d);
	printf("%d\n", int(res.size()));
	for (auto it : res)
		printf("%d %d\n", it.first + 1, it.second + 1);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 9;

int n, a, b;
int hp[N], dmg[N];

bool cmp(int i, int j){
	if(hp[i] - dmg[i] != hp[j] - dmg[j])
		return hp[i] - dmg[i] > hp[j] - dmg[j];
	return i < j;
}

int get(int id){
	return  hp[id] > dmg[id]? hp[id] : dmg[id];
}

int main(){
	scanf("%d %d %d", &n, &a, &b);
	for(int i = 0; i < n; ++i)
		scanf("%d %d", hp + i, dmg + i);
	
	b = min(b, n);
	vector <int> p(n);
	for(int i = 0; i < n; ++i) p[i] = i;
	sort(p.begin(), p.end(), cmp);
	long long res = 0, sum = 0;
	for(int i = 0; i < n; ++i){
		int id = p[i];
		if(i < b) sum += get(id);
		else sum += dmg[id];
	}
	res = sum; 

	if(b == 0){
		printf("%lld\n", res);
		return 0;
	}
	
	long long x = (1LL << a);
	for(int i = 0; i < n; ++i){
		int id = p[i];
		long long nres = sum;
		if(i < b){ 
			nres -= get(id);
			nres += hp[id] * x;
			res = max(res, nres);
		}
		else{
			nres -= dmg[id];
			nres += hp[id] * x;			
			int id2 = p[b - 1];
			nres -= get(id2);
			nres += dmg[id2];
			res = max(res, nres);
			
		}		
	}
	
	printf("%lld\n", res);
	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

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

struct edge {
    int to, c, f, id;

    edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {}
};

vector<edge> es;
vector<int> g[N];

void add_edge(int fr, int to, int cap, int id) {
    g[fr].push_back(sz(es));
    es.emplace_back(to, cap, 0, id);
    g[to].push_back(sz(es));
    es.emplace_back(fr, 0, 0, id);
}

int pw[N];
int n1, n2, m;

inline bool read() {
    if(!(cin >> n1 >> n2 >> m))
        return false;

    fore(id, 0, m) {
        int u, v;
        assert(cin >> u >> v);
        u--, v--;

        pw[u]++;
        pw[n1 + v]++;

        add_edge(u, n1 + v, 1, id);
    }
    return true;
}

int d[N], q[N], hd, tl;
inline bool bfs(int s, int t, int n) {
    fore(i, 0, n)
        d[i] = INF;
    hd = tl = 0;

    d[s] = 0;
    q[tl++] = s;
    while(hd != tl) {
        int v = q[hd++];
        if(v == t)
            break;

        for(int id : g[v]) {
            if(es[id].c - es[id].f == 0)
                continue;

            int to = es[id].to;
            if(d[to] > d[v] + 1) {
                d[to] = d[v] + 1;
                q[tl++] = to;
            }
        }
    }
    return d[t] < INF;
}

int nxt[N];

int dfs(int v, int t, int mx) {
    if(v == t) return mx;
    if(mx == 0) return 0;

    int sum = 0;
    for(; nxt[v] < sz(g[v]); nxt[v]++) {
        int id = g[v][nxt[v]];
        int rem = es[id].c - es[id].f;
        int to = es[id].to;

        if(rem == 0 || d[to] != d[v] + 1)
            continue;

        int cur = 0;
        if((cur = dfs(to, t, min(mx - sum, rem))) > 0) {
            es[id].f += cur;
            es[id ^ 1].f -= cur;
            sum += cur;
        }

        if(sum == mx)
            break;
    }
    return sum;
}

inline int dinic(int s, int t, int n) {
    int mf = 0;
    while(bfs(s, t, n)) {
        fore(i, 0, n)
            nxt[i] = 0;

        int cf = 0;
        while((cf = dfs(s, t, INF)) > 0)
            mf += cf;
    }
    return mf;
}

vector<int> res[N];

inline void getCert(int k) {
    fore(v, 0, n1) {
        for(int id : g[v]) {
            if(es[id].to < n1 || es[id].to >= n1 + n2)
                continue;
            assert(es[id].c > 0);
            if(es[id].f > 0)
                continue;

            res[k].push_back(es[id].id);
        }
    }
}

void solve() {
    int cnt = *min_element(pw, pw + n1 + n2);

    int s = n1 + n2; int t = s + 1;
    fore(i, 0, n1)
        add_edge(s, i, pw[i] - cnt, -1);
    fore(i, n1, n1 + n2)
        add_edge(i, t, pw[i] - cnt, -1);

    int mf = 0, mn = cnt;
    while(mn >= 0) {
        mf += dinic(s, t, n1 + n2 + 2);
        getCert(mn);

        if(mn > 0) {
            for (int id : g[s]) {
                assert(es[id].id < 0);
                assert((id & 1) == 0);
                es[id].c++;
            }
            for (int id : g[t]) {
                assert(es[id].id < 0);
                assert(es[id].c == 0);
                es[id ^ 1].c++;
            }
        }
        mn--;
    }

    fore(i, 0, cnt + 1) {
        printf("%d ", sz(res[i]));
        for(int id : res[i])
            printf("%d ", id + 1);
        puts("");
    }
}

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

    if(read()) {
        solve();
    }
    return 0;
}