stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

const int N = 200005, P = 1000000007;

int n;

std::vector<int> E[N];

int fac[N], inv[N];

int sz[N], f[N], g[N], ans[N];

int qpow(int a, int b = P - 2){

	int s = 1;

	for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) s = 1ll * s * a % P;

	return s;

}

void init(int n){

	fac[0] = 1;

	for (register int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % P;

	inv[n] = qpow(fac[n], P - 2);

	for (register int i = n; i; --i) inv[i - 1] = 1ll * inv[i] * i % P;

}

int C(int n, int m){

	if (m < 0 || m > n) return 0;

	return 1ll * fac[n] * inv[m] % P * inv[n - m] % P; 

}

void dfs_f(int u, int fa = 0){

	f[u] = 1, sz[u] = 1;

	for (int v : E[u])

		if (v != fa){

			dfs_f(v, u), sz[u] += sz[v];

			f[u] = 1ll * f[u] * f[v] % P * C(sz[u] - 1, sz[v]) % P;

		}

}

void dfs_g(int u, int fa = 0){

	ans[u] = 1ll * f[u] * g[u] % P * C(n - 1, n - sz[u]) % P;

	for (int v : E[u])

		if (v != fa){

			g[v] = 1ll * ans[u] * qpow(1ll * f[v] * C(n - 1, sz[v]) % P, P - 2) % P;

			dfs_g(v, u);

		}

}

int main(){

	scanf("%d", &n);

	for (register int i = 1, u, v; i < n; ++i)

		scanf("%d%d", &u, &v), E[u].push_back(v), E[v].push_back(u);

	init(n);

	dfs_f(1), g[1] = 1, dfs_g(1);

	for (register int i = 1; i <= n; ++i) printf("%d\n", ans[i]);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

template<class t> inline t read(t &x){

	char c=getchar();bool f=0;x=0;

	while(!isdigit(c)) f|=c=='-',c=getchar();

	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();

	if(f) x=-x;return x;

}

template<class t> inline void write(t x){

	if(x<0) putchar('-'),write(-x);

	else{if(x>9) write(x/10);putchar('0'+x%10);}

}



#define int long long



const int mod=1e9+7,N=2e5+5;

int en,h[N],fac[N],inv[N],g[N],f[N],n,sz[N];



struct edge{

	int n,v;

}e[N<<1];



void add(int x,int y){

	e[++en]=(edge){h[x],y};

	h[x]=en;

}



int fpow(int x,int y){

	int res=1;

	for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;

	return res;

}



int C(int x,int y){

	return fac[x]*inv[y]%mod*inv[x-y]%mod;

}



void dfs1(int x,int fa){

	f[x]=1;

	for(int i=h[x];i;i=e[i].n){

		int y=e[i].v;

		if(y==fa) continue;

		dfs1(y,x);

		sz[x]+=sz[y];

		f[x]=f[x]*f[y]%mod*C(sz[x],sz[y])%mod;

	}

	sz[x]++;

}



void dfs2(int x,int fa){

	for(int i=h[x];i;i=e[i].n){

		int y=e[i].v;

		if(y==fa) continue;

		g[y]=f[y]*g[x]%mod*fpow(f[y]*C(n-1,sz[y])%mod,mod-2)%mod*C(n-1,n-sz[y])%mod;

		dfs2(y,x);

	}

}



signed main(){

	read(n);

	for(int i=1,x,y;i<n;i++){

		read(x);read(y);

		add(x,y);add(y,x);

	}

	fac[0]=1;

	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;

	inv[n]=fpow(fac[n],mod-2);

	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

	dfs1(1,0);

	g[1]=f[1];

	dfs2(1,0);

	for(int i=1;i<=n;i++) write(g[i]),puts("");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



const int N = 2e5 + 5, mod = 1e9 + 7;



int n;

int siz[N], mul[N], ans[N];

vector<int> g[N];



int pw(int x, int y) {

    int res = 1;

    while (y) {

        if (y & 1)

            res = (ll)res * x % mod;

        x = (ll)x * x % mod;

        y >>= 1;

    }

    return res; 

}



void dfs(int u, int fa) {

    siz[u] = 1, mul[u] = 1;

    for (auto v : g[u]) 

        if (v != fa) {

            dfs(v, u);

            siz[u] += siz[v];

            mul[u] = (ll)mul[u] * mul[v] % mod;

        }

    mul[u] = (ll)mul[u] * siz[u] % mod;

}



void dfs2(int u, int fa, int fromFa) {

    if (u != 1)

        ans[u] = (ll)mul[u] * pw(siz[u], mod - 2) % mod * n % mod * fromFa % mod;

    else 

        ans[u] = (ll)mul[u] * fromFa % mod; 

    for (auto v : g[u]) 

        if (v != fa) {

            int tmp = (ll)fromFa * mul[u] % mod * pw(mul[v], mod - 2) % mod * pw(siz[u], mod - 2) % mod * (n - siz[v]) % mod;

            dfs2(v, u, tmp);

        }

}



int main() {

    ios::sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i < n; i++) {

        int u, v;

        cin >> u >> v;

        g[u].push_back(v);

        g[v].push_back(u);

    }

    dfs(1, 0);

    dfs2(1, 0, 1);

    int x = 1;

    for (int i = 1; i <= n; i++)

        x = (ll)x * i % mod;

    for (int i = 1; i <= n; i++)

        cout << (ll)x * pw(ans[i], mod - 2) % mod << '\n';

    return 0; 

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

template<class t> inline t read(t &x){

	char c=getchar();bool f=0;x=0;

	while(!isdigit(c)) f|=c=='-',c=getchar();

	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();

	if(f) x=-x;return x;

}

template<class t> inline void write(t x){

	if(x<0) putchar('-'),write(-x);

	else{if(x>9) write(x/10);putchar('0'+x%10);}

}



#define int long long



const int mod=1e9+7,N=2e5+5;

int en,h[N],fac[N],inv[N],g[N],f[N],n,sz[N];



struct edge{

	int n,v;

}e[N<<1];



void add(int x,int y){

	e[++en]=(edge){h[x],y};

	h[x]=en;

}



int fpow(int x,int y){

	int res=1;

	for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;

	return res;

}



int C(int x,int y){

	return fac[x]*inv[y]%mod*inv[x-y]%mod;

}



void dfs1(int x,int fa){

	f[x]=1;

	for(int i=h[x];i;i=e[i].n){

		int y=e[i].v;

		if(y==fa) continue;

		dfs1(y,x);

		sz[x]+=sz[y];

		f[x]=f[x]*f[y]%mod*C(sz[x],sz[y])%mod;

	}

	sz[x]++;

}



void dfs2(int x,int fa){

	for(int i=h[x];i;i=e[i].n){

		int y=e[i].v;

		if(y==fa) continue;

		g[y]=f[y]*g[x]%mod*fpow(f[y]*C(n-1,sz[y])%mod,mod-2)%mod*C(n-1,n-sz[y])%mod;

		dfs2(y,x);

	}

}



signed main(){

	read(n);

	for(int i=1,x,y;i<n;i++){

		read(x);read(y);

		add(x,y);add(y,x);

	}

	fac[0]=1;

	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;

	inv[n]=fpow(fac[n],mod-2);

	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

	dfs1(1,0);

	g[1]=f[1];

	dfs2(1,0);

	for(int i=1;i<=n;i++) write(g[i]),puts("");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e3+5,inf=0x3f3f3f3f;

char s[N][N];

int a,b,n=100;

int main()

{

	cin>>a>>b;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

		{

			if(j>50)

				s[i][j]='#';

			else

				s[i][j]='.';

		}

	for(int i=1;i<=n;i+=2)

		for(int j=1;j<50;j++)

		{

			if((i+j)%2&&b!=1)

				s[i][j]='#',b--;

		}

	for(int i=1;i<=n;i+=2)

		for(int j=51;j<=100;j++)

		{

			if((i+j)%2&&a!=1)

				s[i][j]='.',a--;

		}

	puts("100 100");

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)

			printf("%c",s[i][j]);

		printf("\n");

	}

		

	return 0;

}

// Optimized solution to the same problem (faster):
#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <set>

//#inlcude<stringstream>

#define ll long long

#define MODD 1000000007

using namespace std;

ll arr[1000000]={0};

ll brr[1000000]={0};

int main() {

    //

    ll a , b;cin >>a>>b;

    int flag=1;

    a--,b--;

    cout<<100<<" "<<100<<endl;

    for(int i=1;i<=50;i++){

        for(int j=1;j<=100;j++){

           if(i%2==0&&j%2==0&&a){

                a--;

                cout<<".";

           }

           else cout<<"#";

        }

       cout<<endl;

    }

    for(int i=1;i<=50;i++){

        for(int j=1;j<=100;j++){

            if(i%2==0&&j%2==0&&b){

                b--;

                cout<<"#";

           }

           else cout<<".";

        }

        cout<<endl;



    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

const int mod = 1000000007;



int main() {

  int a, b;

  cin >> a >> b;

  int h = 100, w = 100;

  vector<vector<char>> s(101, vector<char>(101));

  rep(i, h / 2) {

    rep(j, w) s[i][j] = '.';

  }

  for(int i = h / 2; i < h; ++i) {

    rep(j, w) s[i][j] = '#';

  }



  --a; --b;

  int cur = 0;

  int height = 0;

  rep(i, b) {

    if(cur >= w) cur = 0, height += 2;

    s[height][cur] = '#';

    cur += 2;

  }

  height = h / 2 + 1;

  cur = 0;

  rep(i, a) {

    if(cur >= w) cur = 0, height += 2;

    s[height][cur] = '.';

    cur += 2;

  }

  cout << h << " " << w << endl;

  rep(i, h) {

    rep(j, w) {

      cout << s[i][j];

    }

    cout << endl;

  }



}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<vector>

#include<string>

#include<algorithm>

#include<utility>

#include<cmath>

#include<climits>

#include<queue>

#include<stack>

#include<numeric>

#include<set>

#include<iomanip>

#include<map>

#include<type_traits>

#include<tuple>

#include<deque>

#include<cassert>

#include<bitset>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

#define chmax(x,y) x=max(x,y)

#define chmin(x,y) x=min(x,y)

const int mod = 1000000007;

const int MAXH = 100;

const int MAXW = 100;



int main() {

  

  int a, b;

  cin >> a >> b;

  vector<string> s(MAXH);

  rep(i, MAXH / 2) {

    s[i] = string(MAXW, '#');

  }

  for (int i = MAXH / 2; i < MAXH; ++i) {

    s[i] = string(MAXW, '.');

  }

  a--; b--;



  int cur = 0;

  rep(i, a) {

    if(cur % 200 == 100) cur += 100;

    s[cur / MAXW][cur % MAXW] = '.';

    cur += 2;

    

  }

  cur = 50 * 100 + 100;

  rep(i, b) {

    if(cur % 200 == 100) cur += 100;

    s[cur / MAXW][cur % MAXW] = '#';

    cur += 2;

    

  }

  cout << MAXH << " " << MAXW << endl;

  rep(i, MAXH) cout << s[i] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

using namespace std;

string S;

char a[27] = {0};

int main()

{

    cin>>S;

    for (int i = 0; i < S.size(); i++)

        a[S[i] - 'a'] = 1;

    for (int i = 0; i < 26; i++)

        if(!a[i])

        {

            printf("%c\n",i+'a');

            return 0;

        }

    cout<<"None"<<endl;

    return 0;

}




// Optimized solution to the same problem (faster):
//q

#include<stdio.h>



int cnt[26]={0}, ok=0;

char s[100005];



int main()

{

	//freopen("in.txt", "r", stdin);

	scanf("%s", s);

	for(int i=0; s[i]; i++) cnt[s[i]-'a']++;

	for(int i=0; i<26; i++)

	{

		if(!cnt[i])

		{

			ok++;

			putchar(i+'a');

			break;

		}

	}

	if(!ok) printf("None");

	puts("");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

#define F first

#define S second

#define ALL(a) begin(a), end(a)

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    string s;

    cin >> s;

    bool vis[26] = {};

    for (char c : s)

        vis[c - 'a'] = 1;

    for (int i = 0; i < 26; ++i)

        if (!vis[i]) {

            cout << (char)('a' + i) << '\n';

            return 0;

        }

    cout << "None\n"; 

}


// Optimized solution to the same problem (faster):
//q

#include<stdio.h>



int cnt[26]={0}, ok=0;

char s[100005];



int main()

{

	//freopen("in.txt", "r", stdin);

	scanf("%s", s);

	for(int i=0; s[i]; i++) cnt[s[i]-'a']++;

	for(int i=0; i<26; i++)

	{

		if(!cnt[i])

		{

			ok++;

			putchar(i+'a');

			break;

		}

	}

	if(!ok) printf("None");

	puts("");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <algorithm>

#include <set>



using namespace std;



int main(){

	string s;

	cin >> s;

	

	set<char> se;

	for(int i = 0; i < s.length(); i++) se.insert(s[i]);

	

	bool flag = false;

	for(int i = 0; i < 26; i++){

		if(se.count(char('a' + i)) == 0){

			flag = true;

			cout << char('a' + i) << endl;

			break;

		

		}

	

	}

	

	if(!flag) cout << "None" << endl;

	

	return 0;

}

/*

+++++ +++++ +++++ +++++

+++++ +++++ ++

>,[[-<->]]



*/


// Optimized solution to the same problem (faster):
//q

#include<stdio.h>



int cnt[26]={0}, ok=0;

char s[100005];



int main()

{

	//freopen("in.txt", "r", stdin);

	scanf("%s", s);

	for(int i=0; s[i]; i++) cnt[s[i]-'a']++;

	for(int i=0; i<26; i++)

	{

		if(!cnt[i])

		{

			ok++;

			putchar(i+'a');

			break;

		}

	}

	if(!ok) printf("None");

	puts("");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <set>

#include <iostream>

using namespace std;

int main() {

	bool have[26];

	string s;

	cin >> s;

	for (int i = 0; i < 26; i++) have[i] = false;

	for (char i : s) have[i - 'a'] = true;

	for (int i = 0; i < 26; i++) if (!have[i]) {

		cout << char('a' + i) << endl;

		return 0;

	}

	cout << "None" << endl;

}


// Optimized solution to the same problem (faster):
//q

#include<stdio.h>



int cnt[26]={0}, ok=0;

char s[100005];



int main()

{

	//freopen("in.txt", "r", stdin);

	scanf("%s", s);

	for(int i=0; s[i]; i++) cnt[s[i]-'a']++;

	for(int i=0; i<26; i++)

	{

		if(!cnt[i])

		{

			ok++;

			putchar(i+'a');

			break;

		}

	}

	if(!ok) printf("None");

	puts("");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

using namespace std;



string s;

int a[26];



int main()

{

	cin>>s;

	int l=s.length();

	for(int i=0;i<l;i++) a[s[i]-'a']=1;

	for(int i=0;i<26;i++)

		if(a[i]==0) { cout<<(char)(i+'a')<<endl; return 0; }

	cout<<"None"<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

bool b[26];

int main(){

    register char ch;

    while((ch=std::getchar())!='\n') b[ch-'a']=true;

    for(int i=0;i<26;++i) if(!b[i]){std::putchar(i+'a');std::putchar(10);return 0;}

    std::puts("None");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main(){

  string s;cin>>s;

  char a='a';

  for(int i=0;i<26;i++){

    if(!count(s.begin(),s.end(),a)){

      cout<<a;

      return 0;

    }

    a++;

  }

  cout<<"None";

}

// Optimized solution to the same problem (faster):


#include<cstdio>

#include<queue>

#include<cstring>

#include<cmath>

using namespace std;

const int B = 300000+10;

const int N = 10000+10;

const int P = 26    +100;

char a[B];



int main()

{

    int num[P];

    while(scanf("%s",a)==1)

    {

        memset(num,0,sizeof num);

        int len=strlen(a);

        for(int i=0;i<len;i++)

        {

            num[a[i]-'a']++;



        }

        int pos=-1;

        for(int i=0;i<26;i++)

        {

            if(num[i]==0)

            {

                pos=i;

                break;

            }

        }



        if(pos==-1)

        {

            printf("None\n");

        }

        else

        {

            printf("%c\n",'a'+pos);

        }



    }

return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#include<bits/stdc++.h>

//#include<tr1/unordered_map>

#include<iostream>

#include<string>

#include<algorithm>

#include<utility>

#include<functional>

#include<vector>



#pragma GCC optimize ("Ofast")

#define ll long long

#define pll pair<long long,long long>

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define F first

#define S second

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

#define Forn(i, n) for(int i=1; i<=int(n); i++)



using namespace std;



/*#include <ext/pb_ds/tree_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> rbtree;*/



string s;



int main()

{

    cin.tie(0);ios_base::sync_with_stdio(false);

    cin >> s;

    sort(s.begin(), s.end());

    for(char c = 'a'; c<='z'; c++)

    {

        if(!binary_search(s.begin(), s.end(), c))

        {

            cout << c << endl;

            return 0;

        }

    }

    cout << "None" << endl;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <string.h>



int cnt[26] = {};

char s[100005];



int main() {

    scanf("%s", s);

    for(int i = 0; s[i]; i++)

        cnt[s[i] - 'a']++;

    for(int i = 0; i < 26; i++) {

        if(!cnt[i]) {

            printf("%c\n", i + 'a');

            return 0;

        }

    }

    puts("None");

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define all(cont) cont.begin(), cont.end()

#define rall(cont) cont.end(), cont.begin()

#define mp make_pair

#define pb push_back

#define fs first

#define sc second

#define fr(i, a, b) for(int i = a ; i < b ; i++)

#define frr(i, a, b) for(int i = a ; i >= b ; i--)

#define tr(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)

#define trr(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)

#define its(x) static_cast< ostringstream & >( ( ostringstream() << dec << x ) ).str() // int to string

#define boost ios_base::sync_with_stdio(false)

#define deb(x) cout << #x" = " << x << '\n'

#define has(cont, x) ((cont).find((x)) != (cont).end())

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



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

typedef vector<int> vi;





int main() {

//    freopen("input.in", "r", stdin);

	int a[5];

	scanf("%d %d %d", a+0, a+1, a+2);

	sort(a, a+3);

//	printf("%d %d %	d\n", a[0], a[1], a[2]);

	bool ok = false;

	while(1) {

		if(a[0]+a[1] == a[2]) ok = true;

//		deb(a[0]);

//		deb(a[1]);

//		deb(a[2]);

		if(!next_permutation(a, a+3)) break;

	}

	puts(ok ? "Yes" : "No");

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>



const int N = 100000;

char a[N];

char b[N];

int main()

{

	int a,b,c;

	scanf("%d%d%d",&a,&b,&c);

	if(a == b+c || b == a+c || c == a+b)

	printf("Yes\n");

	else

	printf("No\n");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

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

struct P{int x,y;P(){}P(int a,int b){x = a , y = b;}};

int operator -(P a, P b){

	return abs(a.x - b.x) + abs(a.y - b.y);

}

int dp[1<<5][5][1000];

#define INF (1<<21)

int main(){	

	int W,H;

	while(cin >> W >> H , W){

		P s , g ;

		vector<P> v[6];

		rep(i,H)rep(j,W){

			char c; cin >> c;

			if(c == 'S') s = P(j,i);

			else if(c == 'G') g = P(j,i);

			else if(c != '.') v[c-'1'].push_back(P(j,i));

		}

		rep(i,1<<5)rep(k,5)rep(j,1000)dp[i][k][j] = INF;

		rep(i,5)rep(j,v[(i+1)%5].size()){

			dp[(1<<i) | (1<<((i+1)%5))][(i+1)%5][j] = s - v[(i+1)%5][j];

		}

		rep(bit,(1<<5)-1)rep(x,5){

			int y = (x+1)%5;

			rep(i,v[x].size()){

				if( dp[bit][x][i] == INF ) continue;

				rep(j,v[y].size()){

					dp[bit|(1<<y)][y][j] = min( dp[bit|(1<<y)][y][j] , dp[bit][x][i] + (v[x][i]-v[y][j]) );

				}

			}

		}

		int ans = INF , cho = -1;

		rep(i,5) rep( j , v[i].size() ){

			int cst = dp[(1<<5)-1][i][j] + (g - v[i][j]);

			int w = (i+1)%5;

			if(ans >= cst){

				if(ans == cst){

					cho = min(cho, w );

				}else{

					cho = w;

					ans = cst;

				}

			}

		}

		if(ans == INF) cout << "NA" << endl;

		else cout << cho+1 << " " << ans << endl;

		

		

	}

	

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#include <cstring>

#include <cstdio>

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

using namespace std;





int W,H;

int sx,sy,gx,gy;

vector< pair<int,int> > e[5];



int memo[1000][1000][5] = {};



int dfs(int x,int y,int c,int r){

	if( memo[x][y][c] != -1 ) return memo[x][y][c];

	if( r == 0 ) return abs(gx-x)+abs(gy-y);

	int g = (c+1)%5;

	int ans = 1e8;

	for(int i = 0 ; i < e[g].size() ; i++){

		ans = min( ans , dfs(e[g][i].first,e[g][i].second,g,r-1) + abs(e[g][i].first-x)+abs(e[g][i].second-y) );

	}

	return memo[x][y][c] = ans;

}

int main(){

	ios_base::sync_with_stdio(false);

	while(cin >> W >> H && W){

		rep(i,5)e[i].clear();

		sx = sy = gx = gy = 1e7;

		

		vector< pair<int,int> > list;

		rep(i,H){

			rep(j,W){

				char c;

				cin >> c;

				if( c == 'S' ) sx = j , sy = i;

				else if( c == 'G' ) gx = j , gy = i;

				else if( c != '.' ) e[c-'1'].push_back(make_pair(j,i)), list.push_back(make_pair(j,i));

			}

		}

		list.push_back(make_pair(sx,sy));

		list.push_back(make_pair(gx,gy));

		int F = !e[0].size() + !e[1].size() + !e[2].size() + !e[3].size() + !e[4].size();

		if( F >= 2){

			cout << "NA" << endl;

			continue;

		}

		pair<int,int> ans = make_pair(1e8,1e8);

		rep(i,5){

			rep(j,list.size()) rep(k,5) memo[list[j].first][list[j].second][k] = -1;

			ans = min(ans,make_pair(dfs(sx,sy,i,4),i));

		}

		if( 1e6 > ans.first ){

			cout << ans.second+1 << " " << ans.first << endl;

		}else{

			cout << "NA" << endl;

		}

	}

}

// Fastest known solution for this problem: