#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
#define MIN (1e-10)
#define equal(a,b) (abs((a)-(b))<MIN)
#define v2 ten
#define chokusen senbun
#define tenten senbun
#define takaku vec<ten>
#define kosu(b,e,v) (upb(b,e,v)-lob(b,e,v))
#define aru(b,e,v) (find(b,e,v)!=e)
using namespace std;
void solve();

struct pea {
	ll f, s;
	bool operator<(const pea &p)const {
		return f != p.f ? f < p.f : s < p.s;
	};
};
struct tri {
	ll f, s, t;
	bool operator<(const tri &p)const {
		if (f != p.f)return f < p.f;
		if (s != p.s)return s < p.s;
		return t < p.t;
	};
};
class ten {
public:
	ld x, y;

	ten operator+(ten p) { return { x + p.x,y + p.y }; }
	ten operator-(ten p) { return { x - p.x,y - p.y }; }
	ten operator*(ld k) { return { k*x,k*y }; }
	ten operator/(ld k) { return { x / k,y / k }; }

	ld abs() { return sqrt(abs2()); }
	ld abs2() { return x * x + y * y; };

	bool operator<(const ten &p)const { return x != p.x ? x < p.x : y < p.y; };
	bool operator==(const ten &p)const {
		return (-MIN < x - p.x) && (x - p.x < MIN) && (-MIN < y - p.y) && (y - p.y < MIN);
	};

	ld naiseki(v2 b) { return x*b.x + y*b.y; }
	ld gaiseki(v2 b) { return x*b.y - y*b.x; }
};
struct senbun { ten p1, p2; };
struct en { ten o; ld r; };

//互いに素な集合
class ufset {
public:
	vll rank, p;
	ufset(ll n) {
		rank.resize(n, 0);
		p.resize(n, 0);
		rep(i, 0, n)make(i);
	}
	void make(ll i) {
		p[i] = i;
		rank[i] = 0;
	}
	bool same(ll i, ll j) { return find(i) == find(j); }
	void unite(ll i, ll j) { link(find(i), find(j)); }
	void link(ll i, ll j) {
		if (rank[i] > rank[j])p[j] = i;
		else {
			p[i] = j;
			if (rank[i] == rank[j])rank[j]++;
		}
	}
	ll find(ll i) {
		if (p[i] != i)p[i] = find(p[i]);
		return p[i];
	}
};

//セグメント木(RMQ)
class seg {
private:
	ll n, m, kanzen;
	vec<tri> node;
public:
	seg(ll k, ll value = 2147483647) {
		n = k;
		m = 2 * n - 1;
		node.resize(m);

		kanzen = 2;
		k = m - n;
		while (k > 0) {
			kanzen *= 2;
			k = (k - 1) / 2;
		}
		kanzen--;

		rep(i, kanzen, m)node[i] = { value,i - kanzen,i - kanzen + 1 };
		rep(i, m - n, kanzen)node[i] = { value,i - kanzen + n,i - kanzen + n + 1 };
		rrep(i, m - n - 1, 0)node[i] = { value,node[2 * i + 1].s,node[2 * i + 2].t };
	}
	seg(vll values) {
		n = values.size();
		m = 2 * n - 1;
		node.resize(m);

		kanzen = 2;
		ll k = m - n;
		while (k > 0) {
			kanzen *= 2;
			k = (k - 1) / 2;
		}
		kanzen--;

		rep(i, kanzen, m)node[i] = { values[i - kanzen],i - kanzen,i - kanzen + 1 };
		rep(i, m - n, kanzen)node[i] = { values[i - kanzen + n],i - kanzen + n,i - kanzen + n + 1 };
		rrep(i, m - n - 1, 0)node[i] = { min(node[2 * i + 1].f, node[2 * i + 2].f),node[2 * i + 1].s,node[2 * i + 2].t };
	}

	ll const &operator[](ll i)const {
		if (i < m - kanzen)return node[kanzen + i].f;
		return node[i + kanzen - n].f;
	}

