#include <cstdio>int f[500010] , n;void add(int x , int a){	int i;	for(i = x ; i <= n ; i += i & -i) f[i] += a;}int query(int x){	int i , ans = 0;	for(i = x ; i ; i -= i & -i) ans += f[i];	return ans;}int main(){	int m , i , opt , x , y;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , add(i , x);	for(i = 1 ; i <= m ; i ++ )	{		scanf("%d%d%d" , &opt , &x , &y);		if(opt == 1) add(x , y);		else printf("%d\n" , query(y) - query(x - 1));	}	return 0;}

#include <cstdio>typedef long long ll;int n;struct data{	ll f[100010];	void add(int x , ll a)	{		int i;		for(i = x ; i <= n ; i += i & -i) f[i] += a;	}	ll query(int x)	{		int i;		ll ans = 0;		for(i = x ; i ; i -= i & -i) ans += f[i];		return ans;	}}A , B;void modify(int p , ll a){	A.add(p , a) , B.add(p , a * p);}ll solve(int p){	return (p + 1) * A.query(p) - B.query(p);}int main(){	int m , i , opt , x , y;	ll z;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &z) , modify(i , z) , modify(i + 1 , -z);	for(i = 1 ; i <= m ; i ++ )	{		scanf("%d%d%d" , &opt , &x , &y);		if(opt == 1) scanf("%lld" , &z) , modify(x , z) , modify(y + 1 , -z);		else printf("%lld\n" , solve(y) - solve(x - 1));	}	return 0;}

#include <cstdio>#include <algorithm>#define N 400010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long long ll;ll p , sum[N] , mul[N] , add[N];void pushup(int x){	sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % p;}void pushdown(int l , int r , int x){	int ls = x << 1 , rs = x << 1 | 1 , mid = (l + r) >> 1;	if(mul[x] != 1)	{		sum[ls] = sum[ls] * mul[x] % p , mul[ls] = mul[ls] * mul[x] % p , add[ls] = add[ls] * mul[x] % p;		sum[rs] = sum[rs] * mul[x] % p , mul[rs] = mul[rs] * mul[x] % p , add[rs] = add[rs] * mul[x] % p;		mul[x] = 1;	}	if(add[x])	{		sum[ls] = (sum[ls] + add[x] * (mid - l + 1)) % p , add[ls] = (add[ls] + add[x]) % p;		sum[rs] = (sum[rs] + add[x] * (r - mid)) % p , add[rs] = (add[rs] + add[x]) % p;		add[x] = 0;	}}void build(int l , int r , int x){	mul[x] = 1 , add[x] = 0;	if(l == r)	{		scanf("%lld" , &sum[x]);		return;	}	int mid = (l + r) >> 1;	build(lson) , build(rson);	pushup(x);}void updatemul(int b , int e , ll m , int l , int r , int x){	if(b <= l && r <= e)	{		sum[x] = sum[x] * m % p , mul[x] = mul[x] * m % p , add[x] = add[x] * m % p;		return;	}	pushdown(l , r , x);	int mid = (l + r) >> 1;	if(b <= mid) updatemul(b , e , m , lson);	if(e > mid) updatemul(b , e , m , rson);	pushup(x);}void updateadd(int b , int e , ll a , int l , int r , int x){	if(b <= l && r <= e)	{		sum[x] = (sum[x] + a * (r - l + 1)) % p , add[x] = (add[x] + a) % p;		return;	}	pushdown(l , r , x);	int mid = (l + r) >> 1;	if(b <= mid) updateadd(b , e , a , lson);	if(e > mid) updateadd(b , e , a , rson);	pushup(x);}ll query(int b , int e , int l , int r , int x){	if(b <= l && r <= e) return sum[x];	pushdown(l , r , x);	int mid = (l + r) >> 1;	ll ans = 0;	if(b <= mid) ans += query(b , e , lson);	if(e > mid) ans += query(b , e , rson);	return ans % p;}int main(){	int n , m , i , opt , x , y;	ll z;	scanf("%d%d%lld" , &n , &m , &p);	build(1 , n , 1);	for(i = 1 ; i <= m ; i ++ )	{		scanf("%d%d%d" , &opt , &x , &y);		if(opt == 1) scanf("%lld" , &z) , updatemul(x , y , z , 1 , n , 1);		else if(opt == 2) scanf("%lld" , &z) , updateadd(x , y , z , 1 , n , 1);		else printf("%lld\n" , query(x , y , 1 , n , 1));	}	return 0;}

#include <cstdio>#include <cstdlib>#define N 100010int l[N] , r[N] , w[N] , si[N] , cnt[N] , rnd[N] , tot , root , tmp;void zig(int &k){	int t = l[k];	l[k] = r[t] , r[t] = k , si[t] = si[k] , si[k] = si[l[k]] + si[r[k]] + cnt[k] , k = t;}void zag(int &k){	int t = r[k];	r[k] = l[t] , l[t] = k , si[t] = si[k] , si[k] = si[l[k]] + si[r[k]] + cnt[k] , k = t;}void insert(int &k , int x){	if(!k) k = ++tot , w[k] = x , si[k] = cnt[k] = 1 , rnd[k] = rand();	else if(x == w[k]) si[k] ++ , cnt[k] ++ ;	else if(x < w[k])	{		si[k] ++ , insert(l[k] , x);		if(rnd[l[k]] < rnd[k]) zig(k);	}	else	{		si[k] ++ , insert(r[k] , x);		if(rnd[r[k]] < rnd[k]) zag(k);	}}void del(int &k , int x){	if(x == w[k])	{		if(cnt[k] > 1) si[k] -- , cnt[k] -- ;		else if(!l[k] || !r[k]) k = l[k] + r[k];		else if(rnd[l[k]] < rnd[r[k]]) zig(k) , del(k , x);		else zag(k) , del(k , x);	}	else if(x < w[k]) si[k] -- , del(l[k] , x);	else si[k] -- , del(r[k] , x);}int getrank(int k , int x){	if(x < w[k]) return getrank(l[k] , x);	else if(x > w[k]) return getrank(r[k] , x) + si[l[k]] + cnt[k];	else return si[l[k]] + 1; }int find(int k , int x){	if(x <= si[l[k]]) return find(l[k] , x);	else if(x > si[l[k]] + cnt[k]) return find(r[k] , x - si[l[k]] - cnt[k]);	else return w[k];}void pro(int k , int x){	if(!k) return;	else if(w[k] < x) tmp = w[k] , pro(r[k] , x);	else pro(l[k] , x);}void sub(int k , int x){	if(!k) return;	else if(w[k] > x) tmp = w[k] , sub(l[k] , x);	else sub(r[k] , x);}int main(){	int n , opt , x;	scanf("%d" , &n);	while(n -- )	{		scanf("%d%d" , &opt , &x);		switch(opt)		{			case 1: insert(root , x); break;			case 2: del(root , x); break;			case 3: printf("%d\n" , getrank(root , x)); break;			case 4: printf("%d\n" , find(root , x)); break;			case 5: pro(root , x); printf("%d\n" , tmp); break;			default: sub(root , x); printf("%d\n" , tmp); break;		}	}	return 0;}

#include <cstdio>#include <algorithm>#define N 100010using namespace std;int fa[N] , c[2][N] , si[N] , rev[N] , root;void rever(int x){	swap(c[0][x] , c[1][x]) , rev[x] ^= 1;}void pushup(int x){	si[x] = si[c[0][x]] + si[c[1][x]] + 1;}void pushdown(int x){	if(rev[x]) rever(c[0][x]) , rever(c[1][x]) , rev[x] = 0;}void build(int l , int r , int f){	if(l > r) return;	int mid = (l + r) >> 1;	build(l , mid - 1 , mid) , build(mid + 1 , r , mid);	fa[mid] = f , c[mid > f][f] = mid;	pushup(mid);}void rotate(int &k , int x){	int y = fa[x] , z = fa[y] , l = (c[1][y] == x) , r = l ^ 1;	if(y == k) k = x;	else c[c[1][z] == y][z] = x;	fa[x] = z , fa[y] = x , fa[c[r][x]] = y , c[l][y] = c[r][x] , c[r][x] = y;	pushup(y) , pushup(x);}void splay(int &k , int x){	while(x != k)	{		int y = fa[x] , z = fa[y];		if(y != k)		{			if((c[0][y] == x) ^ (c[0][z] == y)) rotate(k , x);			else rotate(k , y);		}		rotate(k , x);	}}int find(int k , int x){	pushdown(k);	if(x <= si[c[0][k]]) return find(c[0][k] , x);	else if(x > si[c[0][k]] + 1) return find(c[1][k] , x - si[c[0][k]] - 1);	else return k;}int split(int l , int r){	int a = find(root , l) , b = find(root , r + 2);	splay(root , a) , splay(c[1][root] , b);	return c[0][c[1][root]];}int main(){	int n , m , i , x , y;	scanf("%d%d" , &n , &m);	build(1 , n + 2 , 0) , root = (n + 3) >> 1;	while(m -- ) scanf("%d%d" , &x , &y) , rever(split(x , y));	for(i = 2 ; i <= n + 1 ; i ++ ) printf("%d " , find(root , i) - 1);	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;int w[N] , opt[N] , x[N] , y[N] , z[N] , v[N] , num , c , root[N] , ls[N * 105] , rs[N * 105] , si[N * 105] , tot , R[20] , L[20] , cr , cl;void update(int p , int a , int l , int r , int x , int &y){	y = ++tot , si[y] = si[x] + a;	if(l == r) return;	int mid = (l + r) >> 1;	if(p <= mid) rs[y] = rs[x] , update(p , a , l , mid , ls[x] , ls[y]);	else ls[y] = ls[x] , update(p , a , mid + 1 , r , rs[x] , rs[y]);}int getrank(int p , int l , int r){	if(l == r) return 1;	int mid = (l + r) >> 1 , i , sum = 0;	if(p <= mid)	{		for(i = 1 ; i <= cr ; i ++ ) R[i] = ls[R[i]];		for(i = 1 ; i <= cl ; i ++ ) L[i] = ls[L[i]];		return getrank(p , l , mid);	}	else	{		for(i = 1 ; i <= cr ; i ++ ) sum += si[ls[R[i]]] , R[i] = rs[R[i]];		for(i = 1 ; i <= cl ; i ++ ) sum -= si[ls[L[i]]] , L[i] = rs[L[i]];		return getrank(p , mid + 1 , r) + sum;	}}int find(int k , int l , int r){	if(l == r) return v[l];	int mid = (l + r) >> 1 , i , sum = 0;	for(i = 1 ; i <= cr ; i ++ ) sum += si[ls[R[i]]];	for(i = 1 ; i <= cl ; i ++ ) sum -= si[ls[L[i]]];	if(k <= sum)	{		for(i = 1 ; i <= cr ; i ++ ) R[i] = ls[R[i]];		for(i = 1 ; i <= cl ; i ++ ) L[i] = ls[L[i]];		return find(k , l , mid);	}	else	{		for(i = 1 ; i <= cr ; i ++ ) R[i] = rs[R[i]];		for(i = 1 ; i <= cl ; i ++ ) L[i] = rs[L[i]];		return find(k - sum , mid + 1 , r);	}}void init(int x , int y){	int i;	for(cr = 0 , i = y ; i ; i -= i & -i) R[++cr] = root[i];	for(cl = 0 , i = x - 1 ; i ; i -= i & -i ) L[++cl] = root[i];}int main(){	int n , m , i , j , t;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , v[++num] = w[i];	for(i = 1 ; i <= m ; i ++ )	{		scanf("%d%d" , &opt[i] , &x[i]);		if(opt[i] != 3) scanf("%d" , &y[i]);		scanf("%d" , &z[i]);		if(opt[i] != 2) v[++num] = z[i];	}	sort(v + 1 , v + num + 1) , v[0] = -1 << 30;	for(i = 1 ; i <= num ; i ++ ) if(v[i] != v[i - 1]) v[++c] = v[i];	for(i = 1 ; i <= n ; i ++ ) w[i] = lower_bound(v + 1 , v + c + 1 , w[i]) - v;	for(i = 1 ; i <= m ; i ++ )		if(opt[i] != 2)			z[i] = lower_bound(v + 1 , v + c + 1 , z[i]) - v;	for(i = 1 ; i <= n ; i ++ )		for(j = i ; j <= n ; j += j & -j)			update(w[i] , 1 , 1 , c , root[j] , root[j]);	for(i = 1 ; i <= m ; i ++ )	{		if(opt[i] != 3) init(x[i] , y[i]);		switch(opt[i])		{			case 1: printf("%d\n" , getrank(z[i] , 1 , c)); break;			case 2: printf("%d\n" , find(z[i] , 1 , c)); break;			case 3: for(j = x[i] ; j <= n ; j += j & -j) update(w[x[i]] , -1 , 1 , c , root[j] , root[j]) , update(z[i] , 1 , 1 , c , root[j] , root[j]); w[x[i]] = z[i]; break;			case 4: t = getrank(z[i] , 1 , c) , init(x[i] , y[i]) , printf("%d\n" , find(t - 1 , 1 , c)); break;			default: t = getrank(z[i] + 1 , 1 , c) , init(x[i] , y[i]) , printf("%d\n" , find(t , 1 , c));		}	}	return 0;}

#include <cstdio>#include <algorithm>#define N 200010#define lson l , mid , ls[x] , ls[y]#define rson mid + 1 , r , rs[x] , rs[y]using namespace std;typedef long long ll;struct data{    int x , l , r;    ll p;    data() {}    data(int x0 , int l0 , int r0 , ll p0) {x = x0 , l = l0 , r = r0 , p = p0;}}v[N << 2];int a[N] , lp[N] , rp[N] , sta[N] , top , cnt , root[N] , ls[N << 6] , rs[N << 6] , tot;ll sum[N << 6] , add[N << 6];bool cmp(data a , data b){    return a.x < b.x;}void pushup(int x){    sum[x] = sum[ls[x]] + sum[rs[x]];}void insert(int b , int e , ll a , int l , int r , int x , int &y){    y = ++tot , ls[y] = ls[x] , rs[y] = rs[x] , add[y] = add[x] , sum[y] = sum[x] + a * (e - b + 1);    if(b == l && r == e)    {        add[y] += a;        return;    }    int mid = (l + r) >> 1;    if(e <= mid) insert(b , e , a , lson);    else if(b > mid) insert(b , e , a , rson);    else insert(b , mid , a , lson) , insert(mid + 1 , e , a , rson);}ll query(int b , int e , int l , int r , int x , int y){    if(b <= l && r <= e) return sum[y] - sum[x];    int mid = (l + r) >> 1;    ll ans = (add[y] - add[x]) * (e - b + 1);    if(e <= mid) return ans + query(b , e , lson);    else if(b > mid) return ans + query(b , e , rson);    else return ans + query(b , mid , lson) + query(mid + 1 , e , rson);}int main(){    int n , m , i , j , x , y;    ll p1 , p2;    scanf("%d%d%lld%lld" , &n , &m , &p1 , &p2);    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);    a[0] = a[n + 1] = 1 << 30 , top = 1;    for(i = 1 ; i <= n ; i ++ )    {        while(a[sta[top]] < a[i]) top -- ;        lp[i] = sta[top] , sta[++top] = i;    }    top = 1 , sta[1] = n + 1;    for(i = n ; i >= 1 ; i -- )    {        while(a[sta[top]] < a[i]) top -- ;        rp[i] = sta[top] , sta[++top] = i;    }    for(i = 1 ; i <= n ; i ++ )    {        if(lp[i] != 0 && rp[i] != n + 1) v[++cnt] = data(lp[i] , rp[i] , rp[i] , p1);        if(i < n) v[++cnt] = data(i , i + 1 , i + 1 , p1);        if(lp[i] != 0 && rp[i] - i > 1) v[++cnt] = data(lp[i] , i + 1 , rp[i] - 1 , p2);        if(rp[i] != n + 1 && i - lp[i] > 1) v[++cnt] = data(rp[i] , lp[i] + 1 , i - 1 , p2);    }    sort(v + 1 , v + cnt + 1 , cmp);    for(i = j = 1 ; i <= n ; i ++ )    {        root[i] = root[i - 1];        while(j <= cnt && v[j].x == i)            insert(v[j].l , v[j].r , v[j].p , 1 , n , root[i] , root[i]) , j ++ ;    }    while(m -- )    {        scanf("%d%d" , &x , &y);        printf("%lld\n" , query(x , y , 1 , n , root[x - 1] , root[y]));    }    return 0;}

#include <cstdio>int f[4000010];int find(int x){	return x == f[x] ? x : f[x] = find(f[x]);}int main(){	int n , m , i , opt , x , y , ans = 0;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) f[i] = i;	for(i = 1 ; i <= m ; i ++ )	{		scanf("%d%d%d" , &opt , &x , &y);		if(opt) ans = (ans * 2 + (find(x) == find(y))) % 998244353;		else f[find(x)] = find(y);	}	printf("%d\n" , ans);	return 0;}

#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#define N 100010using namespace std;typedef long long ll;int a[N] , val[N] , cnt[N] , num[410][N];ll ans[410][410];int main(){    int n , m , si , i , j , k , x , y;    ll maxn;    scanf("%d%d" , &n , &m) , si = (int)sqrt(n);    for(i = 0 ; i < n ; i ++ ) scanf("%d" , &a[i]) , val[i] = a[i];    sort(val , val + n);    for(i = 0 ; i < n ; i ++ ) a[i] = lower_bound(val , val + n , a[i]) - val;    for(i = 0 ; i <= (n - 1) / si ; i ++ )    {        for(j = i * si ; j < (i + 1) * si && j < n ; j ++ ) cnt[a[j]] ++ ;        for(j = 0 ; j < n ; j ++ ) num[i][j] = cnt[j];    }    for(i = 0 ; i <= (n - 1) / si ; i ++ )    {        memset(cnt , 0 , sizeof(cnt)) , maxn = 0;        for(j = i ; j <= (n - 1) / si ; j ++ )        {            for(k = j * si ; k < (j + 1) * si && k < n ; k ++ ) cnt[a[k]] ++ , maxn = max(maxn , (ll)cnt[a[k]] * val[a[k]]);            ans[i][j] = maxn;        }    }    memset(cnt , 0 , sizeof(cnt));    while(m -- )    {        scanf("%d%d" , &x , &y) , x -- , y -- ;        if(y / si - x / si < 2)        {            maxn = 0;            for(i = x ; i <= y ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)cnt[a[i]] * val[a[i]]);            for(i = x ; i <= y ; i ++ ) cnt[a[i]] -- ;        }        else        {            maxn = ans[x / si + 1][y / si - 1];            for(i = x ; i < (x / si + 1) * si ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)(cnt[a[i]] + num[y / si - 1][a[i]] - num[x / si][a[i]]) * val[a[i]]);            for(i = y / si * si ; i <= y ; i ++ ) cnt[a[i]] ++ , maxn = max(maxn , (ll)(cnt[a[i]] + num[y / si - 1][a[i]] - num[x / si][a[i]]) * val[a[i]]);            for(i = x ; i < (x / si + 1) * si ; i ++ ) cnt[a[i]] -- ;            for(i = y / si * si ; i <= y ; i ++ ) cnt[a[i]] -- ;        }        printf("%lld\n" , maxn);    }    return 0;}

#include <queue>#include <cstdio>#include <cstring>#include <utility>#include <algorithm>#define N 50010#define squ(x) (x) * (x)#define rep for(int i = 0 ; i < m ; i ++ )using namespace std;typedef pair<int , int> pr;priority_queue<pr> q;struct data{	int p[5] , mx[5] , mn[5] , c[2];}a[N];int v[5] , d , root , m , ans , tmp[20];bool cmp(data a , data b){	rep	{		if(a.p[(d + i) % m] < b.p[(d + i) % m]) return 1;		if(a.p[(d + i) % m] > b.p[(d + i) % m]) return 0;	}	return 0;}void pushup(int k , int x){	rep a[k].mx[i] = max(a[k].mx[i] , a[x].mx[i]) , a[k].mn[i] = min(a[k].mn[i] , a[x].mn[i]);}int build(int l , int r , int now){	int mid = (l + r) >> 1;	d = now , nth_element(a + l , a + mid , a + r + 1 , cmp);	rep a[mid].mx[i] = a[mid].mn[i] = a[mid].p[i];	a[mid].c[0] = a[mid].c[1] = 0;	if(l < mid) a[mid].c[0] = build(l , mid - 1 , (now + 1) % m) , pushup(mid , a[mid].c[0]);	if(r > mid) a[mid].c[1] = build(mid + 1 , r , (now + 1) % m) , pushup(mid , a[mid].c[1]);	return mid;}int getdis(int k){	if(!k) return 0x7fffffff;	int ans = 0;	rep	{		if(v[i] < a[k].mn[i]) ans += squ(v[i] - a[k].mn[i]);		if(v[i] > a[k].mx[i]) ans += squ(v[i] - a[k].mx[i]);	}	return ans;}void query(int k){	int dn = 0 , dl = getdis(a[k].c[0]) , dr = getdis(a[k].c[1]);	rep dn += squ(v[i] - a[k].p[i]);	if(dn < q.top().first) q.pop() , q.push(pr(dn , k));	if(dl < dr)	{		if(dl < q.top().first) query(a[k].c[0]);		if(dr < q.top().first) query(a[k].c[1]);	}	else	{		if(dr < q.top().first) query(a[k].c[1]);		if(dl < q.top().first) query(a[k].c[0]);	}}int main(){	int n , k , i , j , t;	while(scanf("%d%d" , &n , &m) != EOF)	{		for(i = 1 ; i <= n ; i ++ )			for(j = 0 ; j < m ; j ++ )				scanf("%d" , &a[i].p[j]);		root = build(1 , n , 0);		scanf("%d" , &k);		while(k -- )		{			for(i = 0 ; i < m ; i ++ ) scanf("%d" , &v[i]);			scanf("%d" , &t);			for(i = 1 ; i <= t ; i ++ ) q.push(pr(0x7fffffff , 0));			query(root);			for(i = 1 ; i <= t ; i ++ ) tmp[i] = q.top().second , q.pop();			printf("the closest %d points are:\n" , t);			for(i = t ; i >= 1 ; i -- )			{				for(j = 0 ; j < m - 1 ; j ++ ) printf("%d " , a[tmp[i]].p[j]);				printf("%d\n" , a[tmp[i]].p[m - 1]);			}		}	}	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;struct data{	int x , y , t1 , t2;}a[N << 1];int n , fa[N << 2] , c[2][N << 2] , si[N << 2] , w[N << 2] , mp[N << 2] , rev[N << 2] , num[N] , sum , now;inline char nc(){	static char buf[100000] , *p1 , *p2;	return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}inline int read(){	int ret = 0; char ch = nc();	while(ch < ‘0‘ || ch > ‘9‘) ch = nc();	while(ch >= ‘0‘ && ch <= ‘9‘) ret = (ret << 3) + (ret << 1) + ch - 48 , ch = nc();	return ret;}bool cmp(data a , data b){	return a.t1 < b.t1;}void pushup(int x){	si[x] = si[c[0][x]] + si[c[1][x]] + 1;	mp[x] = x;	if(w[mp[c[0][x]]] < w[mp[x]]) mp[x] = mp[c[0][x]];	if(w[mp[c[1][x]]] < w[mp[x]]) mp[x] = mp[c[1][x]];}void pushdown(int x){	if(rev[x])	{		int l = c[0][x] , r = c[1][x];		swap(c[0][l] , c[1][l]) , swap(c[0][r] , c[1][r]);		rev[l] ^= 1 , rev[r] ^= 1 , rev[x] = 0;	}}bool isroot(int x){	return c[0][fa[x]] != x && c[1][fa[x]] != x;}void update(int x){	if(!isroot(x)) update(fa[x]);	pushdown(x);}void rotate(int x){	int y = fa[x] , z = fa[y] , l = (c[1][y] == x) , r = l ^ 1;	if(!isroot(y)) c[c[1][z] == y][z] = x;	fa[x] = z , fa[y] = x , fa[c[r][x]] = y , c[l][y] = c[r][x] , c[r][x] = y;	pushup(y) , pushup(x);}void splay(int x){	update(x);	while(!isroot(x))	{		int y = fa[x] , z = fa[y];		if(!isroot(y))		{			if((c[0][y] == x) ^ (c[0][z] == y)) rotate(x);			else rotate(y);		}		rotate(x);	}}void access(int x){	int t = 0;	while(x) splay(x) , c[1][x] = t , pushup(x) , t = x , x = fa[x];}int find(int x){	access(x) , splay(x);	while(c[0][x]) pushdown(x) , x = c[0][x];	return x;}void makeroot(int x){	access(x) , splay(x);	swap(c[0][x] , c[1][x]) , rev[x] ^= 1;}void link(int x , int y){	makeroot(x) , fa[x] = y;}void cut(int x , int y){	makeroot(x) , access(y) , splay(y) , fa[x] = c[0][y] = 0 , pushup(y);}void split(int x , int y){	makeroot(x) , access(y) , splay(y);}void add(int p){	int tx = a[p].x , ty = a[p].y , tmp , flag = 0;	if(tx == ty && a[p].t2 > now) num[a[p].t2] ++ , sum ++ ;	else	{		if(find(tx) != find(ty)) link(p + n , tx) , link(p + n , ty);		else		{			split(tx , ty);			if(!((si[ty] >> 1) & 1)) flag = 1;			if(w[mp[ty]] >= a[p].t2) tmp = p;			else tmp = mp[ty] - n , cut(tmp + n , a[tmp].x) , cut(tmp + n , a[tmp].y) , link(p + n , tx) , link(p + n , ty);			if(flag && a[tmp].t2 > now) num[a[tmp].t2] ++ , sum ++ ;		}	}}int main(){	int m , t , i , p = 1;	n = read() , m = read() , t = read();	for(i = 1 ; i <= m ; i ++ ) a[i].x = read() , a[i].y = read() , a[i].t1 = read() , a[i].t2 = read();	sort(a + 1 , a + m + 1 , cmp);	for(i = 1 ; i <= n + m ; i ++ ) si[i] = 1 , mp[i] = i;	for(i = 0 ; i <= n ; i ++ ) w[i] = 1 << 30;	for(i = 1 ; i <= m ; i ++ ) w[i + n] = a[i].t2;	for(i = 0 ; i < t ; i ++ )	{		now = i;		while(p <= m && a[p].t1 <= i) add(p ++ );		sum -= num[i];		if(sum) puts("No");		else puts("Yes");	}	return 0;}

