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

#include <cstring>

using namespace std;



#define MAX_N 100001



typedef unsigned long long ull;



bool M[MAX_N];   // マークされてるかどうか

int P[MAX_N];   // 親



int main() {

    int N, Q;

    while (cin >> N >> Q, N != 0 && Q != 0) {

        memset(M, 0, sizeof(M));

        M[1] = true;

        memset(P, 0, sizeof(P));

        for (int i = 2; i < N+1; i++) {

            int p; cin >> p;

            P[i] = p;

        }



//        for (int i = 1; i <= N; i++) cout << P[i] << ' ';

//        cout << endl;

//        for (int i = 1; i <= N; i++) cout << M[i] << ' ';

//        cout << endl;



        ull sum = 0;

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

            char q; int v;

            cin >> q >> v;

            if (q == 'Q') {

                while (!M[v]) {

                    v = P[v];

                }

                sum += v;

            } else {

                M[v] = true;

            }

        }

//        for (int i = 1; i <= N; i++) cout << M[i] << ' ';

//        cout << endl;

        cout << sum << endl;

    }

    return 0;

}

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

#include <cassert>

#include <cstring>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <iostream>

#include <vector>

#include <map>

#include <iterator>

#include <queue>

#include <utility>

#include <stack>



using namespace std;



typedef long long Long;



#define MN 100000

#define MQ 100000

int N, Q;

int parent[MN + 1];

bool marked[MN + 1];

pair<int, int> queries[MQ];



int root(int x) {

    if (marked[x]) return x;

    return parent[x] = root(parent[x]);

}

void merge(int x, int y) {

    x = root(x); y = root(y);

    if (x == y) return;

    parent[x] = y;

}



bool input() {

    scanf("%d %d", &N, &Q);

    if (N == 0 && Q == 0) return false;

    for (int i = 2; i <= N; i++) {

        int p;

        scanf("%d", &p);

        parent[i] = p;

    }

    memset(marked, false, N + 1);

    marked[1] = true;

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

        char t; int n;

        scanf("%*[ \t\r\n]%c %d", &t, &n);

        if (t == 'M') {

            if (marked[n]) {

                queries[i] = make_pair('X', 0);

                continue;

            }

            marked[n] = true;

        }

        queries[i] = make_pair(t, n);

    }

    return true;

}



void solve() {

    Long ans = 0;

    for (int q = Q - 1; q >= 0; q--) {

        pair<int, int> query = queries[q];

        if (query.first == 'Q') {

            ans += root(query.second);

        } else if (query.first == 'M') {

            marked[query.second] = false;

        }

    }

    printf("%lld\n", ans);

}



int main() {

    while (input()) {

        solve();

    }

    return 0;

}

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

using namespace std;

const int N = 1414 ;

int n , m , answer = 0 , matrix [N][N] , dp [N][N] ;

int isval (int i , int j , int len )

{

	if ( len == 0 )

	{

		return 1 ;

	}

	int z = len ;

	for (int q = 1 ; q <= len ; q ++)

	{

		if ( matrix [i - q ][j] == 1 || matrix[i][j - q ] == 1)

		{

			z = q - 1 ; 

			break ;

		}

	}

 	return z + 1;

}

int main ()

{

	ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> m ; 

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

	{

		for (int j = 0 ; j < m ; j ++)

		{

			cin >> matrix[j][i] ;

			if ( matrix[j][i] == 0 )

			{

				dp[j][i] = 1 ;

				answer = 1 ;

			}

		}

	}

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

	{

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

		{

			if ( matrix[j][i] == 0)

			{

				dp[j][i] = isval ( j , i , dp[j - 1][i - 1 ] ) ;

			}

			answer = max ( answer , dp[j][i] ) ;

		}

	}

	answer *= answer ;

	cout << answer << endl ; 

	/*cerr << "*********************************" << endl ;

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

	{

		for (int j = 0 ; j < m ; j ++)

		{

			cerr << dp[j][i] << " " ;

		}

		cerr << endl ;

	}*/

	return  0 ; 

}

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

#include <algorithm>



int h, w;

int a[1401][1401];

int dp[1401][1401];



int main()