	void update(ll i, ll x) {
		ll k;
		if (i < m - kanzen)k = kanzen + i;
		else k = i + kanzen - n;

		node[k].f = x;
		while (k > 0) {
			x = min(x, node[(k % 2 == 0 ? k - 1 : k + 1)].f);
			k = (k - 1) / 2;
			node[k].f = x;
		}
	}

	//区間[a,b)
	ll getmin(ll a, ll b, ll k = 0) {
		if (a <= node[k].s && node[k].t <= b)return node[k].f;
		if (node[k].t <= a || b <= node[k].s)return 2147483647;

		ll vl = getmin(a, b, k * 2 + 1);
		ll vr = getmin(a, b, k * 2 + 2);
		return min(vl, vr);
	}
};

//nCk(mod p)
class nck {
public:
	ll NUM, p;
	vll fac, finv, inv;
	nck(ll maxn, ll mod = MOD) {
		NUM = maxn + 1;
		p = mod;
		fac.resize(NUM);
		finv.resize(NUM);
		inv.resize(NUM);
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		rep(i, 2, NUM) {
			fac[i] = fac[i - 1] * i%p;
			inv[i] = p - inv[p%i] * (p / i) % p;
			finv[i] = finv[i - 1] * inv[i] % p;
		}
	}
	ll c(ll n, ll k) { return fac[n] * (finv[k] * finv[n - k] % p) % p; }
};

//最大公約数
ll gcd(ll n, ll m) {
	ll k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return m;
}
ll gcd(vector<ll> a) {
	rep(i, 1, a.size()) {
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
	}
	return a.back();
}

//最小公倍数
ll lcm(ll n, ll m) {
	ll t = n * m, k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return t / m;
}
ll lcm(vector<ll> a) {
	ll n;
	rep(i, 1, a.size()) {
		n = a[i - 1] * a[i];
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
		n /= a[i];
		a[i] = n;
	}
	return n;
}

//a^b(mod p)
ll pow2(ll a, ll b, ll p = MOD) {
	if (b == -1)return pow2(a, p - 2);
	ll res = 1;
	if (b > 0) {
		res = pow2(a, b / 2);
		if (b % 2 == 0)res = res * res%p;
		else res = res * res%p*a%p;
	}
	return res;
}

//トポロジカルソート
void tsort(const vec<vll> &c, vll &a) {
	ll n = c.size();
	vll p(n, 0);
	rep(i, 0, n)rep(j, 0, c[i].size())p[c[i][j]]++;
	rep(i, 0, n)if (p[i] == 0) {
		deque<ll> d; d.pub(i);
		while (!d.empty()) {
			ll j = d.front(); d.pof();
			a.pub(j);
			rep(k, 0, c[j].size()) {
				ll l = c[j][k];
				p[l]--;
				if (p[l] == 0) {
					p[l] = -1;
					d.pub(l);
				}
			}
		}
	}
}

//深さ優先探索
vec<bool> seen;
void dfs(const vec<vll> &c, ll i = 0) {
	seen[i] = true;
	rep(j, 0, c[i].size()) {
		if (!seen[c[i][j]])dfs(c, c[i][j]);
	}
}

//最小全域木
ll kruskal(ll v, vec<tri> &e) {
	ll sum = 0;
	sort(ALL(e));
	ufset s(v);
	rep(i, 0, e.size()) {
		if (!s.same(e[i].s, e[i].t)) {
			s.unite(e[i].s, e[i].t);
			sum += e[i].f;
		}
	}
	return sum;
}

//単一始点最短経路
void dijkstra(const vec<vec<pea>> &c, ll v, vll &d) {
	d[v] = 0;
	ll n = c.size();
	ll count = 1;
	vec<bool> seen(n, false);
	seen[v] = true;
	yuque<pea> hen;
	rep(i, 0, c[v].size())hen.push({ -c[v][i].f,c[v][i].s });
	while (count != n) {
		if (hen.empty())break;
		pea k = hen.top(); hen.pop();
		while (seen[k.s]) {
			if (hen.empty()) {
				count = -1;
				break;
			}
			k = hen.top();
			hen.pop();
		}
		if (count == -1)break;
		d[k.s] = -k.f;
		count++;
		seen[k.s] = true;
		rep(i, 0, c[k.s].size())hen.push({ k.f - c[k.s][i].f,c[k.s][i].s });
	}
}

