stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main(){

	int n;

	cin>>n;

	int count=0;

	int k=sqrt(n);

	int maxi=1;

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

		for(int j=2; j<n; j++){

			if(pow(i,j)<=n){

			count=pow(i,j);

			maxi=max(count,maxi);

		//	cout<<i<<" "<<j<<" "<<maxi<<endl;

		}

	}}

	cout<<maxi;

}

// Faster C++ solution for the same problem (measured speedup: 2.17440731669242x):
#include <bits/stdc++.h>

using namespace std;



int main() {

	int n; cin >> n;

	int mx = 1;

	for (int i = 2; i * i <= n; ++i) {

		int s = i;

		while (s * i <= n)

			s *= i;

		mx = max(s, mx);

	}

	cout << mx;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <cmath>



using namespace std;



int main() {

    

    int X;

    cin >> X;

    

    int ans=1;

    

    for(int b=1;b<=1000;b++){

        for(int p=2;p<=10;p++){

            if((pow(b,p)<=X)&&(pow(b,p)>=ans)){

                ans = pow(b,p);

            }

        }

    }

    

    cout << ans << endl;

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2863753529594317x):
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <cmath>

#include <set>

#include <sstream>

#include <bitset>



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

#define REP(i,n)  FOR(i,0,n)



typedef long long ll;



using namespace std;



int main() {

    

    int x;

    cin >> x;

    int ans=1;

    FOR(b, 2, 32){

        FOR(p, 2, 10){

            if((pow(b, p)>ans)&&(pow(b, p)<=x)){

                ans = pow(b, p);

            }

        }

    }

    

    cout << ans << endl;

    

    

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF=1001001001;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){

  vector<pair<int64_t,int64_t>>p;

  for(int64_t i=2;i*i<=x;i++){

    int cnt=0;

    if(x%i==0){

    while(x%i==0){cnt++;x/=i;}

    p.push_back(make_pair(i,cnt));

    }

  }

  if(x!=1){p.push_back(make_pair(x,1));}

  return p; 

}



int main() {

  int X;

  cin>>X;

  int ans=1;

  for(int b=1;b<=X;b++){

    for(int p=2;p<=X;p++){

      int s=pow(b,p);

      if(s<=X){chmax(ans,s);}

    }

  }

  cout<<ans<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.069805229346344x):
#include <bits/stdc++.h>

using namespace std;

#include <math.h>

#include <iomanip>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



const int mod=1e9+7;

const int INF=1001001001;



int main() {

  int x;

  cin>>x;

  int MAX=1;

  for(int i=2;i*i<=x;i++){

    int p=i;

    while(p*i<=x){

      p*=i;

    }

    chmax(MAX,p);

  }

  cout<<MAX<<endl;

  return 0;  

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std ;



int main () {

  int  N ;

  cin >> N ;

  int ans = 0 ;

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

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

      int pre = pow(i,j) ;

      if( pre <= N ) ans = max(ans,pre) ;

    }

  }

  cout << ans << endl ;

}

// Faster C++ solution for the same problem (measured speedup: 2.120664625314034x):
#include<bits/stdc++.h>

using namespace std ;



int main () {

  int  N ;

  cin >> N ;

  int ans = 0 ;

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

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

      int pre = pow(i,j) ;

      if( pre <= N ) ans = max(ans,pre) ;

      else break ;

    }

  }

  cout << ans << endl ;

}
// Slower C++ solution:
/** author: __nishad__ **/



#include<bits/stdc++.h>

using namespace std;





typedef long long ll ;

typedef vector<ll> vll ;



#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

#define precision(k) cout<<setprecision(k)<<fixed;

#define loop(i,a) for(int i=0; i<a;i++)

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

#define minv(v) *min_element(all(v))

#define maxv(v) *max_element(all(v))

#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())

#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())

#define pb push_back

#define pi 3.14159265358979323

#define endl "\n"



int main()

{

    IOS;



    ll x, i, j;

    vll v;

    cin>>x;



    if(x == 1)

        cout<<"1";

    else{

        for(i=1; i<=x; i++){

            for(j=2; j<=x; j++){

                if(pow(i, j) == int(pow(i, j)) && (pow(i, j) <= x)){

                    v.pb(pow(i, j));

                }

            }

        }

        sort(all(v));



        cout<<v[v.size()-1];

    }







}




// Faster C++ solution for the same problem (measured speedup: 1.3136738265359367x):
/** author: __nishad__ **/



#include<bits/stdc++.h>

using namespace std;





typedef long long ll ;

typedef vector<ll> vll ;



#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