#include <cstdio>#include <set>#define N 300010using namespace std;multiset<int> s;multiset<int>::iterator it;int w[N] , fa[N] , l[N] , r[N] , d[N] , add[N];char str[5];void pushdown(int x){    if(add[x]) w[l[x]] += add[x] , w[r[x]] += add[x] , add[l[x]] += add[x] , add[r[x]] += add[x] , add[x] = 0;}void update(int x){    if(fa[x]) update(fa[x]);    pushdown(x);}int find(int x){    return fa[x] ? find(fa[x]) : x;}int merge(int x , int y){    if(!x) return y;    if(!y) return x;    pushdown(x) , pushdown(y);    if(w[x] < w[y]) swap(x , y);    r[x] = merge(r[x] , y) , fa[r[x]] = x;    if(d[l[x]] < d[r[x]]) swap(l[x] , r[x]);    d[x] = d[r[x]] + 1;    return x;}int clear(int x){    int t = merge(l[x] , r[x]) , f = fa[x];    fa[x] = l[x] = r[x] = 0;    if(x == l[f]) l[f] = t;    else r[f] = t;    fa[t] = f;    return find(t);}void del(int x){    s.erase(s.find(x));}int main(){    int n , i , m , v = 0 , x , y , tx , ty;    scanf("%d" , &n);    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , s.insert(w[i]);    scanf("%d" , &m);    d[0] = -1;    while(m -- )    {        scanf("%s" , str);        if(str[0] == ‘U‘)        {            scanf("%d%d" , &x , &y) , tx = find(x) , ty = find(y);            if(tx != ty)            {                if(merge(tx , ty) == tx) del(w[ty]);                else del(w[tx]);            }        }        else if(str[0] == ‘A‘)        {            scanf("%d" , &x);            if(str[1] == ‘1‘) scanf("%d" , &y) , update(x) , del(w[find(x)]) , w[x] += y , s.insert(w[merge(x , clear(x))]);            else if(str[1] == ‘2‘) scanf("%d" , &y) , tx = find(x) , del(w[tx]) , w[tx] += y , s.insert(w[tx]) , add[tx] += y;            else v += x;        }        else        {            if(str[1] == ‘1‘) scanf("%d" , &x) , update(x) , printf("%d\n" , w[x] + v);            else if(str[1] == ‘2‘) scanf("%d" , &x) , tx = find(x) , printf("%d\n" , w[tx] + v);            else printf("%d\n" , *(--s.end()) + v);        }    }    return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;typedef long long ll;const ll mod = 998244353;int root[N << 2] , ls[N << 8] , rs[N << 8] , tot , n;ll sum[N << 8];ll cal(ll x , ll y){    return (x * y + (1 - x + mod) * (1 - y + mod)) % mod;}ll pow(ll x , ll y){    ll ans = 1;    while(y)    {        if(y & 1) ans = ans * x % mod;        x = x * x % mod , y >>= 1;    }    return ans;}void update(int b , int e , ll v , int l , int r , int &x){    if(!x) x = ++tot , sum[x] = 1;    if(b <= l && r <= e)    {        sum[x] = cal(sum[x] , v);        return;    }    int mid = (l + r) >> 1;    if(b <= mid) update(b , e , v , l , mid , ls[x]);    if(e > mid) update(b , e , v , mid + 1 , r , rs[x]);}ll query(int p , int l , int r , int x){    if(!x) return 1;    if(l == r) return sum[x];    int mid = (l + r) >> 1;    if(p <= mid) return cal(sum[x] , query(p , l , mid , ls[x]));    else return cal(sum[x] , query(p , mid + 1 , r , rs[x]));}void modify(int p , int q , ll v , int b , int e , int l , int r , int x){    if(p <= l && r <= q)    {        update(b , e , v , 1 , n , root[x]);        return;    }    int mid = (l + r) >> 1;    if(p <= mid) modify(p , q , v , b , e , l , mid , x << 1);    if(q > mid) modify(p , q , v , b , e , mid + 1 , r , x << 1 | 1);}ll solve(int p , int q , int l , int r , int x){    if(l == r) return query(q , 1 , n , root[x]);    int mid = (l + r) >> 1;    if(p <= mid) return cal(query(q , 1 , n , root[x]) , solve(p , q , l , mid , x << 1));    else return cal(query(q , 1 , n , root[x]) , solve(p , q , mid + 1 , r , x << 1 | 1));}int main(){    int m , opt , l , r;    ll p;    scanf("%d%d" , &n , &m);    while(m -- )    {        scanf("%d%d%d" , &opt , &l , &r);        if(opt == 1)        {            p = pow(r - l + 1 , mod - 2);            if(l > 1) modify(1 , l - 1 , (1 - p + mod) % mod , l , r , 0 , n , 1) , modify(0 , 0 , 0 , 1 , l - 1 , 0 , n , 1);            if(r < n) modify(l , r , (1 - p + mod) % mod , r + 1 , n , 0 , n , 1) , modify(0 , 0 , 0 , r + 1 , n , 0 , n , 1);            modify(l , r , (1 - (p << 1) % mod + mod) % mod , l , r , 0 , n , 1) , modify(0 , 0 , p , l , r , 0 , n , 1);        }        else printf("%lld\n" , solve(l - 1 , r , 0 , n , 1));    }    return 0;}

#include <cstdio>typedef long long ll;const ll mod = 998244353;ll phi(ll n){	ll i , ans = n;	for(i = 2 ; i * i <= n ; i ++ )	{		if(n % i == 0)		{			ans = ans / i * (i - 1);			while(n % i == 0) n /= i;		}	}	if(n != 1) ans = ans / n * (n - 1);	return ans % mod;}int main(){	ll n , m;	scanf("%lld%lld" , &n , &m);	printf("%lld\n" , phi(n) * phi(m) % mod * (n % mod) % mod * (m % mod) % mod);	return 0;}

#include <cstdio>#define mod 10007int fac[10010];int pow(int x , int y){    int ans = 1;    while(y)    {        if(y & 1) ans = ans * x % mod;        x = x * x % mod , y >>= 1;    }    return ans;}int cal(int n , int m){    if(n < m) return 0;    return fac[n] * pow(fac[m] , mod - 2) % mod * pow(fac[n - m] , mod - 2) % mod;}int lucas(int n , int m){    if(!m) return 1;    return cal(n % mod , m % mod) * lucas(n / mod , m / mod) % mod;}int main(){    int t , n , m , i;    scanf("%d" , &t);    fac[0] = 1;    for(i = 1 ; i < mod ; i ++ ) fac[i] = fac[i - 1] * i % mod;    while(t -- )    {        scanf("%d%d" , &n , &m);        printf("%d\n" , lucas(n , m));    }    return 0;}

#include <cstdio>typedef long long ll;ll ine[3000010];int main(){	ll n , p , i;	scanf("%lld%lld" , &n , &p);	ine[1] = 1 , puts("1");	for(i = 2 ; i <= n ; i ++ )		ine[i] = (p - p / i) * ine[p % i] % p , printf("%lld\n" , ine[i]);	return 0;}

#include <cstdio>#include <bitset>using namespace std;bitset<1010> a[2010];int n , m , ans;char str[1010];void gauss(){	int i , j;	for(i = 1 ; i <= n ; i ++ )	{		for(j = i ; j <= m && !a[j][i] ; j ++ );		if(j > m)		{			ans = 0;			return;		}		else ans = max(ans , j);		swap(a[i] , a[j]);		for(j = 1 ; j <= m ; j ++ )			if(j != i && a[j][i])				a[j] ^= a[i];	}}int main(){	int i , j , t;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= m ; i ++ )	{		scanf("%s" , str + 1);		for(j = 1 ; j <= n ; j ++ ) a[i][j] = str[j] - ‘0‘;		scanf("%d" , &t) , a[i][n + 1] = t;	}	gauss();	if(!ans)	{		printf("Cannot Determine\n");		return 0;	}	printf("%d\n" , ans);	for(i = 1 ; i <= n ; i ++ ) printf("%s\n" , a[i][n + 1] ? "?y7M#" : "Earth");	return 0;}

#include <cstdio>#include <algorithm>using namespace std;int a[100010];int main(){    int n , i , j , tot = 0 , ans = 0;    scanf("%d" , &n);    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);    for(i = 1 << 30 ; i ; i >>= 1)    {        for(j = ++tot ; j <= n ; j ++ )        {            if(a[j] & i)            {                swap(a[tot] , a[j]);                break;            }        }        if(j > n)        {            tot -- ;            continue;        }        for(j = 1 ; j <= n ; j ++ )            if(j != tot && a[j] & i)                a[j] ^= a[tot];    }    for(i = 1 ; i < tot ; i ++ ) ans ^= a[i];    printf("%d %d\n" , ans ^ a[tot] , ans);    return 0;}

#include <cstdio>#define N 510typedef long long ll;const ll mod = 1000000007;ll a[N][N] , b[N][N] , c[N][N];int main(){	int n , m , p , i , j , k;	scanf("%d%d%d" , &n , &p , &m);	for(i = 1 ; i <= n ; i ++ )		for(j = 1 ; j <= p ; j ++ )			scanf("%lld" , &a[i][j]);	for(i = 1 ; i <= p ; i ++ )		for(j = 1 ; j <= m ; j ++ )			scanf("%lld" , &b[i][j]);	for(i = 1 ; i <= n ; i ++ )		for(j = 1 ; j <= m ; j ++ )			for(k = 1 ; k <= p ; k ++ )				c[i][j] = ((c[i][j] + a[i][k] * b[k][j]) % mod + mod) % mod;	for(i = 1 ; i <= n ; i ++ )	{		for(j = 1 ; j <= m ; j ++ )			printf("%lld " , c[i][j]);		printf("\n");	}	return 0;}

#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>#define N 400010using namespace std;const double pi = acos(-1);struct data{	double x , y;	data() {}	data(double x0 , double y0) {x = x0 , y = y0;}	data operator+(data a) {return data(x + a.x , y + a.y);}	data operator-(data a) {return data(x - a.x , y - a.y);}	data operator*(data a) {return data(x * a.x - y * a.y , x * a.y + y * a.x);}}a[N] , b[N];void fft(data *a , int len , int flag){	int i , j , k;	for(i = k = 0 ; i < len ; i ++ )	{		if(i > k) swap(a[i] , a[k]);		for(j = len >> 1 ; (k ^= j) < j ; j >>= 1);	}	for(k = 2 ; k <= len ; k <<= 1)	{		data wn(cos(2 * pi * flag / k) , sin(2 * pi * flag / k));		for(i = 0 ; i < len ; i += k)		{			data w(1 , 0) , t;			for(j = i ; j < i + (k >> 1) ; j ++ , w = w * wn)				t = w * a[j + (k >> 1)] , a[j + (k >> 1)] = a[j] - t , a[j] = a[j] + t;		}	}}void work(data *a , data *b , int len){	int i;	fft(a , len , 1) , fft(b , len , 1);	for(i = 0 ; i < len ; i ++ ) a[i] = a[i] * b[i];	fft(a , len , -1);	for(i = 0 ; i < len ; i ++ ) a[i].x /= len;}int main(){	int n , m , i , len = 1;	scanf("%d%d" , &n , &m);	for(i = 0 ; i <= n ; i ++ ) scanf("%lf" , &a[i].x);	for(i = 0 ; i <= m ; i ++ ) scanf("%lf" , &b[i].x);	while(len <= n + m) len <<= 1;	work(a , b , len);	for(i = 0 ; i < n + m ; i ++ ) printf("%d " , (int)(a[i].x + 0.1));	printf("%d" , (int)(a[n + m].x + 0.1));	return 0;}

#include <queue>#include <cstdio>#include <cstring>#include <utility>#define N 2510#define M 12510using namespace std;typedef long long ll;typedef pair<ll , int> pr;priority_queue<pr> q;int head[N] , to[M] , next[M] , cnt;ll len[M] , dis[N];bool vis[N];void add(int x , int y , ll z){	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}int main(){	int n , m , s , t , i , x , y;	ll z;	scanf("%d%d%d%d" , &n , &m , &s , &t);	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%lld" , &x , &y , &z) , add(x , y , z) , add(y , x , z);	memset(dis , 0x3f , sizeof(dis));	dis[s] = 0 , q.push(pr(0 , s));	while(!q.empty())	{		x = q.top().second , q.pop();		if(vis[x]) continue;		vis[x] = 1;		for(i = head[x] ; i ; i = next[i])			if(dis[to[i]] > dis[x] + len[i])				dis[to[i]] = dis[x] + len[i] , q.push(pr(-dis[to[i]] , to[i]));	}	printf("%lld\n" , dis[t]);	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 310using namespace std;int n , log[N];struct data{    int v[N][N];    data()    {        memset(v , 0x3f , sizeof(v));    }    data operator*(const data a)const    {        data ans;        int i , j , k;        for(k = 1 ; k <= n ; k ++ )            for(i = 1 ; i <= n ; i ++ )                for(j = 1 ; j <= n ; j ++ )                    ans.v[i][j] = min(ans.v[i][j] , v[i][k] + a.v[k][j]);        return ans;    }}dis[10] , tmp;bool judge(data a){    int i;    for(i = 1 ; i <= n ; i ++ )        if(a.v[i][i] < 0)            return 1;    return 0;}int main(){    int m , x , y , z , i , sum = 0;    scanf("%d%d" , &n , &m);    for(i = 1 ; i <= n ; i ++ ) dis[0].v[i][i] = tmp.v[i][i] = 0;    for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;    while(m -- ) scanf("%d%d%d" , &x , &y , &z) , dis[0].v[x][y] = z;    for(i = 1 ; i <= log[n] ; i ++ ) dis[i] = dis[i - 1] * dis[i - 1];    for(i = log[n] ; ~i ; i -- )        if(!judge(tmp * dis[i]))            tmp = tmp * dis[i] , sum += (1 << i);    tmp = tmp * dis[0];    printf("%d\n" , judge(tmp) ? sum + 1 : 0);    return 0;}

#include <cstdio>#include <cstring>#include <queue>using namespace std;queue<pair<int , int> > q;int head[60] , to[2010] , len[2010] , next[2010] , cnt , dis[60][60] , inq[60][60];void add(int x , int y , int z){    to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}int main(){    int n , m , k , i , x , y , z , ans = 0x3f3f3f3f;    scanf("%d%d%d" , &n , &m , &k);    while(m -- ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z) , add(y , x , z);    memset(dis , 0x3f , sizeof(dis));    dis[1][0] = 0 , q.push(make_pair(1 , 0));    while(!q.empty())    {        x = q.front().first , y = q.front().second , q.pop() , inq[x][y] = 0;        for(i = head[x] ; i ; i = next[i])        {            if(dis[to[i]][y] > dis[x][y] + len[i])            {                dis[to[i]][y] = dis[x][y] + len[i];                if(!inq[to[i]][y]) inq[to[i]][y] = 1 , q.push(make_pair(to[i] , y));            }            if(y < k && dis[to[i]][y + 1] > dis[x][y] + len[i] / 2)            {                dis[to[i]][y + 1] = dis[x][y] + len[i] / 2;                if(!inq[to[i]][y + 1]) inq[to[i]][y + 1] = 1 , q.push(make_pair(to[i] , y + 1));            }        }    }    for(i = 0 ; i <= k ; i ++ ) ans = min(ans , dis[n][i]);    printf("%d\n" , ans);    return 0;}

#include <cstdio>#include <cmath>#include <algorithm>using namespace std;struct data{    int x , y , z;}a[1000010];int dx[1010] , dy[1010] , cnt , f[1010];bool cmp(data a , data b){    return a.z < b.z;}int find(int x){    return x == f[x] ? x : f[x] = find(f[x]);}int main(){    int n , k , i , j , cedge = 0 , tx , ty;    scanf("%d%d" , &n , &k);    for(i = 1 ; i <= n ; i ++ )        scanf("%d%d" , &dx[i] , &dy[i]);    for(i = 1 ; i <= n ; i ++ )        for(j = i + 1 ; j <= n ; j ++ )            a[++cnt].x = i , a[cnt].y = j , a[cnt].z = (dx[i] - dx[j]) * (dx[i] - dx[j]) + (dy[i] - dy[j]) * (dy[i] - dy[j]);    sort(a + 1 , a + cnt + 1 , cmp);    for(i = 1 ; i <= n ; i ++ )        f[i] = i;    for(i = 1 ; i <= cnt ; i ++ )    {        tx = find(a[i].x) , ty = find(a[i].y);        if(tx != ty)        {            if(cedge == n - k)            {                printf("%.2lf\n" , sqrt(a[i].z));                return 0;            }            else f[tx] = ty , cedge ++ ;        }    }    return 0;}

#include <cstdio>#include <algorithm>using namespace std;int head[500010] , to[1000010] , next[1000010] , cnt , log[500010] , fa[500010][21] , deep[500010];void add(int x , int y){    to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x){    int i;    for(i = 1 ; i <= log[deep[x]] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1];    for(i = head[x] ; i ; i = next[i])        if(to[i] != fa[x][0])            fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]);}int getlca(int x , int y){    int i;    if(deep[x] < deep[y]) swap(x , y);    for(i = log[deep[x] - deep[y]] ; ~i ; i -- )        if(deep[x] - (1 << i) >= deep[y])            x = fa[x][i];    if(x == y) return x;    for(i = log[deep[x]] ; ~i ; i -- )        if(fa[x][i] != fa[y][i])            x = fa[x][i] , y = fa[y][i];    return fa[x][0];}int main(){    int n , m , i , x , y , z , xy , xz , yz , t;    scanf("%d%d" , &n , &m);    for(i = 1 ; i < n ; i ++ )        scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);    for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;    dfs(1);    while(m -- )    {        scanf("%d%d%d" , &x , &y , &z);        xy = getlca(x , y) , xz = getlca(x , z) , yz = getlca(y , z) , t = deep[x] + deep[y] + deep[z] - 2 * deep[getlca(xy , z)];        if(deep[xy] > deep[xz] && deep[xy] > deep[yz]) printf("%d %d\n" , xy , t - deep[xy]);        else if(deep[xz] > deep[yz]) printf("%d %d\n" , xz , t - deep[xz]);        else printf("%d %d\n" , yz , t - deep[yz]);    }    return 0;}

#include <cstdio>#include <cstring>#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1#define N 100100int fa[N] , bl[N] , deep[N] , si[N] , pos[N] , tot;int head[N] , to[N] , next[N] , cnt;int sum[N << 2] , tag[N << 2] , n;char str[20];inline int read(){    int num = 0;    char ch;    while(ch < ‘0‘ || ch > ‘9‘) ch = getchar();    while(ch >= ‘0‘ && ch <= ‘9‘) num = num * 10 + ch - ‘0‘ , ch = getchar();    return num;}void add(int x , int y){    to[++cnt] = y;    next[cnt] = head[x];    head[x] = cnt;}void dfs1(int x){    int i;    si[x] = 1;    for(i = head[x] ; i ; i = next[i])    {        deep[to[i]] = deep[x] + 1;        dfs1(to[i]);        si[x] += si[to[i]];    }}void dfs2(int x , int c){    int i , k = n + 1;    pos[x] = ++tot;    bl[x] = c;    for(i = head[x] ; i ; i = next[i])        if(si[to[i]] > si[k])            k = to[i];    if(k != n + 1)    {        dfs2(k , c);        for(i = head[x] ; i ; i = next[i])            if(to[i] != k)                dfs2(to[i] , to[i]);    }}void pushup(int x){    sum[x] = sum[x << 1] + sum[x << 1 | 1];}void pushdown(int x , int m){    if(tag[x] != -1)    {        sum[x << 1] = tag[x] * (m - (m >> 1));        sum[x << 1 | 1] = tag[x] * (m >> 1);        tag[x << 1] = tag[x << 1 | 1] = tag[x];        tag[x] = -1;    }}void update(int b , int e , int a , int l , int r , int x){    if(b <= l && r <= e)    {        sum[x] = a * (r - l + 1);        tag[x] = a;        return;    }    pushdown(x , r - l + 1);    int mid = (l + r) >> 1;    if(b <= mid) update(b , e , a , lson);    if(e > mid) update(b , e , a , rson);    pushup(x);}int query(int b , int e , int l , int r , int x){    if(b <= l && r <= e)        return sum[x];    pushdown(x , r - l + 1);    int mid = (l + r) >> 1 , ans = 0;    if(b <= mid) ans += query(b , e , lson);    if(e > mid) ans += query(b , e , rson);    return ans;}void solveupdate(int x){    while(bl[x])    {        update(pos[bl[x]] , pos[x] , 1 , 1 , n , 1);        x = fa[bl[x]];    }    update(1 , pos[x] , 1 , 1 , n , 1);}int solvequery(int x){    int ans = 0;    while(bl[x])    {        ans += query(pos[bl[x]] , pos[x] , 1 , n , 1);        x = fa[bl[x]];    }    ans += query(1 , pos[x] , 1 , n , 1);    return ans;}int main(){    int i , q , x;    n = read();    for(i = 1 ; i < n ; i ++ )    {        fa[i] = read();        add(fa[i] , i);    }    dfs1(0);    dfs2(0 , 0);    memset(tag , -1 , sizeof(tag));    q = read();    while(q -- )    {        scanf("%s" , str);        x = read();        if(str[0] == ‘i‘)        {            printf("%d\n" , deep[x] - solvequery(x) + 1);            solveupdate(x);        }        else        {            printf("%d\n" , query(pos[x] , pos[x] + si[x] - 1 , 1 , n , 1));            update(pos[x] , pos[x] + si[x] - 1 , 0 , 1 , n , 1);        }    }    return 0;}

#include <cstdio>#include <algorithm>using namespace std;int a[1000010] , deep[1000010] , low[1000010] , tot , sta[1000010] , top , vis[1000010] , ins[1000010] , bel[1000010] , cnt , cd[1000010];void tarjan(int x){    deep[x] = low[x] = ++tot;    ins[x] = vis[x] = 1;    sta[++top] = x;    if(!vis[a[x]])        tarjan(a[x]) , low[x] = min(low[x] , low[a[x]]);    else if(ins[a[x]])        low[x] = min(low[x] , deep[a[x]]);    if(deep[x] == low[x])    {        int t;        cnt ++ ;        do        {            t = sta[top -- ];            ins[t] = 0;            bel[t] = cnt;        }while(t != x);    }}int main(){    int n , i , ans = 0;    scanf("%d" , &n);    for(i = 1 ; i <= n ; i ++ )        scanf("%d" , &a[i]);    for(i = 1 ; i <= n ; i ++ )        if(!vis[i])            tarjan(i);    for(i = 1 ; i <= n ; i ++ )        if(bel[i] != bel[a[i]])            cd[bel[i]] ++ ;    for(i = 1 ; i <= cnt ; i ++ )        if(!cd[i])            ans ++ ;    printf("%d\n" , ans);    return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 100010using namespace std;queue<int> q;int head[N] , to[N << 1] , next[N << 1] , cnt , rd[N] , cd[N] , f[N];void add(int x , int y){    to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}int main(){    int n , m , i , x , y , ans = 0;    scanf("%d%d" , &n , &m);    for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , cd[x] ++ , rd[y] ++ ;    for(i = 1 ; i <= n ; i ++ )    {        if(!rd[i])        {            if(cd[i]) f[i] = 1;            q.push(i);        }    }    while(!q.empty())    {        x = q.front() , q.pop();        for(i = head[x] ; i ; i = next[i])        {            f[to[i]] += f[x] , rd[to[i]] -- ;            if(!rd[to[i]]) q.push(to[i]);        }    }    for(i = 1 ; i <= n ; i ++ ) if(!cd[i]) ans += f[i];    printf("%d\n" , ans);    return 0;}

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char s1[1000010] , s2[1010];int nxt[1010];int main(){	int n , m , i , j;	scanf("%s%s" , s1 , s2) , n = strlen(s1) , m = strlen(s2);	nxt[0] = -1;	for(i = 1 , j = -1 ; i <= m ; i ++ )	{		while(~j && s2[j] != s2[i - 1]) j = nxt[j];		nxt[i] = ++j;	}	for(i = j = 0 ; i < n ; i ++ )	{		while(~j && s1[i] != s2[j]) j = nxt[j];		j ++ ;		if(j == m) printf("%d\n" , i - m + 2) , j = nxt[j];	}	for(i = 1 ; i <= m ; i ++ ) printf("%d " , nxt[i]);	return 0;}