//全点対間最短経路
bool floyd(vec<vll> &d) {
	ll n = d.size();
	rep(i, 0, n)d[i][i] = 0;
	rep(k, 0, n) {
		rep(i, 0, n) {
			if (d[i][k] != MOD) {
				rep(j, 0, n) {
					if (d[k][j] != MOD) {
						d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
					}
				}
			}
		}
	}
	bool b = true;
	rep(i, 0, n)if (d[i][i] < 0)b = false;
	return b;
}

//計算幾何学
v2 beku(ld r,ld t){
	return { r*cos(t),r*sin(t) };
}
ld kakudo(v2 a) {
	return atan2(a.y, a.x);
}
ten shaei(ten p, chokusen l) {
	v2 a = l.p2 - l.p1;
	return l.p1 + a * a.naiseki(p - l.p1) / a.abs2();
}
ten hansha(ten p, chokusen l) {
	return shaei(p, l) * 2 - p;
}
ld tenchoku(ten p, chokusen l) {
	v2 a = l.p2 - l.p1;
	return abs(a.gaiseki(p - l.p1)) / a.abs();
}
ld tensen(ten p, senbun s) {
	if ((p - s.p1).naiseki(s.p2 - s.p1) < 0)return (p - s.p1).abs();
	if ((p - s.p2).naiseki(s.p1 - s.p2) < 0)return (p - s.p2).abs();
	return tenchoku(p, s);
}
ll ccw(ten p0, ten p1, ten p2) {
	v2 a = p1 - p0, b = p2 - p0;
	if (a.gaiseki(b) > MIN)return -1;//012反時計回り
	if (a.gaiseki(b) < -MIN)return 1;//012時計回り
	if (a.naiseki(b) < -MIN)return -2;//102
	if (a.abs2() < b.abs2())return 2;//012
	return 0;//021
}
bool majiwaru(senbun s, senbun t) { 
	return ccw(s.p1, s.p2, t.p1)*ccw(s.p1, s.p2, t.p2) <= 0 
		&& ccw(t.p1, t.p2, s.p1)*ccw(t.p1, t.p2, s.p2) <= 0; 
}
ld sensen(senbun s, senbun t) {
	if (majiwaru(s, t))return 0;
	return min({ tensen(s.p1,t),tensen(s.p2,t),tensen(t.p1,s),tensen(t.p2,s) });
}
ten koten(senbun s, senbun t) {
	v2 a = t.p2 - t.p1;
	ld d1 = abs(a.gaiseki(s.p1 - t.p1));
	ld d2 = abs(a.gaiseki(s.p2 - t.p1));
	return s.p1 + (s.p2 - s.p1)*d1 / (d1 + d2);
}
tenten koten(en c, chokusen l) {
	ten h = shaei(c.o, l);
	ld k = sqrt(c.r*c.r - (h - c.o).abs2());
	v2 a = (l.p1 - l.p2) / (l.p1 - l.p2).abs();
	return { h + a * k,h - a * k };
}
tenten koten(en c1, en c2) {
	ld d = (c2.o - c1.o).abs();
	ld s = acos((c1.r*c1.r + d * d - c2.r*c2.r) / (2 * c1.r*d));
	ld t = kakudo(c2.o - c1.o);
	return { c1.o + beku(c1.r,t + s),c1.o + beku(c1.r,t - s) };
}
ll uchi(ten p, takaku &g) {
	//2:IN,1:ON,0:OUT
	ll n = g.size();
	v2 a, b;
	bool x = false;
	rep(i, 0, n) {
		a = g[i] - p; b = g[(i + 1) % n] - p;
		if (abs(a.gaiseki(b)) < MIN&&a.naiseki(b) < MIN)return 1;
		if (a.y > b.y)swap(a, b);
		if (a.y < MIN&&MIN<b.y&&a.gaiseki(b)>MIN)x = !x;
	}
	return x ? 2 : 0;
}