#define precision(k) cout<<setprecision(k)<<fixed;

#define loop(i,a) for(int i=0; i<a;i++)

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

#define minv(v) *min_element(all(v))

#define maxv(v) *max_element(all(v))

#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())

#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())

#define pb push_back

#define pi 3.14159265358979323

#define endl "\n"



int main()

{

    IOS;



    ll x, i, j, p;

    vll v;

    cin>>x;



    if(x == 1)

        cout<<"1";

    else{

        for(i=1; i<=x; i++){

            for(j=2; j<=x; j++){

                p = pow(i, j);

                if(p == int(p) && (p <= x)){

                    v.pb(p);

                }

            }

        }

        sort(all(v));



        cout<<v[v.size()-1];

    }







}
// Slower C++ solution:
#define rep(i, n) for (int i = 0; i < (n); i++)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int MOD = 1000000007;



int main() {

    int X;

    cin >> X;

    int maxValue = 1;

    for (int i = 1; i <= X; i++) {  // O(N^2) -> 1000 * 1000 = 10^6

        for (int j = 2; j <= X; j++) {

            if (pow(i, j) <= X) {

                maxValue = max(maxValue, (int)pow(i, j));

            }

        }

    }



    cout << maxValue << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.1650001812820467x):
#define rep(i, n) for (int i = 0; i < (n); i++)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int MOD = 1000000007;



int main() {

    int X;

    cin >> X;

    int maxValue = 1;

    vector<bool> expo(X + 1);



    expo[1] = true;

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

        int tmp = i * i;

        while (tmp <= X) {

            expo[tmp] = true;

            tmp *= i;

        }

    }



    for (int i = X; 1 <= i; i--) {

        if (expo[i]){

            cout << i << endl;

            break;

        }

    }



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int main(){

  int X;

  cin >> X;

  double ans=1;

  for(int i=X;i>0;--i){

    for(int j=1;j<=sqrt(X);++j){

      for(int k=2;k<=10;++k){

        if(pow(j,k)<=X) ans=max(ans,pow(j,k));

      }

    }

  }

  cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.5137204629430134x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<long long,long long> pll;

#define ep emplace_back

#define pb push_back

#define mp make_pair

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

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

#define revall(v) v.rbegin(), v.rend()

constexpr int mod=1000000007;

constexpr int mod1=998244353;

vector<int> dx={0,1,0,-1},dy={-1,0,1,0};

bool inside(int y,int x,int h,int w){ if(y<h && y>=0 && x<w && x>=0) return true; return false; }

template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true; } return false; }













int main(){

	cin.tie(0);

	ios::sync_with_stdio(false);

	int n;cin >> n;

	int ans = 1;

	for(int i = 2; i * i <= n; i++){

		int t = i;

		for(int j = 2; j < n; j++){

			t *= i;

			if(t > n) break;

			ans = max(ans, t);

		}

	}

	cout << ans << endl;

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<algorithm>

#include<cctype>

#include<utility>

#include<string>

#include<cmath>



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

#define LLREP(n) for(long long int  i = 0;i < n;i++)

typedef long long int ll;

using namespace std;

#define MAX_A 100005



int main(){



    int x;

    cin >> x;

    int ans = 1;

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

        for(int j = 2;j <= x;j++){

            if(pow(i,j)<= x){

                ans = max(ans,(int)pow(i,j));

            }

            

        }

        //cout << ans << endl;

    }

    cout << ans << endl;



   

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.1859467286077017x):
#include<iostream>

#include<vector>

#include<algorithm>

#include<cmath>

using namespace std;





int main() {



	int n;

	cin >> n;



	int ans = 1;



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



		int num = i;

		if (i*i > n)

		{

			break;

		}

		while (num * i <= n) {

			num *= i;

		}

		ans = max(ans, num);

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



int mypow(int n, int p) {

    if (p == 0) return 1;

    else if (p & 1) {

        return n * mypow(n, p - 1);

    } else {

        int half = mypow(n, p >> 1);

        return half * half;

    }

}



int main() {

    int x;

    cin >> x;

    int ans = 1;

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

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

            int tmp = mypow(j, i);

            if (tmp <= x) ans = max(tmp, ans);

        }

    }

    cout << ans << endl;

    return 0;

}



static int speedUp = []() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    return 0;

}();

// Faster C++ solution for the same problem (measured speedup: 1.8740693650177278x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



int mypow(int n, int p) {

    if (p == 0) return 1;

    else if (p & 1) {

        return n * mypow(n, p - 1);

    } else {

        int half = mypow(n, p >> 1);

        return half * half;

    }

}



int main() {

    int x;

    cin >> x;

    int ans = 1;

    for (int j = 2; j <= sqrt(x); ++j) {

        int tmp = j;

        int cnt = 0;

        while (tmp < x) {

            tmp *= j;

            ++cnt;

        }

        if (tmp == x) ++cnt;

        else tmp /= j;

        if (cnt >= 2)

            ans = max(tmp, ans);

    }

    cout << ans << endl;

    return 0;

}



static int speedUp = []() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    return 0;

}();
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

bool isPrime(int n)

{

	if (n < 2)return false;

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

	{

		if (n % i == 0)return false;

	}

}

int gcd(int a, int b)

{

	for (int i = min(a, b); i >= 2; i--)

	{

		if (a % i == 0 && b % i == 0) return i;

	}

	return 1;

}

int main()

{

	int X;

	cin >> X;

	int ans = 1;

	for (int b = X; b > 1; b--)

	{

		for (int p = 2; p <= X; p++)

		{

			int t = pow(b, p);

			if (t <= X)

			{

				ans = max(t, ans);

			}

		}

	}

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.228914495951608x):
#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

bool isPrime(int n)

{

	if (n < 2)return false;

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

	{

		if (n % i == 0)return false;

	}

}

int gcd(int a, int b)

{

	for (int i = min(a, b); i >= 2; i--)

	{

		if (a % i == 0 && b % i == 0) return i;

	}

	return 1;

}

int main()

{

	int X;

	cin >> X;

	int ans = 1;

	for (int b = X; b > 1; b--)

	{

		for (int p = 2; p <= X; p++)

		{

			int t = pow(b, p);

			if (t <= X)

			{

				ans = max(t, ans);

			}

			else {

				break;

			}

		}

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	int a[3][3],x,i;

	cin>>a[0][0]>>a[0][1]>>a[1][1];

	x=a[1][1]*3;

	a[0][2]=x-a[0][0]-a[0][1];

	a[2][1]=x-a[0][1]-a[1][1];

	a[2][2]=x-a[0][0]-a[1][1];

	a[2][0]=x-a[1][1]-a[0][2];

	a[1][0]=x-a[0][0]-a[2][0];

	a[1][2]=x-a[0][2]-a[2][2];

	for(i=0;i<3;i++){

		cout<<a[i][0]<<" "<<a[i][1]<<" "<<a[i][2]<<endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.208378333448627x):
#include<stdio.h>

int a,b,c;

int main()

{

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

	printf("%d %d %d\n",a,b,3*c-a-b);

	printf("%d %d %d\n",(c<<2)-(a<<1)-b,c,(a<<1)+b-(c<<1));

	printf("%d %d %d\n",a+b-c,(c<<1)-b,(c<<1)-a);

	return 0 ;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

        int A,B,C;

        cin>>A>>B>>C;

        cout<<A<<' '<<B<<' '<<C*3-A-B<<endl<<4*C-2*A-B<<' '<<C<<' '<<2*A+B-2*C<<endl<<A+B-C<<' '<<C*2-B<<' '<<C*2-A;

}


// Faster C++ solution for the same problem (measured speedup: 5.212491889388908x):
#include<stdio.h>

int a,b,c;

int main()

{

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

	printf("%d %d %d\n",a,b,3*c-a-b);

	printf("%d %d %d\n",(c<<2)-(a<<1)-b,c,(a<<1)+b-(c<<1));

	printf("%d %d %d\n",a+b-c,(c<<1)-b,(c<<1)-a);

	return 0 ;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int main(){



  int a,b,c,d,e,f,g,h,i;

  

  cin>>a>>b>>e;





  for(int s=-(1e6);s<=(1e6);s++){



    h=s-(b+e);



    c=s-(a+b);



    i=s-(a+e);



    f=s-(c+i);



    d=s-(e+f);



    g=s-(c+e);



    if(a+b+c==s&&d+e+f==s&&g+h+i==s&&a+d+g==s&&b+e+h==s&&c+f+i==s&&a+e+i==s&&c+e+g==s){



      cout<<a<<' '<<b<<' '<<c<<endl;

      

      cout<<d<<' '<<e<<' '<<f<<endl;

      

      cout<<g<<' '<<h<<' '<<i<<endl;

      

      return 0;

    }

    

  }

  

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.2295133263345566x):
#include<bits/stdc++.h>

using namespace std;



int main(){



  int a,b,c,d,e,f,g,h,i;

  

  cin>>a>>b>>e;





  for(int s=-300;s<=300;s++){



    h=s-(b+e);



    c=s-(a+b);



    i=s-(a+e);



    f=s-(c+i);



    d=s-(e+f);



    g=s-(c+e);



    if(a+b+c==s&&d+e+f==s&&g+h+i==s&&a+d+g==s&&b+e+h==s&&c+f+i==s&&a+e+i==s&&c+e+g==s){



      cout<<a<<' '<<b<<' '<<c<<endl;

      

      cout<<d<<' '<<e<<' '<<f<<endl;

      

      cout<<g<<' '<<h<<' '<<i<<endl;

      

      return 0;

    }

    

  }

  

  return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#define MIN(A,B) ((A)<=(B)?(A):(B))

#define MAX(A,B) ((A)>=(B)?(A):(B))

int X,Y,Z,V[4],E[51],A[51];

double dp[51][5001];

int main() {

	while(scanf("%d %d %d",&X,&Y,&Z),X) {

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

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

		}

		memset(E,0,sizeof(E));

		memset(A,0,sizeof(A));

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

			int n;

			scanf("%d",&n);

			scanf("%d %d",&E[n],&A[n]);

		}

		memset(dp,0,sizeof(dp));

		dp[0][0]=1;

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

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

				for(int k=0;k<X;k++) {

					int next=MIN(Y,i+V[k]),money=j;

					if(E[next]==2) money+=A[next];

					if(E[next]==3) money=MAX(0,money-A[next]);

					if(E[next]==1) next=MIN(Y,next+A[next]);

					dp[next][money]+=dp[i][j]/X;

				}

			}

		}

		double sum=0;

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

			sum+=i*dp[Y][i];

		}

		printf("%d\n",(int)sum);

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.103214758905891x):
#include <cstdio>

#include <cstring>

#define MIN(A,B) ((A)<=(B)?(A):(B))

#define MAX(A,B) ((A)>=(B)?(A):(B))

int X,Y,Z,V[4],E[51],A[51];

double dp[51][5001];

int main() {

	while(scanf("%d %d %d",&X,&Y,&Z),X) {

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

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

		}

		memset(E,0,sizeof(E));

		memset(A,0,sizeof(A));

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

			int n;

			scanf("%d",&n);

			scanf("%d %d",&E[n],&A[n]);

		}

		memset(dp,0,sizeof(dp));

		dp[0][0]=1;

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

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

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

				for(int k=0;k<X;k++) {

					int next=MIN(Y,i+V[k]),money=j;

					if(E[next]==2) money+=A[next];

					if(E[next]==3) money=MAX(0,money-A[next]);

					if(E[next]==1) next=MIN(Y,next+A[next]);

					dp[next][money]+=dp[i][j]/X;

				}

			}

		}

		double sum=0;

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

			sum+=i*dp[Y][i];

		}

		printf("%d\n",(int)sum);

	}

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

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

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z;

  int v[4],e[51],a[51];



  while(cin >> x >> y >> z && (x||y||z)){



    FOR(i,x)cin >> v[i];

    FOR(i,y+1)e[i] = a[i] = 0;

    FOR(i,z){

      int n,m,l;

      cin >> n >> m >> l;

      e[n] = m; a[n] = l;

    }



    FOR(i,y+1)FOR(j,5001)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



    FOR(i,y)FOR(j,5001){

      FOR(k,x){

	if(pb[i][j] == 0.0)continue;

	int next = min(y,i+v[k]),value = j;

	if(e[next] == 1)next = min(y,next+a[next]);

	else if(e[next] == 2)value = j + a[next];

	else if(e[next] == 3)value = max(0,j-a[next]);

	pb[next][value] += pb[i][j]/x;

      }

    }



    double ans = 0.0;

    FOR(i,5001)ans += pb[y][i] * i;

    cout << (int)(ans) << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.654978738564345x):
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z,n,m,l,ub;

  int v[4],e[51],a[51];



  while(cin >> x >> y >> z && (x||y||z)){



    for(int i=0;i<x;i++)cin >> v[i];

    for(int i=0;i<=y;i++)e[i] = a[i] = 0;

    ub = 0;

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

      cin >> n >> m >> l;

      e[n] = m; a[n] = l;

      if(m==2)ub += a[n];

    }



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

      for(int j=0;j<=ub;j++)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



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

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

	if(pb[i][j] == 0.0)continue;

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

	  int next = min(y,i+v[k]),value = j;

	  if(e[next] == 1)next = min(y,next+a[next]);

	  else if(e[next] == 2)value = j + a[next];

	  else if(e[next] == 3)value = max(0,j-a[next]);

	  pb[next][value] += pb[i][j]/x;

	}

      }

    



    double ans = 0.0;

    for(int i=0;i<=ub;i++)ans += pb[y][i] * i;

    cout << (int)(ans) << endl;

  }

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

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

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z;

  int v[4],e[51],a[51];



  while(cin >> x >> y >> z && (x||y||z)){



    FOR(i,x)cin >> v[i];

    FOR(i,y+1)e[i] = a[i] = 0;

    FOR(i,z){

      int n,m,l;

      cin >> n >> m >> l;

      e[n] = m; a[n] = l;

    }



    FOR(i,y+1)FOR(j,5001)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



    FOR(i,y)FOR(j,5001){

      FOR(k,x){

	if(pb[i][j] == 0.0)continue;

	int next = min(y,i+v[k]),value = j;

	if(e[next] == 1)next = min(y,next+a[next]);

	else if(e[next] == 2)value = j + a[next];

	else if(e[next] == 3)value = max(0,j-a[next]);

	pb[next][value] += pb[i][j]/x;

      }

    }



    double ans = 0.0;

    FOR(i,5001)ans += pb[y][i] * i;

    cout << (int)(ans) << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.149511080273983x):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z,n,m,l,ub,i,j,k;

  int v[4],e[51],a[51];



  while(scanf("%d %d %d",&x,&y,&z) && (x||y||z)){



    for(i=0;i<x;i++)scanf("%d",&v[i]);

    for(i=0;i<=y;i++)e[i] = a[i] = 0;

    ub = 0;

    for(i=0;i<z;i++){

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

      e[n] = m; a[n] = l;

      if(m==2)ub += a[n];

    }



    for(i=0;i<=y;i++)

      for(j=0;j<=ub;j++)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



    for(i=0;i<y;i++)

      for(j=0;j<=ub;j++){

	if(pb[i][j] == 0.0)continue;

	for(k=0;k<x;k++){

	  n = min(y,i+v[k]),m = j;

	  if(e[n] == 1)n = min(y,n+a[n]);

	  else if(e[n] == 2)m = j + a[n];

	  else if(e[n] == 3)m = max(0,j-a[n]);

	  pb[n][m] += pb[i][j]/x;

	}

      }

    



    double ans = 0.0;

    for(i=0;i<=ub;i++)ans += pb[y][i] * i;

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

  }

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z,n,m,l,ub;

  int v[4],e[51],a[51];



  while(cin >> x >> y >> z && (x||y||z)){



    for(int i=0;i<x;i++)cin >> v[i];

    for(int i=0;i<=y;i++)e[i] = a[i] = 0;

    ub = 0;

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

      cin >> n >> m >> l;

      e[n] = m; a[n] = l;

      if(m==2)ub += a[n];

    }



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

      for(int j=0;j<=ub;j++)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



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

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

	if(pb[i][j] == 0.0)continue;

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

	  int next = min(y,i+v[k]),value = j;

	  if(e[next] == 1)next = min(y,next+a[next]);

	  else if(e[next] == 2)value = j + a[next];

	  else if(e[next] == 3)value = max(0,j-a[next]);

	  pb[next][value] += pb[i][j]/x;

	}

      }

    



    double ans = 0.0;

    for(int i=0;i<=ub;i++)ans += pb[y][i] * i;

    cout << (int)(ans) << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 3.715764400459029x):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  double pb[100][5001];

  int x,y,z,n,m,l,ub,i,j,k;

  int v[4],e[51],a[51];



  while(scanf("%d %d %d",&x,&y,&z) && (x||y||z)){



    for(i=0;i<x;i++)scanf("%d",&v[i]);

    for(i=0;i<=y;i++)e[i] = a[i] = 0;

    ub = 0;

    for(i=0;i<z;i++){

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

      e[n] = m; a[n] = l;

      if(m==2)ub += a[n];

    }



    for(i=0;i<=y;i++)

      for(j=0;j<=ub;j++)pb[i][j] = 0.0;

    pb[0][0] = 1.0;



    for(i=0;i<y;i++)

      for(j=0;j<=ub;j++){

	if(pb[i][j] == 0.0)continue;

	for(k=0;k<x;k++){

	  n = min(y,i+v[k]),m = j;

	  if(e[n] == 1)n = min(y,n+a[n]);

	  else if(e[n] == 2)m = j + a[n];

	  else if(e[n] == 3)m = max(0,j-a[n]);

	  pb[n][m] += pb[i][j]/x;

	}

      }

    



    double ans = 0.0;

    for(i=0;i<=ub;i++)ans += pb[y][i] * i;

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

  }

}