#include <cstdio>#include <map>#define N 200010using namespace std;typedef unsigned long long ull;struct data{    ull b[N] , h1[N] , h2[N];    ull hash(int l , int r)    {        return (h1[r] - h1[l - 1] * b[r - l + 1]) * (h2[l] - h2[r + 1] * b[r - l + 1]);    }}t1 , t2;map<pair<ull , ull> , bool> f;int a[N] , sta[N] , top;int main(){    int n , i , j , cnt , ans = 0;    scanf("%d" , &n);    t1.b[0] = t2.b[0] = 1;    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);    for(i = 1 ; i <= n ; i ++ ) t1.b[i] = t1.b[i - 1] * 233 , t2.b[i] = t2.b[i - 1] * 2333;    for(i = 1 ; i <= n ; i ++ ) t1.h1[i] = t1.h1[i - 1] * 233 + a[i] , t2.h1[i] = t2.h1[i - 1] * 2333 + a[i];    for(i = n ; i >= 1 ; i -- ) t1.h2[i] = t1.h2[i + 1] * 233 + a[i] , t2.h2[i] = t2.h2[i + 1] * 2333 + a[i];    for(i = 1 ; i <= n ; i ++ )    {        f.clear() , cnt = 0;        for(j = 1 ; j + i - 1 <= n ; j += i)            if(!f[make_pair(t1.hash(j , j + i - 1) , t2.hash(j , j + i - 1))])                f[make_pair(t1.hash(j , j + i - 1) , t2.hash(j , j + i - 1))] = 1 , cnt ++ ;        if(cnt > ans) top = 1 , sta[top] = i , ans = cnt;        else if(cnt == ans) sta[++top] = i;    }    printf("%d %d\n" , ans , top);    for(i = 1 ; i < top ; i ++ ) printf("%d " , sta[i]);    printf("%d" , sta[top]);    return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 10000010using namespace std;queue<int> q;int next[N][4] , fail[N] , len[N] , tot = 1 , pos[100010][110];bool vis[N];char str[N] , w[N];int tra(char ch){    return ch == ‘E‘ ? 0 : ch == ‘S‘ ? 1 : ch == ‘W‘ ? 2 : 3;}void build(){    int x , i;    for(i = 0 ; i < 4 ; i ++ ) next[0][i] = 1;    q.push(1);    while(!q.empty())    {        x = q.front() , q.pop();        for(i = 0 ; i < 4 ; i ++ )        {            if(next[x][i]) fail[next[x][i]] = next[fail[x]][i] , q.push(next[x][i]);            else next[x][i] = next[fail[x]][i];        }    }}int main(){    int n , m , i , j , t;    scanf("%d%d%s" , &n , &m , str + 1);    for(i = 1 ; i <= m ; i ++ )    {        scanf("%s" , w + 1) , len[i] = strlen(w + 1);        for(j = t = 1 ; j <= len[i] ; j ++ )        {            if(!next[t][tra(w[j])]) next[t][tra(w[j])] = ++tot;            t = next[t][tra(w[j])] , pos[i][j] = t;        }    }    build();    vis[1] = 1 , t = 1;    for(i = 1 ; i <= n ; i ++ )    {        t = next[t][tra(str[i])];        for(j = t ; !vis[j] ; j = fail[j]) vis[j] = 1;    }    for(i = 1 ; i <= m ; i ++ )    {        for(j = len[i] ; j ; j -- ) if(vis[pos[i][j]]) break;        printf("%d\n" , j);    }    return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 1000010using namespace std;char str[N];int r[N] , sa[N] , ws[N] , wa[N] , wb[N] , n , m = 129;void getsa(){	int i , j , p , *x = wa , *y = wb;	for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ;	for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];	for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i;	for(p = j = 1 ; p < n ; j <<= 1 , m = p)	{		for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i;		for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j;		for(i = 0 ; i < m ; i ++ ) ws[i] = 0;		for(i = 0 ; i < n ; i ++ ) ws[x[y[i]]] ++ ;		for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];		for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i];		for(swap(x , y) , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ )		{			if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p - 1;			else x[sa[i]] = p ++ ;		}	}}int main(){	int i;	scanf("%s" , str) , n = strlen(str);	for(i = 0 ; i < n ; i ++ ) r[i] = str[i];	n ++ , getsa();	for(i = 1 ; i < n ; i ++ ) printf("%d " , sa[i] + 1);	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 200010using namespace std;char str[N];int next[N][26] , fa[N] , dis[N] , tot = 1 , last;long long ans;void ins(int c){	int p = last , np = last = ++tot;	dis[np] = dis[p] + 1;	while(p && !next[p][c]) next[p][c] = np , p = fa[p];	if(!p) fa[np] = 1;	else	{		int q = next[p][c];		if(dis[q] == dis[p] + 1) fa[np] = q;		else		{			int nq = ++tot;			memcpy(next[nq] , next[q] , sizeof(next[q])) , dis[nq] = dis[p] + 1 , fa[nq] = fa[q] , fa[np] = fa[q] = nq;			while(p && next[p][c] == q) next[p][c] = nq , p = fa[p];		}	}	ans += dis[np] - dis[fa[np]];}int main(){	int n , i;	scanf("%d" , &n);	while(n -- )	{		scanf("%s" , str) , last = 1;		for(i = 0 ; str[i] ; i ++ ) ins(str[i] - ‘a‘) , printf("%lld\n" , ans);	}	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char str[5000010] , tmp[10000010];int p[10000010];int main(){	int n , i , mx = 0 , last , pos , ans = -1;	scanf("%s" , str + 1) , n = strlen(str + 1);	tmp[0] = ‘$‘;	for(i = 1 ; i <= n ; i ++ ) tmp[(i << 1) - 1] = ‘#‘ , tmp[i << 1] = str[i];	tmp[n << 1 | 1] = ‘#‘;	for(i = 1 ; i <= 2 * n ; i ++ )	{		if(i <= mx) p[i] = min(p[2 * last - i] , mx - i + 1);		else p[i] = 1;		while(tmp[i - p[i]] == tmp[i + p[i]]) p[i] ++ ;		if(p[i] + i - 1 > mx) mx = p[i] + i - 1 , last = i;	}	for(i = 1 ; i <= 2 * n ; i ++ )		if(p[i] - 1 > ans)			ans = p[i] - 1 , pos = (i - p[i] + 2) >> 1;	printf("%d\n%d\n" , pos , ans);	return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 1000010#define M 8000010using namespace std;queue<int> q;int head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N];void add(int x , int y , int z){	to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;	to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){	int x , i;	memset(dis , 0 , sizeof(dis));	while(!q.empty()) q.pop();	dis[s] = 1 , q.push(s);	while(!q.empty())	{		x = q.front() , q.pop();		for(i = head[x] ; i ; i = next[i])		{			if(val[i] && !dis[to[i]])			{				dis[to[i]] = dis[x] + 1;				if(to[i] == t) return 1;				q.push(to[i]);			}		}	}	return 0;}int dinic(int x , int low){	if(x == t) return low;	int temp = low , i , k;	for(i = head[x] ; i ; i = next[i])	{		if(val[i] && dis[to[i]] == dis[x] + 1)		{			k = dinic(to[i] , min(temp , val[i]));			if(!k) dis[to[i]] = 0;			val[i] -= k , val[i ^ 1] += k;			if(!(temp -= k)) break;		}	}	return low - temp;}int main(){	int n , m , i , x , y , z , ans = 0;	scanf("%d%d%d%d" , &n , &m , &s , &t);	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z);	while(bfs()) ans += dinic(s , 0x7fffffff);	printf("%d\n" , ans);	return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 410#define M 30010using namespace std;queue<int> q;int head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , inq[N] , from[N] , pre[N];void add(int x , int y , int v , int c){	to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;	to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){	int x , i;	memset(from , -1 , sizeof(from));	memset(dis , 0x3f , sizeof(dis));	dis[s] = 0 , q.push(s);	while(!q.empty())	{		x = q.front() , q.pop() , inq[x] = 0;		for(i = head[x] ; i ; i = next[i])		{			if(val[i] && dis[to[i]] > dis[x] + cost[i])			{				dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i;				if(!inq[to[i]]) inq[to[i]] = 1 , q.push(to[i]);			}		}	}	return ~from[t];}int main(){	int n , m , i , x , y , v , c , ff = 0 , cc = 0;	scanf("%d%d" , &n , &m) , s = 1 , t = n;	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d" , &x , &y , &v , &c) , add(x , y , v , c);	while(spfa())	{		x = 0x7fffffff;		for(i = t ; i != s ; i = from[i]) x = min(x , val[pre[i]]);		ff += x , cc += x * dis[t];		for(i = t ; i != s ; i = from[i]) val[pre[i]] -= x , val[pre[i] ^ 1] += x;	}	printf("%d %d\n" , ff , cc);	return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 210#define M 21000using namespace std;queue<int> q;int head[N] , to[M] , low[M] , val[M] , id[M] , next[M] , cnt = 1 , ind[N] , s , t , dis[N] , ans[M];void add(int x , int y , int l , int r , int i){	to[++cnt] = y , val[cnt] = r - l , next[cnt] = head[x] , head[x] = cnt , low[cnt] = l , id[cnt] = i;	to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;	ind[x] -= l , ind[y] += l;}bool bfs(){	int x , i;	memset(dis , 0 , sizeof(dis));	while(!q.empty()) q.pop();	dis[s] = 1 , q.push(s);	while(!q.empty())	{		x = q.front() , q.pop();		for(i = head[x] ; i ; i = next[i])		{			if(val[i] && !dis[to[i]])			{				dis[to[i]] = dis[x] + 1;				if(to[i] == t) return 1;				q.push(to[i]);			}		}	}	return 0;}int dinic(int x , int low){	if(x == t) return low;	int temp = low , i , k;	for(i = head[x] ; i ; i = next[i])	{		if(val[i] && dis[to[i]] == dis[x] + 1)		{			k = dinic(to[i] , min(temp , val[i]));			if(!k) dis[to[i]] = 0;			val[i] -= k , val[i ^ 1] += k;			if(!(temp -= k)) break;		}	}	return low - temp;}int main(){	int n , m , i , x , y , l , r , sum = 0;	scanf("%d%d" , &n , &m) , s = 0 , t = n + 1;	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d" , &x , &y , &l , &r) , add(x , y , l , r , i);	for(i = 1 ; i <= n ; i ++ )	{		if(ind[i] > 0) add(s , i , 0 , ind[i] , 0) , sum += ind[i];		if(ind[i] < 0) add(i , t , 0 , -ind[i] , 0);	}	while(bfs()) sum -= dinic(s , 1 << 30);	if(sum) puts("NO");	else	{		puts("YES");		for(x = 1 ; x <= n ; x ++ )			for(i = head[x] ; i ; i = next[i])				if(id[i])					ans[id[i]] = low[i] + val[i ^ 1];		for(i = 1 ; i <= m ; i ++ ) printf("%d\n" , ans[i]);	}	return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 210#define M 21000using namespace std;queue<int> q;int head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N] , ind[N];void add(int x , int y , int z){	to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;	to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){	int x , i;	memset(dis , 0 , sizeof(dis));	while(!q.empty()) q.pop();	dis[s] = 1 , q.push(s);	while(!q.empty())	{		x = q.front() , q.pop();		for(i = head[x] ; i ; i = next[i])		{			if(val[i] && !dis[to[i]])			{				dis[to[i]] = dis[x] + 1;				if(to[i] == t) return 1;				q.push(to[i]);			}		}	}	return 0;}int dinic(int x , int low){	if(x == t) return low;	int temp = low , i , k;	for(i = head[x] ; i ; i = next[i])	{		if(val[i] && dis[to[i]] == dis[x] + 1)		{			k = dinic(to[i] , min(temp , val[i]));			if(!k) dis[to[i]] = 0;			val[i] -= k , val[i ^ 1] += k;			if(!(temp -= k)) break;		}	}	return low - temp;}int main(){	int n , m , b , e , i , x , y , l , r , ans = 0 , sum = 0;	scanf("%d%d%d%d" , &n , &m , &b , &e) , s = 0 , t = n + 1;	add(e , b , 1 << 30);	for(i = 1 ; i <= m ; i ++ )		scanf("%d%d%d%d" , &x , &y , &l , &r) , add(x , y , r - l) , ind[x] -= l , ind[y] += l;	for(i = 1 ; i <= n ; i ++ )	{		if(ind[i] > 0) add(s , i , ind[i]) , sum += ind[i];		if(ind[i] < 0) add(i , t , -ind[i]);	}	while(bfs()) sum -= dinic(s , 1 << 30);	if(sum) puts("please go home to sleep");	else	{		ans = val[3] , val[2] = val[3] = 0;		for(i = head[s] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;		for(i = head[t] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;		s = b , t = e;		while(bfs()) ans += dinic(s , 1 << 30);		printf("%d\n" , ans);	}	return 0;}

#include <cstdio>#include <cstring>#include <queue>#define N 210#define M 21000using namespace std;queue<int> q;int head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N] , ind[N];void add(int x , int y , int z){	to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;	to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){	int x , i;	memset(dis , 0 , sizeof(dis));	while(!q.empty()) q.pop();	dis[s] = 1 , q.push(s);	while(!q.empty())	{		x = q.front() , q.pop();		for(i = head[x] ; i ; i = next[i])		{			if(val[i] && !dis[to[i]])			{				dis[to[i]] = dis[x] + 1;				if(to[i] == t) return 1;				q.push(to[i]);			}		}	}	return 0;}int dinic(int x , int low){	if(x == t) return low;	int temp = low , i , k;	for(i = head[x] ; i ; i = next[i])	{		if(val[i] && dis[to[i]] == dis[x] + 1)		{			k = dinic(to[i] , min(temp , val[i]));			if(!k) dis[to[i]] = 0;			val[i] -= k , val[i ^ 1] += k;			if(!(temp -= k)) break;		}	}	return low - temp;}int main(){	int n , m , b , e , i , x , y , l , r , ans = 0 , sum = 0;	scanf("%d%d%d%d" , &n , &m , &b , &e) , s = 0 , t = n + 1;	add(e , b , 1 << 30);	for(i = 1 ; i <= m ; i ++ )		scanf("%d%d%d%d" , &x , &y , &l , &r) , add(x , y , r - l) , ind[x] -= l , ind[y] += l;	for(i = 1 ; i <= n ; i ++ )	{		if(ind[i] > 0) add(s , i , ind[i]) , sum += ind[i];		if(ind[i] < 0) add(i , t , -ind[i]);	}	while(bfs()) sum -= dinic(s , 1 << 30);	if(sum) puts("please go home to sleep");	else	{		ans = val[3] , val[2] = val[3] = 0;		for(i = head[s] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;		for(i = head[t] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;		s = b , t = e;		while(bfs()) ans += dinic(s , 1 << 30);		printf("%d\n" , ans);	}	return 0;}

#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;struct data{	int x , y , z , cnt , sum;}a[N] , tmp[N];int f[N << 1] , k , tot , ans[N];bool cmp(data a , data b){	return a.x == b.x ? a.y == b.y ? a.z < b.z : a.y < b.y : a.x < b.x;}void add(int x , int a){	int i;	for(i = x ; i <= k ; i += i & -i ) f[i] += a;}int query(int x){	int i , ans = 0;	for(i = x ; i ; i -= i & -i) ans += f[i];	return ans;}void solve(int l , int r){	if(l >= r) return;	int mid = (l + r) >> 1 , p1 = l , p2 = mid + 1 , i;	solve(l , mid) , solve(mid + 1 , r);	for(i = l ; i <= r ; i ++ )	{		if(p1 == mid + 1 || (p2 != r + 1 && a[p2].y < a[p1].y)) a[p2].sum += query(a[p2].z) , tmp[i] = a[p2 ++ ];		else add(a[p1].z , a[p1].cnt) , tmp[i] = a[p1 ++ ];	}	for(i = l ; i <= mid ; i ++ ) add(a[i].z , -a[i].cnt);	for(i = l ; i <= r ; i ++ ) a[i] = tmp[i];}int main(){	int n , i;	scanf("%d%d" , &n , &k);	for(i = 1 ; i <= n ; i ++ ) scanf("%d%d%d" , &a[i].x , &a[i].y , &a[i].z);	sort(a + 1 , a + n + 1 , cmp);	for(i = 1 ; i <= n ; i ++ )	{		if((a[i].x != a[i - 1].x) || (a[i].y != a[i - 1].y) || (a[i].z != a[i - 1].z)) a[++tot] = a[i];		a[tot].cnt ++ ;	}	solve(1 , tot);	for(i = 1 ; i <= tot ; i ++ ) ans[a[i].sum + a[i].cnt] += a[i].cnt;	for(i = 1 ; i <= n ; i ++ ) printf("%d\n" , ans[i]);	return 0;}

#include <cstdio>#include <cmath>#include <algorithm>#define N 110using namespace std;const double eps = 1e-7;int n , m;double a[N][N] , b[N] , c[N] , ans;void pivot(int l , int e){	int i , j;	b[l] /= a[l][e];	for(i = 1 ; i <= n ; i ++ ) if(i != e) a[l][i] /= a[l][e];	a[l][e] = 1 / a[l][e];	for(i = 1 ; i <= m ; i ++ )	{		if(i != l && fabs(a[i][e]) > eps)		{			b[i] -= b[l] * a[i][e];			for(j = 1 ; j <= n ; j ++ ) if(j != e) a[i][j] -= a[l][j] * a[i][e];			a[i][e] = -a[l][e] * a[i][e];		}	}	ans += b[l] * c[e];	for(i = 1 ; i <= n ; i ++ ) if(i != e) c[i] -= c[e] * a[l][i];	c[e] = -c[e] * a[l][e];}void simplex(){	int i , l , e;	double tmp;	while(1)	{		for(i = 1 ; i <= n ; i ++ ) if(c[i] > eps) break;		if(i > n) break;		e = i;		for(i = 1 , tmp = 1e10 ; i <= m ; i ++ )			if(a[i][e] > eps && b[i] / a[i][e] < tmp)				l = i , tmp = b[i] / a[i][e];		if(tmp == 1e10)		{			ans = -1;			break;		}		pivot(l , e);	}}int main(){	int i , j;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= m ; i ++ )	{		for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &a[i][j]);		scanf("%lf" , &b[i]);	}	for(i = 1 ; i <= n ; i ++ ) scanf("%lf" , &c[i]);	simplex();	if(ans != -1) printf("%.2lf\n" , ans);	else puts("Infinity");	return 0;}