//凸包
takaku andrew(takaku g) {
	takaku u, b;
	if (g.size() < 3)return g;
	sort(ALL(g));
	u.pub(g[0]); u.pub(g[1]);
	b.pub(g.back()); b.pub(g[g.size() - 2]);
	rep(i, 2, g.size()) {
		rrep(j, u.size(), 2) {
			if (ccw(u[j - 2], u[j - 1], g[i]) == 1)break;
			u.pob();
		}
		u.pub(g[i]);
	}
	rrep(i, g.size() - 3, 0) {
		rrep(j, b.size(), 2) {
			if (ccw(b[j - 2], b[j - 1], g[i]) == 1)break;
			b.pob();
		}
		b.pub(g[i]);
	}
	rep(i, 1, b.size() - 1)u.pub(b[i]);
	return u;
}

//線分交差問題
ll kotensu(vec<senbun> s) {
	ll n = s.size();
	struct endp {
		ten p; ll id, kind;//kind => 0:BOTTOM,1:LEFT,2:RIGHT,3:TOP
		bool operator<(const endp &e)const {
			return p.y != e.p.y ? p.y < e.p.y : kind < e.kind;
		};
	};
	
	vec<endp> ep(2 * n);
	rep(i, 0, n) {
		if (equal(s[i].p1.y, s[i].p2.y)) {
			if (s[i].p1.x > s[i].p2.x)swap(s[i].p1, s[i].p2);
			ep[2 * i] = { s[i].p1,i,1 };
			ep[2 * i + 1] = { s[i].p2,i,2 };
		}
		else {
			if (s[i].p1.y > s[i].p2.y)swap(s[i].p1, s[i].p2);
			ep[2 * i] = { s[i].p1,i,0 };
			ep[2 * i + 1] = { s[i].p2,i,3 };
		}
	}

	sort(ALL(ep));

	set<ll> bt;
	ll cnt = 0;
	rep(i, 0, 2 * n) {
		if (ep[i].kind == 3)bt.erase(ep[i].p.x);
		else if (ep[i].kind == 0)bt.insert(ep[i].p.x);
		else if (ep[i].kind == 1)cnt += distance(bt.lob(s[ep[i].id].p1.x), bt.upb(s[ep[i].id].p2.x));
	}
	return cnt;
}

//0-1 ナップザック問題
ll maxvalue(ll W, const vll &v, const vll &w, vll &select) {
	ll n = v.size();

	vec<vll> dp(n + 1, vll(W + 1, 0));
	vec<vec<bool>> tuika(n + 1, vec<bool>(W + 1, false));

	rep(i, 1, n + 1) {
		rep(j, 1, W + 1) {
			if (j - w[i - 1] >= 0 && dp[i - 1][j - w[i - 1]] + v[i - 1] > dp[i - 1][j]) {
				dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1];
				tuika[i][j] = true;
			}
			else dp[i][j] = dp[i - 1][j];
		}
	}

	ll ww = W; select.clear();
	rrep(i, n, 1) {
		if (tuika[i][ww]) {
			select.pub(i - 1);
			ww -= w[i - 1];
		}
	}
	reverse(ALL(select));

	return dp[n][W];
}

//二分探索
bool isok(ll key) {
	return false;
}
ll minkey(ll lkey, ll rkey) {
	//[lkey,rkey)
	while (lkey < rkey) {
		ll mkey = (lkey + rkey) / 2;
		if (isok(mkey))rkey = mkey;
		else lkey = mkey + 1;
	}
	return lkey;
}

//最長増加部分列
ll lis(const vll &a) {
	ll n = a.size();

	vll l; l.pub(a[0]);

	rep(i, 1, n) {
		if (l.back() < a[i])l.pub(a[i]);
		else *lob(ALL(l), a[i]) = a[i];
	}
	return l.size();
}