{

	scanf("%d%d", &h, &w);

	int res = 0;

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

		for (int j = 0; j < w; j++)

		{

			scanf("%d", &a[i][j]);

			dp[i][j] = !a[i][j];

			res |= dp[i][j];

		}



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

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

		{

			if (a[i][j] == 0)

				dp[i][j] = std::min(std::min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;

			res = std::max(res, dp[i][j]);

		}



	printf("%d\n", res * res);



	return 0;

}




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

using namespace std;



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

#define SZ(a) int((a).size())

#define SORT(c) sort(ALL((c)))

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)

#define debug(x) cerr << #x << ": " << x << endl



using LL = long long; template<class T> using V = vector<T>;





int main() {

	cin.tie(0);

	ios_base::sync_with_stdio(false);



	int H, W;

	cin >> H >> W;

	V<V<int>>a(H + 1, V<int>(W + 1));

	FOR(i, 0, H) {

		FOR(j, 0, W) {

			cin >> a[i + 1][j + 1];

		}

	}

	LL ans = 0;

	V<V<int>>dp(H + 1, V<int>(W + 1, 0));

	FOR(i, 1, H + 1) {

		FOR(j, 1, W + 1) {

			if (a[i][j] == 1)dp[i][j] = 0;

			else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;

		}

	}



	FOR(i, 1, H + 1) {

		FOR(j, 1, W + 1) {

			ans = max(ans, (LL)dp[i][j]);

		}

	}

	cout << ans * ans << endl;



	return 0;

}


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

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 2e3+10;

int dp[maxn][maxn],a[maxn][maxn];



int main(){

    int n,m,ans=0;

    scanf("%d%d",&n,&m);

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

        for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

    }

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

        for(int j=m;j>=1;j--){

            if(a[i][j]) dp[i][j]=0;

            else dp[i][j]=min(min(dp[i-1][j],dp[i][j+1]),dp[i-1][j+1])+1;

            ans=max(ans,dp[i][j]);

//            printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);

        }

    }

    printf("%d\n",ans*ans);

    return 0;

}




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

#include <algorithm>

using namespace std;

int dp[1401][1401], G[1401][1401];



int main()

{

	int H, W;

	cin >> H >> W;

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

		for (int j = 0; j < W; ++j)

			cin >> G[i][j];

	int	maxWidth = 0;

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

		for (int j = 0; j < W; ++j)

		{

			dp[i][j] = (G[i][j] == 1 ? 0 : 1);

			if (maxWidth < dp[i][j])

				maxWidth = dp[i][j];

		}

		

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

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

		{

			if (G[i][j])

				dp[i][j] = 0;

			else

			{

				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;

				maxWidth = max(maxWidth, dp[i][j]);

			}

		}

	cout << maxWidth * maxWidth << endl;

	return 0;

}


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

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 2e3+10;

int dp[maxn][maxn],a[maxn][maxn];



int main(){

    int n,m,ans=0;

    scanf("%d%d",&n,&m);

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

        for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

    }

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

        for(int j=m;j>=1;j--){

            if(a[i][j]) dp[i][j]=0;

            else dp[i][j]=min(min(dp[i-1][j],dp[i][j+1]),dp[i-1][j+1])+1;

            ans=max(ans,dp[i][j]);

//            printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);

        }

    }

    printf("%d\n",ans*ans);

    return 0;

}




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

#include<algorithm>

using namespace std;



const int MAX = 1400;



int minSquare(int tile[MAX][MAX], int x, int y) {

	if (tile[y][x] == 1) {

		tile[y][x] = 0;

		return 0;

	}

	return min(tile[y - 1][x - 1], min(tile[y - 1][x], tile[y][x - 1])) + 1;

}



int main() {

	int H, W;

	int tile[MAX][MAX];

	int ans = 0;





	cin >> H >> W;

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

		for (int j = 0; j < W; j++) {

			cin >> tile[i][j];

		}

	}



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

		if (tile[i][0] == 1)tile[i][0] = 0;

		else {

			tile[i][0] = 1;

			ans = 1;

		}

	}

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

		if (tile[0][i] == 1)tile[0][i] = 0;

		else {

			tile[0][i] = 1;

			ans = 1;

		}

	}



	int x = 1;

	int y = 1;

	int n = min(H, W);

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

		for (int j = y; j < H; j++) {

			tile[j][x] = minSquare(tile, x, j);

			ans = max(tile[j][x], ans);

		}

		for (int j = x + 1; j < W; j++) {

			tile[y][j] = minSquare(tile, j, y);

			ans = max(tile[y][j], ans);

		}

		x++;

		y++;

	}



	cout << ans * ans << endl;

	return 0;

}

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

