#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) ((x).begin()), ((x).end())
#define fi first
#define se second
typedef long long LL;
const LL infll = 1e18;
const int N = 200022;
mt19937 gene(233);
int vst[N], fa[N], siz[N], p[N];
int tim = 0;
bool banned[N];
LL w[N], a[N], mx[N];
vector<pair<int, LL> > e[N];
pair<LL, int> operator + (const pair<LL, int> & a, LL b) {
	return make_pair(a.fi + b, a.se);
}
struct MP {
	vector<int> vec;
	int operator [] (int x) const {
		return lower_bound(all(vec), x) - vec.begin();
	}
	int count(int x) {
		int pos = lower_bound(all(vec), x) - vec.begin();
		return pos < (int)vec.size() && vec[pos] == x;
	}
};
struct SGT {
	int n;
	int taglen;
	pair<LL, int> *a;
	LL *tag;
	void collect(int k) {
		a[k] = max(a[k * 2], a[k * 2 + 1]);
	}
	void apply(int k, LL delta) {
		a[k] = a[k] + delta;
		if(k < taglen) tag[k] += delta;
	}
	void pushdown(int k) {
		if(tag[k] == 0) return;
		apply(k * 2, tag[k]);
		apply(k * 2 + 1, tag[k]);
		tag[k] = 0;
	}

	void modify(int k, int le, int ri, int pos, pair<LL, int> val) {
		if(le == ri) {
			a[k] = val;
		}else {
			pushdown(k);
			int mid = (le + ri) / 2;
			if(pos <= mid) {
				modify(k * 2, le, mid, pos, val);
			}else {
				modify(k * 2 + 1, mid + 1, ri, pos, val);
			}
			collect(k);
		}
	}
	void add(int k, int le, int ri, int ql, int qr, LL val) {
		if(ql > qr) return;
		if(ql <= le && ri <= qr) {
			a[k] = a[k] + val;
			if(le != ri) tag[k] = tag[k] + val;
		}else {
			pushdown(k);
			int mid = (le + ri) / 2;
			if(ql <= mid) {
				add(k * 2, le, mid, ql, qr, val);
			}
			if(qr >= mid + 1) {
				add(k * 2 + 1, mid + 1, ri, ql, qr, val);
			}
			collect(k);
		}
	}
	pair<LL, int> getmax(int k, int le, int ri, int ql, int qr) {
		if(ql > qr) {
			return make_pair(-infll, -1);
		}
		if(ql <= le && ri <= qr) {
			return a[k];
		}else {
			pushdown(k);
			pair<LL, int> res{-infll, -1};
			int mid = (le + ri) / 2;
			if(ql <= mid) res = max(res, getmax(k * 2, le, mid, ql, qr));
			if(qr >= mid + 1) res = max(res, getmax(k * 2 + 1, mid + 1, ri, ql, qr));

			return res;
		}
	}
};
struct Dnode {
	int rt;
	int n;
	MP mp;
	int *blg;
	LL * dep;
	SGT sgt;
	int * bg, *ed;
	LL tag;
	LL len;
	pair<LL, int> *a;
	Dnode ** s;
	int * sid;
	void resize(int n) {
		bg = new int[n];
		ed = new int[n];
		blg = new int[n];
		dep = new LL[n];
	}
} dn_pool[200033];
int dn_num = 0;
void dfs(Dnode & dn, int v) {
	int mpv = dn.mp[v];
	dn.bg[mpv] = ++dn.n;
	int _ = 0;
	for(auto t : e[v]) {
		int y = t.fi;
		if(banned[y]) {
			_++;
			continue;
		}
		int mpy = dn.mp[y];
		if(fa[v] != y) {
			fa[y] = v;
			dn.dep[mpy] = dn.dep[mpv] + t.se;
			dn.blg[mpy] = fa[v] == -1 ? _ : dn.blg[mpv];
			dfs(dn, y);
		}
		_++;
	}
	dn.ed[mpv] = dn.n;
}
Dnode * dvcq(int st) {
	assert(!banned[st]);
	Dnode &dn = dn_pool[dn_num++];
	MP &mp(dn.mp);
	//printf("dvcq %d\n", st);
	vector<int> q;
	q.pb(st);
	mp.vec.pb(st);
	tim++;
	vst[st] = tim;
	fa[st] = -1;
	for(int op = 0; op < (int)q.size(); op++) {
		int v = q[op];
		siz[v] = 0;
		//printf("v = %d\n", v);
		//if(v != st && banned[v]) continue;
		for(auto t : e[v]) {
			int y = t.fi;
			//printf("%d->%d\n", v, y);
			if(banned[y]) continue;
			if(vst[y] != tim) {
				vst[y] = tim;
				q.pb(y);
				mp.vec.pb(y);
				fa[y] = v;
			}
		}
	}
	sort(all(mp.vec));
	for(int i = (int)q.size() - 1; i >= 0; i--) {
		siz[q[i]]++;
		if(fa[q[i]] != -1) siz[fa[q[i]]] += siz[q[i]];
	}
	//cout << "q" << q.size() << endl;
	dn.resize(q.size());

	int rt = st;

	for(;;) {
		bool flag = true;
		for(auto t : e[rt]) {
			int y = t.fi;
			if(banned[y]) continue;
			if(fa[y] == rt && siz[y] > q.size() / 2) {
				rt = y;
				flag = false;
				break;
			}
		}
		if(flag) break;
	}
	dn.rt = rt;

	//cout << "vertices: ";
	//for(int i : q) cout << i << ' ';
	//cout << endl;
	dn.dep[mp[rt]] = 0;
	for(int v : q) fa[v] = -1;
	dn.blg[mp[rt]] = -1;
	dn.n = 0;
	dfs(dn, rt);

	if(q.size() == 1) {
		dn.a = new pair<LL, int>[1];
		dn.a[0] = make_pair(-a[rt], rt);
		/*		dn.len = dn.dep[mp[q[0]]] + dn.dep[mp[q[1]]];
				dn.a = new pair<LL, int>[2];
				dn.a[mp[q[0]]] = make_pair(-a[q[0]], q[0]);
				dn.a[mp[q[1]]] = make_pair(-a[q[1]], q[1]);*/
		return &dn;
	}
	dn.sgt.n = dn.n;
	dn.sgt.a = new pair<LL, int>[4 * (1 << ilogb(dn.n))];
	dn.sgt.tag = new LL[2 * (1 << ilogb(dn.n))];
	dn.sgt.a -= 1;
	dn.sgt.tag -= 1;
	dn.sgt.taglen = 2 * (1 << ilogb(dn.n)) + 1;
	for(int v : q) {
		int mpv = mp[v];
		dn.sgt.modify(1, 1, dn.n, dn.bg[mpv], make_pair(dn.dep[mpv] - a[v], -v));
		//printf("modify %d %d %d\n", v, dn.bg[mpv], dn.dep[mpv] - a[v]);
	}

	dn.s = new Dnode*[e[rt].size()];
	dn.sid = new int[e[rt].size()];
	vector<pair<int, LL> > bak(1);
	swap(bak, e[rt]);
	banned[rt] = true;
	for(int i = 0; i < (int)bak.size(); i++) {
		//printf("-? %d %d %d\n", rt, bak[i].fi, e[rt].size());
		e[rt][0] = bak[i];
		dn.s[i] = banned[bak[i].fi] ? NULL : dvcq(bak[i].fi);
		dn.sid[i] = mp[bak[i].fi];
	}
	swap(bak, e[rt]);
	return &dn;
}
void add(Dnode * p, int y, int fa, LL w) {
	if(p->mp.count(y) == 0) return;
	int mpy = p->mp[y];
	int mpp = p->mp.count(fa) ? p->mp[fa] : -1;
	if(p->sgt.n == 0) {
		p->a[0] = p->a[0] + w;
		/*if(mpp != -1) {
		  p->a[mpy] = p->a[mpy] + w;
		  }else {
		  p->a[0] = p->a[0] + w;
		  p->a[1] = p->a[1] + w;
		  }*/
		//printf("%d %lld %d %lld %d\n", y, p->a[0].fi, p->a[0].se, p->a[1].fi, p->a[1].se);
		return;
	}
	//printf("add %d %d\n", y, p->rt);
	if(mpp != -1 && p->bg[mpp] > p->bg[mpy]) {
		//printf("@@%d %d\n", p->bg[mpp], p->ed[mpp]);
		//printf("%lld %d\n", p->sgt.a[1].fi, p->sgt.a[1].se);
		p->tag += w;
		//		p->sgt.add(1, 1, p->sgt.n, 1, p->bg[mpp] - 1, w);
		//	printf("%lld %d\n", p->sgt.a[1].fi, p->sgt.a[1].se);
		//		p->sgt.add(1, 1, p->sgt.n, p->ed[mpp] + 1, p->sgt.n, w);
		p->sgt.add(1, 1, p->sgt.n, p->bg[mpp], p->ed[mpp], -w);
		p->s[p->blg[mpp]]->tag -= w;
		//printf("%lld %d\n", p->sgt.a[1].fi, p->sgt.a[1].se);
		add(p->s[p->blg[mpp]], y, fa, w);
	}else if(y == p->rt || y == 1) {
		//printf("!!!!!!!%d %lld\n", y, w);
		//p->sgt.add(1, 1, p->sgt.n, 1, p->sgt.n, w);
		p->tag += w;
	}else {
		p->sgt.add(1,1, p->sgt.n, p->bg[mpy], p->ed[mpy], w);
		//printf("%d %d\n",y, p->rt);
		//printf("%d %d\n", p->mp[y], p->mp[p->rt]);
		//for(int i = 0; i <p->n; i++) printf("%d ", p->blg[i]);
		//printf("?\n");
		//printf("%d\n",p->blg[mpy]);
		add(p->s[p->blg[mpy]], y, fa, w);
	}
}
pair<LL, int> query(Dnode * p, int x) {
	LL mpx = p->mp[x];
	//printf("%d %d %lld\n", p->rt, p->n, p->tag);
	//if(p->mp.count(6)) printf("%lld\n", p->sgt.getmax(1, 1, p->sgt.n, p->bg[p->mp[6]], p->bg[p->mp[6]]).fi);
	if(p->sgt.n == 0) {
		return p->a[0]; //max(p->a[mpx], p->a[mpx ^ 1] + p->len) + p->tag;
	}
	LL depx = p->dep[mpx];
	if(x == p->rt) {
		//printf("a1 %lld %d\n", p->sgt.a[1].fi, p->sgt.a[1].se);
		return p->sgt.a[1] + p->tag;
	}
	pair<LL, int> res{-infll, -1};
	LL blg = p->blg[mpx];
	LL blgrep = p->sid[blg];
	//printf("%d %d\n", p->bg[blgrep], p->ed[blgrep]);
	res = max(p->sgt.getmax(1, 1, p->sgt.n, 1, p->bg[blgrep] - 1), p->sgt.getmax(1, 1, p->sgt.n, p->ed[blgrep] + 1, p->sgt.n));
	//printf("res %lld %d\n", res.fi, p->tag);
	res = res + depx;
	//printf("res %lld %d\n", res.fi, p->tag);
	res = max(res, query(p->s[blg], x));
	//printf("res %lld %d\n", res.fi, p->tag);
	return res + p->tag;
}
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	n = 200000;
	q = 200000;


	for(int i = 1; i <= n; i++) {
		//	cout << i << endl;
		//scanf("%lld", &a[i]);
		a[i] = i;
	}
	for(int i = 1; i < n; i++) {
		//scanf("%d%lld", &p[i + 1], &w[i + 1]);
		p[i + 1] = gene() % i + 1;
		w[i + 1] = i;
		e[p[i + 1]].pb({i + 1, w[i + 1]});
		e[i + 1].pb({p[i + 1], w[i + 1]});
	}
	Dnode * rt = dvcq(1);
	//cout << dn_num << endl;
	//exit(0);
	//printf("dvcq over\n");
	for(int i = 1; i <= q; i++) {
		LL x, y, w;
		//scanf("%lld%lld%lld", &x, &y, &w);
		x = gene() % n + 1;
		y = gene() % n + 1;
		w = i;
		add(rt, y, p[y], -w);
		pair<LL, int> res = query(rt, x);
		printf("%d %lld\n", res.se * -1, res.fi);
	}
}