//最大正方形
ll seimen(const vec<vll> &g) {
	ll h = g.size(), w = g[0].size();

	vec<vll> dp(h, vll(w, 1));

	bool b = false;
	rep(i, 0, h)if (g[i][0] == 1)dp[i][0] = 0; else b = true;
	rep(i, 1, w)if (g[0][i] == 1)dp[0][i] = 0; else b = true;

	ll maxhen = (b ? 1 : 0);
	rep(i, 1, h) {
		rep(j, 1, w) {
			if (g[i][j] == 1)dp[i][j] = 0;
			else {
				dp[i][j] = min({ dp[i][j - 1],dp[i - 1][j - 1],dp[i - 1][j] }) + 1;
				maxhen = max(maxhen, dp[i][j]);
			}
		}
	}
	return maxhen * maxhen;
}

//最大長方形
ll chomen(const vec<vll> &g) {
	ll h = g.size(), w = g[0].size();

	ll maxmen = 0;
	vec<vll> dp(h, vll(w));

	rep(i, 0, w)dp[0][i] = (g[0][i] == 1 ? 0 : 1);
	rep(i, 1, h)rep(j, 0, w)dp[i][j] = (g[i][j] == 1 ? 0 : dp[i - 1][j] + 1);

	rep(i, 0, h) {

		vec<pea> a;
		rep(j, 0, w) {
			if (a.empty() || a.back().f < dp[i][j])a.pub({ dp[i][j],j });

			else if (a.back().f > dp[i][j]) {
				ll k;
				while (!a.empty() && a.back().f >= dp[i][j]) {
					maxmen = max(maxmen, a.back().f*(j - a.back().s));
					k = a.back().s;
					a.pob();
				}
				a.pub({ dp[i][j],k });
			}
		}

		while (!a.empty()) {
			maxmen = max(maxmen, a.back().f*(w - a.back().s));
			a.pob();
		}
	}

	return maxmen;
}

//素数判定
bool sosu(ll n) {
	if (n == 2)return true;
	if (n < 2 || n % 2 == 0)return false;
	for (ll i = 3; i*i <= n; i += 2)if (n%i == 0)return false;
	return true;
}
class eratos {
public:
	vec<bool> sosu;
	eratos(ll maxn) {
		sosu.resize(maxn + 1, true);
		sosu[0] = sosu[1] = false;
		for (ll i = 2; i*i <= maxn; i++) {
			if (sosu[i]) {
				ll j = i + i;
				while (j <= maxn) {
					sosu[j] = false;
					j += i;
				}
			}
		}
	}
};

//バックトラック(8クイーン問題)
bool board[8][8],retu[8],gyo[8],lurb[15],rulb[15];
void recursive(ll i) {
	if (i == 8) {
		rep(h, 0, 8) {
			rep(w, 0, 8) {
				if (board[h][w])cout << 'Q';
				else cout << '.';
			}
			cout << kai;
		}
		return;
	}

	if (gyo[i]) {
		recursive(i + 1);
		return;
	}

	rep(j, 0, 8) {
		if (!retu[j] && !lurb[i - j + 7] && !rulb[i + j]) {
			retu[j] = gyo[i] = lurb[i - j + 7] = rulb[i + j] = true;
			board[i][j] = true;

			recursive(i + 1);

			retu[j] = gyo[i] = lurb[i - j + 7] = rulb[i + j] = false;
			board[i][j] = false;
		}
	}
}

//幅優先探索(8パズル)
ll bfs(vll hajime) {
	struct pazzle { vll id; ll depth; };

	vll goal = { 1,2,3,4,5,6,7,8,0 };

	map<vll, bool> hantei;

	deque<pazzle> p;
	p.pub({ hajime,0 });
	while (!p.empty()) {
		if (p[0].id == goal)return p[0].depth;

		ll pos = find(ALL(p[0].id), 0) - p[0].id.begin();
		if (pos % 3 != 2) {
			swap(p[0].id[pos], p[0].id[pos + 1]);
			if (!hantei[p[0].id]) {
				p.pub({ p[0].id,p[0].depth + 1 });
				hantei[p[0].id] = true;
			}
			swap(p[0].id[pos], p[0].id[pos + 1]);
		}
		if (pos % 3 != 0) {
			swap(p[0].id[pos], p[0].id[pos - 1]);
			if (!hantei[p[0].id]) {
				p.pub({ p[0].id,p[0].depth + 1 });
				hantei[p[0].id] = true;
			}
			swap(p[0].id[pos], p[0].id[pos - 1]);
		}
		if (pos >= 3) {
			swap(p[0].id[pos], p[0].id[pos - 3]);
			if (!hantei[p[0].id]) {
				p.pub({ p[0].id,p[0].depth + 1 });
				hantei[p[0].id] = true;
			}
			swap(p[0].id[pos], p[0].id[pos - 3]);
		}
		if (pos <= 5) {
			swap(p[0].id[pos], p[0].id[pos + 3]);
			if (!hantei[p[0].id]) {
				p.pub({ p[0].id,p[0].depth + 1 });
				hantei[p[0].id] = true;
			}
			swap(p[0].id[pos], p[0].id[pos + 3]);
		}

		p.pof();
	}
}