#include<algorithm>

using namespace std;



const int MAX = 1400;



int main() {

	int H, W;

	int tile[MAX][MAX];

	int ans = 0;



	scanf("%d%d", &H, &W);

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

		for (int j = 0; j < W; j++) {

			scanf("%d", &tile[i][j]);

		}

	}



	for (int y = 0; y < H; y++) {

		for (int x = 0; x < W; x++) {

			if (tile[y][x] == 1) tile[y][x] = 0;

			else if (x < 1 || y < 1) tile[y][x] = 1;

			else tile[y][x] = min(tile[y - 1][x - 1], min(tile[y - 1][x], tile[y][x - 1])) + 1;

			ans = max(tile[y][x], ans);

		}

	}



	printf("%d\n", ans * ans);

	return 0;

}

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

using namespace std;

void func(int,int,double,int);

int p,q,a,n,cnt;

double k;

 

int main(){

  while(1){

    cin>>p>>q>>a>>n;

    if(!p&&!q&&!a&&!n) break;

    k=1.0*p/q;

    cnt=0;

    func(0,1,0,1);

    cout<<cnt<<endl;

  }

  return 0;

}

 

void func(int x,int w,double y,int I){

  if(-0.00000001<=k-y&&k-y<=0.00000001) cnt++;

  if(x==n) return ;

  for(int i=I;w*i<=a;i++){

    if(y+1.0/i>k+0.1) continue;

    func(x+1,w*i,1.0/i+y,i);

  }

}

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

using namespace std;

void func(int,int,double,int);

int p,q,a,n,cnt;

double k;

 

int main(){

  while(1){

    cin>>p>>q>>a>>n;

    if(!p&&!q&&!a&&!n) break;

    k=1.0*p/q;

    cnt=0;

    func(0,1,0,1);

    cout<<cnt<<endl;

  }

  return 0;

}

 

void func(int x,int w,double y,int I){

  if(-0.00000001<=k-y&&k-y<=0.00000001) cnt++;

  if(x==n) return ;

  for(int i=I;w*i<=a;i++){

    if(y+1.0/i>k+0.0000001) continue;

    func(x+1,w*i,1.0/i+y,i);

  }

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int gcd(int x,int y){

    if(y==0) return x;

    return gcd(y,x%y);

}



int dfs(int denom,int numer,int prev,int product,int num){

    int res=0;

    if((double)p/q-eps<=(double)numer/denom  and (double)numer/denom<=(double)p/q+eps) ++res;

    if(num==0) return res;



    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if((double)tmp2/tmp1<(double)p/q) return 0;

    }



    if((double)numer/denom>(double)p/q) return 0;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int dfs(int denom,int numer,int prev,int product,int num){

    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if(tmp2*q<p*tmp1) return 0;

    }

    if(numer*q>p*denom) return 0;



    int res=0;

    if(numer*q==p*denom) ++res;

    if(num==0) return res;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int gcd(int x,int y){

    if(y==0) return x;

    return gcd(y,x%y);

}



int dfs(int denom,int numer,int prev,int product,int num){

    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if((double)tmp2/tmp1+eps<(double)p/q) return 0;

    }

    if((double)numer/denom-eps>(double)p/q) return 0;



    int res=0;

    if((double)p/q-eps<=(double)numer/denom  and (double)numer/denom<=(double)p/q+eps) ++res;

    if(num==0) return res;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int dfs(int denom,int numer,int prev,int product,int num){

    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if(tmp2*q<p*tmp1) return 0;

    }

    if(numer*q>p*denom) return 0;



    int res=0;

    if(numer*q==p*denom) ++res;

    if(num==0) return res;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int dfs(int denom,int numer,int prev,int product,int num){

    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if((double)tmp2/tmp1+eps<(double)p/q) return 0;

    }

    if((double)numer/denom-eps>(double)p/q) return 0;



    int res=0;

    if((double)p/q-eps<=(double)numer/denom  and (double)numer/denom<=(double)p/q+eps) ++res;

    if(num==0) return res;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define debug(x) #x << "=" << (x)



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int inf=1<<30;

const long long int infll=1LL<<58;

const double eps=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



int p,q,a,n;



int dfs(int denom,int numer,int prev,int product,int num){

    {

        int tmp1=denom*prev,tmp2=numer*prev+denom*num;

        if(tmp2*q<p*tmp1) return 0;

    }

    if(numer*q>p*denom) return 0;



    int res=0;

    if(numer*q==p*denom) ++res;

    if(num==0) return res;



    int x=prev;

    while(true){

        if(product*x>a) break;

        res+=dfs(denom*x,numer*x+denom,x,product*x,num-1);

        ++x;

    }

    return res;

}



void solve(){

    while(cin >> p >> q >> a >> n){

        if(p==0 and q==0 and a==0 and n==0) break;

        cout << dfs(1,0,1,1,n) << endl;

    }

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;

int N, M, L, R, s[50003], t[50003], e[50003], c[10003]; long long d[10003];

int main() {

	cin >> N >> M;

	while(true) {

		cin >> s[R] >> t[R] >> e[R]; s[R]--, t[R]--;

		if (!e[R]) break; R++;

	}

	cin >> L;

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

		for (int j = 0; j < M; j++) cin >> c[j];

		for (int j = 0; j < N; j++) d[j] = 0;

		for (int j = 0; j < R; j++) d[s[j]] += c[t[j]] * e[j];

		for (int j = 0; j < N; j++) cout << (j ? " " : "") << d[j];

		cout << endl;

	}

}

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

int N, M, L, R, s[50003], t[50003], e[50003], c[10003]; long long d[10003];

int main() {

	scanf("%d%d", &N, &M);

	while(true) {

		scanf("%d%d%d", s + R, t + R, e + R); s[R]--, t[R]--;

		if (!e[R]) break; R++;

	}

	scanf("%d", &L);

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

		for (int j = 0; j < M; j++) scanf("%d", &c[j]);

		for (int j = 0; j < N; j++) d[j] = 0;

		for (int j = 0; j < R; j++) d[s[j]] += c[t[j]] * e[j];

		for (int j = 0; j < N; j++) printf(j ? " %d" : "%d", d[j]);

		printf("\n");

	}

}

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

