#include<bits/stdc++.h>using namespace std;const int Maxn=300020;typedef long long LL;typedef pair<int,int>pi;struct P{	double x,y;	P(){x=y=0;}	P(double _x,double _y){x=_x,y=_y;}	P operator+(P v){return P(x+v.x,y+v.y);}	P operator-(P v){return P(x-v.x,y-v.y);}	P operator*(double v){return P(x*v,y*v);}	double len(){return hypot(x,y);}	double len_sqr(){return x*x+y*y;}	P rot90(){return P(-y,x);}}a[111111],A,B;const double eps=1e-8;int sgn(double x){	if(x<-eps)return -1;	if(x>eps)return 1;	return 0;}double cross(P a,P b){	return a.x*b.y-a.y*b.x;}P line_intersection(P a,P b,P p,P q){	double U=cross(p-a,q-p),D=cross(b-a,q-p);	return a+(b-a)*(U/D);}int main(){	freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	int n,m,i;	scanf("%d%d",&n,&m);	for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);	while(m--){		scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);		P t=B-A;		t=t.rot90();		//printf("t=%.4f %.4f\n",t.x,t.y);		for(i=1;i<=n;i++)if(cross(a[i]-A,B-A)>0){			P o=line_intersection(A,B,a[i],a[i]+t);			//printf("->%d %.4f %.4f\n",i,(a[i]+t).x,(a[i]+t).y);			a[i]=(o*2.0)-a[i];		}		//for(i=1;i<=n;i++)printf("%.4f %.4f\n",a[i].x,a[i].y);	}	for(i=1;i<=n;i++)printf("%.8f %.8f\n",a[i].x,a[i].y);	return 0;}

#include<bits/stdc++.h>using namespace std;const int Maxn=300020;int n;string name[Maxn];map<string,int>id;int a[Maxn<<2];char s[Maxn];bool check(int id1,int id2){	id1+=n;id2+=n;	for(int i=id2;i;i>>=1)if(a[i]==id1)return 1;	return 0;}int main(){	freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	while(scanf("%d",&n)!=EOF){		n=1<<n;		id.clear();		for(int i=0;i<n;i++)		cin>>name[i],id[name[i]]=i,a[n+i]=n+i;		int cur=n>>1,tot=0;		scanf("%s",s);		//printf("sss=%s\n",s);		for(;cur;cur>>=1){			for(int i=cur;i<cur<<1;i++){				char c=s[tot++];				if(c==‘W‘)a[i]=a[i<<1];				else a[i]=a[i<<1|1];			}		}		int q;scanf("%d",&q);		//printf("q=%d\n",q);		while(q--){			string s1,s2;			cin>>s1>>s2;			int id1=id[s1],id2=id[s2];			if(check(id1,id2)){				puts("Win");			}			else if(check(id2,id1)){puts("Lose");}			else puts("Unknown");		}	}}

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 1000005 ;const int MAXE = 1000005 ;struct Edge {	int v , c , n ;	Edge () {}	Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}} ;Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , vis[MAXN] , cnt[MAXN] , Q[MAXN] , head , tail ;int maxv[MAXN] ;int n , m ;void init () {	cntE = 0 ;	clr ( H , -1 ) ;}void addedge ( int u , int v , int c ) {	E[cntE] = Edge ( v , c , H[u] ) ;	H[u] = cntE ++ ;}int spfa () {	while ( head != tail ) {		int u = Q[head ++] ;		if ( head == MAXN ) head = 0 ;		vis[u] = 0 ;		for ( int i = H[u] ; ~i ; i = E[i].n ) {			//if ( clock () > 1.99 * CLOCKS_PER_SEC ) return 0 ;			int v = E[i].v ;			if ( d[v] < d[u] + E[i].c ) {				d[v] = d[u] + E[i].c ;				if ( d[v] > maxv[v] ) return 0 ;				if ( !vis[v] ) {					vis[v] = 1 ;					cnt[v] ++ ;					if ( cnt[v] == n + 1 ) return 0 ;					if ( d[Q[head]] < d[v] ) {						-- head ;						if ( head < 0 ) head = MAXN - 1 ;						Q[head] = v ;					} else {						Q[tail ++] = v ;						if ( tail == MAXN ) tail = 0 ;					}				}			}		}	}	return 1 ;}void solve () {	init () ;	int ok = 1 ;	head = tail = 0 ;	for ( int i = 1 ; i <= n ; ++ i ) {		d[i] = -2e9 ;		maxv[i] = 2e9 ;		Q[tail ++] = i ;		vis[i] = 1 ;		cnt[i] = 0 ;	}	for ( int i = 0 ; i < m ; ++ i ) {		int op , x , xv , y , yv ;		scanf ( "%d%d%d%d%d" , &op , &x , &xv , &y , &yv ) ;		if ( x == 0 ) {			if ( y == 0 ) addedge ( xv , yv , op ) ;			else maxv[xv] = min ( maxv[xv] , yv - op ) ;		} else {			if ( y == 0 ) d[yv] = max ( d[yv] , xv + op ) ;			else if ( xv + op > yv ) ok = 0 ;		}	}	if ( !ok || !spfa () ) {		puts ( "NO" ) ;		return ;	}	puts ( "YES" ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		printf ( "%d\n" , d[i] ) ;	}}int main () {	freopen ( "input.txt" , "r" , stdin ) ;	freopen ( "output.txt" , "w" , stdout ) ;	while ( ~scanf ( "%d%d" , &m , &n ) ) solve () ;	return 0 ;}

#include <bits/stdc++.h>using namespace std ;const int MAXN = 100005 ;struct Node {	int p , a ;	bool operator < ( const Node& t ) const {		return p < t.p ;		//return min ( a - p , t.a - p - t.p ) > min ( a - p - t.p , t.a - t.p ) ;	}} ;Node a[MAXN] ;int d , n ;void solve () {	int S , P , A ;	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d%d%d" , &S , &P , &A ) ;		a[i].p = S * P ;		a[i].a = S * A ;	}	sort ( a + 1 , a + n + 1 ) ;	double l = 0 , r = 1e6 ;	for ( int o = 0 ; o <= 100 ; ++ o ) {		double x = ( l + r ) / 2 , mid = x ;		double D = 0 ;		int ok = 0 ;		for ( int i = 1 ; i <= n ; ++ i ) {			double l = max ( 0.0 , 1.0 * ( a[i].a - x ) / a[i].p ) ;			D += l ;			x += l * a[i].p ;			if ( D >= d ) {				ok = 1 ;				break ;			}		}		if ( ok ) l = mid ;		else r = mid ;	}	printf ( "%.10f\n" , l ) ;}	int main () {	freopen ( "input.txt" , "r" , stdin ) ;	freopen ( "output.txt" , "w" , stdout ) ;	while ( ~scanf ( "%d%d" , &d , &n ) ) solve () ;	return 0 ;}

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 1605 ;const double INF = 1e50 ;int n , m , k , vr , vf ;double d[MAXN] , G[MAXN][MAXN] ;int vis[MAXN] , p[MAXN] ;int x[MAXN] , y[MAXN] ;vector < int > S ;double get_dis ( int x , int y ) {	return sqrt ( 1.0 * x * x + 1.0 * y * y ) ;}void dij ( int s ) {	for ( int i = 1 ; i <= n ; ++ i ) {		d[i] = INF ;		vis[i] = 0 ;		p[i] = 0 ;	}	d[s] = 0 ;	for ( int i = 1 ; i < n ; ++ i ) {		double minv = INF ;		int u = s ;		for ( int j = 1 ; j <= n ; ++ j ) {			if ( !vis[j] && d[j] < minv ) {				minv = d[j] ;				u = j ;			}		}		vis[u] = 1 ;		for ( int j = 1 ; j <= n ; ++ j ) {			if ( !vis[j] && d[u] + G[u][j] < d[j] ) {				d[j] = d[u] + G[u][j] ;				p[j] = u ;			}		}	}}void insert ( int o ) {	if ( p[o] ) {		insert ( p[o] ) ;		S.push_back ( p[o] ) ;	}}void solve () {	S.clear () ;	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d%d" , &x[i] , &y[i] ) ;		for ( int j = 1 ; j <= i ; ++ j ) {			G[i][j] = G[j][i] = get_dis ( x[i] - x[j] , y[i] - y[j] ) / vf ;		}	}	for ( int i = 0 ; i < m ; ++ i ) {		int u , v ;		scanf ( "%d%d" , &u , &v ) ;		G[u][v] = G[v][u] = G[u][v] * vf / vr ;	}	int pre = 1 , now ;	double ans = 0 ;	for ( int i = 1 ; i <= k ; ++ i ) {		scanf ( "%d" , &now ) ;		dij ( pre ) ;		insert ( now ) ;		ans += d[now] ;		pre = now ;	}	dij ( now ) ;	insert ( n ) ;	ans += d[n] ;	S.push_back ( n ) ;	printf ( "%.10f\n" , ans ) ;	for ( int i = 0 ; i < S.size () ; ++ i ) {		i && putchar ( ‘ ‘ ) ;		printf ( "%d" , S[i] ) ;	}	puts ( "" ) ;}int main () {	freopen ( "input.txt" , "r" , stdin ) ;	freopen ( "output.txt" , "w" , stdout ) ;	while ( ~scanf ( "%d%d%d%d%d" , &n , &m , &k , &vr , &vf ) ) solve () ;	return 0 ;}

#include<bits/stdc++.h>using namespace std;const int Maxn=300020;typedef long long LL;typedef pair<int,int>pi;void scan(LL &x){	char s[10];scanf("%s",s);	int ned=5;	int has=0;	x=0;	for(int i=0;s[i];i++){		if(s[i]==‘.‘){			has=1;			continue;		}		x=x*10+s[i]-‘0‘;		if(has)ned--;	}	for(int i=0;i<ned;i++)x=x*10;}int main(){		freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	int _;scanf("%d",&_);	while(_--){		LL a,b,c;		scan(a);		scan(b);		scan(c);		LL tot=a*b*c;		LL res=tot/a+tot/b+tot/c;		//printf("a=%lld b=%lld c=%lld\n",a,b,c);		//printf("res=%lld tot=%lld\n",res,tot);		if(res*100000<tot)puts("YES");		else puts("NO");	}}

#include<bits/stdc++.h>using namespace std;const int Maxn=300020;typedef long long LL;typedef pair<int,int>pi;int n,S;pi a[Maxn];int dp[2][50020][2];void up(int &x,int y){x=max(x,y);}int main(){	freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	while(scanf("%d%d",&n,&S)!=EOF){		for(int i=0;i<n;i++){			scanf("%d%d",&a[i].first,&a[i].second);		}		sort(a,a+n);		memset(dp,-1,sizeof dp);		dp[0][0][0]=0;		int cs=0;		for(int i=0;i<n;i++){			int islast=(i==n-1)||(a[i+1].first!=a[i].first);			memset(dp[cs^1],-1,sizeof dp[cs^1]);			int w=a[i].second;			for(int j=0;j<=S;j++){				int nw=w+j;				//if(nw>S)continue;				for(int k=0;k<2;k++){					int val=dp[cs][j][k];					if(val<0)continue;					up(dp[cs^1][j][islast?0:k],val);					if(nw>S)continue;					up(dp[cs^1][nw][islast?0:1],val+(k!=1));				}			}			cs^=1;		}		int ans=max(dp[cs][S][0],dp[cs][S][1]);		if(ans<0)puts("Impossible");		else printf("%d\n",ans);	}}

#include<cstdio>typedef unsigned int UI ;UI Hash ( UI v ) {	v = v + ( v << 10 ) ;	v = v ^ ( v >> 6 ) ;	v = v + ( v << 3 ) ;	v = v ^ ( v >> 11 ) ;	v = v + ( v << 16 ) ;	return v;}typedef long long ll;ll exgcd(ll a,ll b,ll&x,ll&y){  if(!b)return x=1,y=0,a;  ll d=exgcd(b,a%b,x,y),t=x;  return x=y,y=t-a/b*y,d;}ll cal(ll a,ll b,ll n){  ll x,y,d=exgcd(a,n,x,y);  x=(x%n+n)%n;  return x*(b/d)%(n/d);}UI F(UI v,int B){  ll a=(1U<<B)+1;  ll b=v;  ll n=1LL<<32;  return cal(a,b,n);}UI G11(UI v){  UI G=v>>21,H=(v>>10)&((1U<<11)-1),I=v&((1U<<10)-1);  UI A=G;  UI B=H^A;  UI C=I^(B>>1);  return (A<<21)|(B<<10)|(C);}UI G6(UI v){  UI a=v>>26,b=(v>>20)&((1U<<6)-1),c=(v>>14)&((1U<<6)-1),     d=(v>>8)&((1U<<6)-1),e=(v>>2)&((1U<<6)-1),f=v&((1U<<2)-1);  UI A=a;  UI B=A^b;  UI C=B^c;  UI D=C^d;  UI E=D^e;  UI F=(E>>4)^f;  return (A<<26)|(B<<20)|(C<<14)|(D<<8)|(E<<2)|F;}UI Hash2 ( UI v ) {	v = F(v,16);	v = G11(v);	v = F(v,3);	v = G6(v);	v = F(v,10);	return v;}int cal(UI v){  UI t=v;  for(int i=1;;i++){    t=Hash(t);    if(t==v)return i;  }}UI n ;int main () {	freopen ( "input.txt" , "r" , stdin ) ;	freopen ( "output.txt" , "w" , stdout ) ;	int T ;	scanf ( "%d" , &T ) ;	while ( T -- ) {		scanf ( "%u" , &n ) ;		printf ( "%u\n" , Hash2 ( n ) ) ;	}	return 0 ;}

#include<bits/stdc++.h>using namespace std;const int Maxn=300020;typedef long long LL;int n,S;vector<int>V[Maxn];int main(){	freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	while(scanf("%d%d",&n,&S)!=EOF){		vector<int>tmp;		for(int i=1;i<=n;i++)V[i].clear();		for(int i=1;i<=n;i++){			int x,y;scanf("%d%d",&x,&y);			V[x].push_back(y);		}		for(int i=1;i<=n;i++){			if(!V[i].size())continue;			sort(V[i].begin(),V[i].end());			tmp.push_back(V[i][0]);		}		sort(tmp.begin(),tmp.end());		LL cur=0;		int ans=0;		for(int i=0;i<tmp.size();i++){			if(cur+tmp[i]<=S){				cur+=tmp[i];				ans++;			}			else break;		}		printf("%d\n",ans);	}}

#include<bits/stdc++.h>using namespace std;const int Maxn=300020;typedef long long LL;typedef pair<int,int>pi;int n,m;int di[2][2]={{1,0},{0,1}};int Mp[22][22];int col[22][22];int ltc[]={1,1,2,3,1,1};int wc[]={1,1,1,1,2,3};int ans[11];int base[]={0,1,3,2,3,2,1,5,5,1,2,2,2,2,1,1,2,2,2,2,3,10,5,10,5,10,10,10	    ,5,5,10,10,3};int main(){	freopen("input.txt","r",stdin);	freopen("output.txt","w",stdout);	col[1][1]=5;	for(int i=2;i<=5;i++){		col[i][i]=4;	}	col[6][2]=col[2][6]=3;	col[4][1]=col[1][4]=col[3][7]=col[7][3]=col[7][7]=2;	for(int i=1;i<=7;i++){		for(int j=1;j<=7;j++){			col[16-i][j]=col[i][16-j]=col[i][j];		}	}	col[8][1]=col[1][8]=col[8][15]=col[15][8]=5;	col[8][4]=col[4][8]=col[8][12]=col[12][8]=2;	col[8][8]=1;	for(int i=1;i<=7;i++){		for(int j=9;j<=15;j++){			col[16-i][j]=col[i][j];		}	}	scanf("%d%d",&n,&m);	//puts("ok");	for(int i=1,turn=0;i<=m;i++,(turn=(turn+1)%n)){		int k;scanf("%d",&k);		//printf("kk=%d\n",k);		int cnt=0;		for(int it=0;it<k;it++){			char d;			int curx,cury;			int num;scanf("%d %c%d%d",&num,&d,&curx,&cury);			int ty=d==‘h‘?0:1;			int tmp=0,mul=1;			for(int it2=0;it2<num;it2++){				int x;scanf("%d",&x);				if(!Mp[curx][cury])cnt++;				Mp[curx][cury]=x;				tmp+=base[x]*ltc[col[curx][cury]];				mul*=wc[col[curx][cury]];				curx+=di[ty][0];				cury+=di[ty][1];			}			ans[turn]+=tmp*mul;					}		if(cnt>=7)ans[turn]+=15;	}	for(int i=0;i<n;i++)printf("%d\n",ans[i]);}