//反復深化IDA*(15パズル)
ll manhattan[16][16];
ll dfs(vll &state,ll depth,ll limit,ll prestep) {
	ll summ = 0;
	rep(i, 0, 16)if (state[i] != 0)summ += manhattan[state[i] - 1][i]; else summ += manhattan[15][i];
	if (summ == 0)return depth;
	if (depth + summ > limit)return -1;

	ll cnt = 46;
	ll pos = find(ALL(state), 0) - state.begin();
	if (pos % 4 != 3 && prestep != 2) {
		swap(state[pos], state[pos + 1]);
		ll ret = dfs(state, depth + 1, limit, 1);
		if (ret != -1 && ret < cnt)cnt = ret;
		swap(state[pos], state[pos + 1]);
	}
	if (pos % 4 != 0 && prestep != 1) {
		swap(state[pos], state[pos - 1]);
		ll ret = dfs(state, depth + 1, limit, 2);
		if (ret != -1 && ret < cnt)cnt = ret;
		swap(state[pos], state[pos - 1]);
	}
	if (pos > 3 && prestep != 4) {
		swap(state[pos], state[pos - 4]);
		ll ret = dfs(state, depth + 1, limit, 3);
		if (ret != -1 && ret < cnt)cnt = ret;
		swap(state[pos], state[pos - 4]);
	}
	if (pos < 12 && prestep != 3) {
		swap(state[pos], state[pos + 4]);
		ll ret = dfs(state, depth + 1, limit, 4);
		if (ret != -1 && ret < cnt)cnt = ret;
		swap(state[pos], state[pos + 4]);
	}

	if (cnt == 46)return -1;
	else return cnt;
}

//bit全探索(n!探索=>bit DP)
bool zt01(vll a, ll m) {
	ll n = a.size(), j = 1, k = 0, l = 0;
	vll dp(1 << n); dp[0] = 0;
	//dp不可時:rep(i,0,n)if(bit & (1<<i))
	rep(i, 1, 1 << n) {
		k++;
		dp[i] = dp[i - j] + a[l];
		if (k == j) { j *= 2; k = 0; l++; }
		if (dp[i] == m)return true;
	}
	return false;
}

//nCk全探索(k≠0)
ll nec(ll bit) {
	//for(ll bit=(1<<k)-1;bit<(1<<n);bit=nec(bit))
	ll x = bit & -bit, y = bit + x;
	return (((bit & ~y) / x) >> 1) | y;
}

//乱数生成[0,4294967295]
ll ransu() {
	static unsigned int TX = 123456789, TY = 362436069, TZ = 521288629, TW = 88675123;
	unsigned int tt = (TX ^ (TX << 11));
	TX = TY; TY = TZ; TZ = TW;
	return (TW = (TW ^ (TW >> 19)) ^ (tt ^ (tt >> 8)));
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed;
	solve();
}
void solve() {
	ll n, q; cin >> n >> q;
	seg a(n);
	rep(i, 0, q) {
		ll c, x, y;
		cin >> c >> x >> y;
		if (c == 0) {
			a.update(x, y);
		}
		else {
			cout << a.getmin(x, y + 1) << kai;
		}
	}
}


Measured memory_bytes: 7636