#define mk make_pair

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

using namespace std;

string s[500];

int h,w,sum=0;

vector<int>x,y;

void del(int t1,int t2){

  vector<pair<char,pair<int,int> > >p;

  for(int i=t1;i<h;i++)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t1;i>=0;i--)if(s[i][t2]!='.'){

    p.push_back(mk(s[i][t2],mk(i,t2)));

    break;

  }

  for(int i=t2;i<w;i++)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

  for(int i=t2;i>=0;i--)if(s[t1][i]!='.'){

    p.push_back(mk(s[t1][i],mk(t1,i)));

    break;

  }

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

  if(p.size()>=2){

    r(i,p.size()-1){

      if(p[i].first==p[i+1].first){

        sum++;

        s[p[i].second.first][p[i].second.second]='.';

        s[p[i+1].second.first][p[i+1].second.second]='.';

      }

    }

  }

}

int main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];

  r(i,h)r(j,w)if(s[i][j]!='.'){

      y.push_back(i),x.push_back(j);

      if(i+1<h)y.push_back(i+1);

      if(j+1<w)x.push_back(j+1);

    }

  r(k,26)r(i,y.size())r(j,x.size())

    if(s[y[i]][x[j]]=='.')del(y[i],x[j]);

  cout<<sum*2<<endl;

}

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

#define int long long

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

using namespace std;

typedef pair<int,int>P;



int h,w;

string s[600];

int dy[]={0,1,0,-1};

int dx[]={1,0,-1,0};

int sum=0;



bool ng[555][555];



void knock(int Y,int X){

  

  map<char,vector<P> >M;

  r(i,4){

    int y=Y;

    int x=X;



    while(!isalpha(s[y][x])){

      y+=dy[i];

      x+=dx[i];

      if(y<0||x<0||y>=h||x>=w)break;

    }



    if(y<0||x<0||y>=h||x>=w)continue;

    M[s[y][x]].push_back(P(y,x));

  }



  int TX=0;

  for(auto &e:M){

    if(e.second.size()!=2)continue;

    sum+=2;

    s[e.second[0].first][e.second[0].second] = '.';

    s[e.second[1].first][e.second[1].second] = '.';

    TX++;

  }



  if(!M.size())ng[Y][X]=1;



}



signed main(){

  cin>>h>>w;

  r(i,h)cin>>s[i];



  r(tim,26)r(i,h)r(j,w)if(!isalpha(s[i][j])&&!ng[i][j]){

    knock(i,j);

  }



  cout<<sum<<endl;

}


// Fastest known solution for this problem: