CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())
    ret = 1
    for b in range(1, N):
        for p in range(2, N//2):
            if b ** p <= N:
                ret = max(ret, b ** p)

    print(ret)


if __name__ == '__main__':
    main()


# Optimized solution
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    if N == 1:
        print((1))
        exit()

    b, p = 2, 1
    ret = []
    while b ** p <= N:
        if b ** (p + 1) <= N:
            p += 1
            ret.append(b ** p)
        else:
            b += 1
            p = 1

    ret.sort(reverse=True)
    print((ret[0]))


if __name__ == '__main__':
    main()
# Original solution
n=int(eval(input()))
max=0
if(n==1):
  print((1))
else:
  for i in range(n):
    for j in range(2,10):
      if(max<=i**j and i**j<=n):
        max=i**j
  print(max)

# Optimized solution
import math
n = int(eval(input()))
j = 2
tmp = 0
Max = 1
for i in range(2,n):
  while(n > tmp):
    tmp = i**j
    j+=1
    if(Max < tmp and n >= tmp):
      Max = tmp
  j = 2
  tmp = 0
print(Max)
# Original solution
def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf
def examB():
    X = I()
    ans = 0
    for i in range(X,0,-1):
        cur = pff(i)
        flag = True
        now = 0
        for j in list(cur.values()):
            if j==1:
                flag = False
            if now==0:
                now = j
            else:
                if now!=j:
                    flag = False
        if flag:
            ans = i
            break
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()

# Optimized solution
def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf
def examB():
    X = I()
    ans = 0
    for i in range(X,0,-1):
        cur = pff(i)
        flag = True
        now = 0
        for j in list(cur.values()):
            if j==1:
                flag = False
            if now==0:
                now = j
            else:
                if now%j!=0 and j%now!=0:
                    flag = False
        if flag:
            ans = i
            break
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()
# Original solution
x = int(eval(input()))
S = set()
S.add(1)
for b in range(2, int(1000**0.5) + 1):
	for p in range(2, 10):
		if b**p > 1000:
			break
		S.add(b**p)
for n in range(x, 0, -1):
	if n in S:
		print(n)
		exit()

# Optimized solution
x = int(eval(input()))
ans = 1
for b in range(2, 33):
	for p in range(2, 10):
		n = b**p
		if n > x:
			break
		ans = max(ans, n)
print(ans)
# Original solution
X = int(eval(input()))
ans = 1
for i in range(2,int(X**0.5)+1):
    cnt = 2
    y = i**cnt
    while y<=X:
        ans = max(ans,y)
        cnt +=1
        y = y*i
print(ans)       

# Optimized solution
X = int(eval(input()))
if X==1:
    print((1))
else:
    cmax = 0
    for i in range(2,int(X**0.5)+1):
        k = 2
        while i**k<=X:
            k += 1
        cmax = max(cmax,i**(k-1))
    print(cmax)
# Original solution
X = int(eval(input()))
if X==1:
    print((1))
else:
    cmax = 1
    for i in range(2,int(X**0.5)+1):
        k = 2
        while i**k<=X:
            cmax = max(cmax,i**k)
            k += 1
    print(cmax)

# Optimized solution
X = int(eval(input()))
n = 1
if X<=3:
    print((1))
elif X==4:
    print((4))
else:
    n = 4
    for i in range(2,int(X**0.5)+1):
        b = i
        k = 1
        while b**k<=X:
            k += 1
        k -= 1
        if k>=2:
            n = max(n,b**k)
    print(n)
# Original solution
import math

X = int(eval(input()))

ans = 1
for i in range(X+1):
  for j in range(2,max(math.floor(math.sqrt(X-i))+1,3)):
    beki = False
    tmp = X-i
    while True:
      if tmp%j != 0:
        if tmp == 1:
          beki = True
        break
      else:
        tmp //= j
    if beki:
      ans = X-i
      break
  if beki:
    break

print(ans)


# Optimized solution
import math

X = int(eval(input()))

ans = 1

for i in range(2,max(3, math.floor(math.sqrt(X))+1)):
  j = 2
  while i**j <= X:
    if i**j > ans:
      ans = i**j
    j += 1

print(ans)
# Original solution
#素因数分解して列挙する関数、約数列挙ではない！
from collections import Counter
def factorize(n):
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  f = list(Counter(fct).values())
  if 1 not in f and len(set(f))==1:
    return True
  return False

X = int(eval(input()))
for i in range(X,0,-1):
  f = factorize(i)
  if f==True or i==1:
    print(i)
    break

# Optimized solution
def solve():
  ans = 0
  X = int(eval(input()))
  lis = [False]*(X+1)
  lis[1] = True
  for b in range(2,X+1):
    p = 2
    while b**p<=X:
      lis[b**p] = True
      p += 1
  for i in range(X,-1,-1):
    if lis[i]==True:
      return i
print((solve()))
# Original solution
#abc097 b bekijousu
import math

def large_num(n):
    xx=x/n
    p=1
    while xx-n**p>=0:
        p+=1
    if p==1:
        return 0
    else:
        return n**p

x=int(eval(input()))
b_last=int(math.sqrt(1000))
num=[i for i in range(2,b_last+1)]

ans=0


if 4>x:
    ans=1
else:
    for i in num:
        ans=max(large_num(i),ans)
print(ans)


# Optimized solution
#abc97 b
x=int(eval(input()))

beki=[1]

def gene_beki():
    for b in range(2,36):
        for p in range(2,10):
            num=b**p
            if num>x:
                continue
            else:
                beki.append(num)
gene_beki()
print((max(beki)))
# Original solution
*r,=list(range(1,32));x=int(eval(input()));print((max(b**p*(b**p<=x)for p in r[1:]for b in r)))

# Optimized solution
r=list(range(1,32));x=int(eval(input()));print((max(b**p*(b**p<=x)for p in r[1:]for b in r)))
# Original solution
x = int(eval(input()))
c = 1

for b in range(1,x):
  for q in range(2,x):
    if b**q <=x:
      c = max(c,b**q)
    else:
      break
print(c)

# Optimized solution
x = int(eval(input()))
c = []

for b in range(1,x+1):
  for q in range(2,x+2):
    a = b**q
    if a <=x:
      c.append(a)
    else:
      break

C = set(c)
print((max(C)))
# Original solution
n = int(eval(input()))
l = []
for i in range(1,n+1):
    for j in range(2,100):
        if i**j <= n:
            l.append(i**j)
print((max(l)))

# Optimized solution
n = int(eval(input()))
l = []
for i in range(1,n+1):
    for j in range(2,10):
        if i**j <= n:
            l.append(i**j)
print((max(l)))
# Original solution
import math
x = int(eval(input()))

L = []
for i in range(2,int(math.floor(math.sqrt(x)))+1):
  for j in range(x//i + 1):
    if i ** j <= x:
      L.append(i ** j)
      
if L == []:
  print("1")
else:
  print((max(L)))


# Optimized solution
import math
x = int(eval(input()))
if x == 1 or x== 2 or x==3:
  print((1))
  exit()

s = math.floor(math.sqrt(x))

def l(k,p):
    return(int(math.floor(math.log(p)/math.log(k))))

ans = 0
for i in range(2,s+1):
  if i ** (1 + l(i,x)) <= x:
    ans = max(ans, i ** (1+l(i,x)))
  else:
    ans = max(ans, i ** l(i,x))
  if ans == x:
    print(x)
    exit()
  
print(ans)
# Original solution
X = int(eval(input()))
se = set(n**e for n in range(32) for e in range(2,11) if n**e <= X)

answer = max(se)
print(answer)


# Optimized solution
X = int(eval(input()))
S = set(n**e for n in range(32) for e in range(2,11) if n**e<=X)
print((max(S)))
# Original solution
X = int(eval(input()))
ans = 0
for b in range(X + 1):
	for p in range(2, 10):  #2^10=1024
		tmp = b ** p
		if tmp <= X and tmp > ans:
			ans = tmp
print(ans)


# Optimized solution
from bisect import bisect_right

expo = sorted(list(set([b**p for b in range(1, int(1000**0.5)+1) for p in range(2, 10) if b**p <= 1000])))
X = int(eval(input()))

print((expo[bisect_right(expo, X)-1]))
# Original solution
from math import sqrt
X=int(eval(input()))
ans=0
for i in range(1,int(sqrt(X))+1):
    now=i
    b=2
    while i!=1 and X>=i**b:
        now=i**b
        b+=1
    ans=max(ans, now)
print(ans)

# Optimized solution
X=int(eval(input()))
ans=0
for i in range(1,33):
    for j in range(2,11):
        now=i**j
        if ans<now and now<=X:
            ans=now

print(ans)
# Original solution
a = int(eval(input()))
l = [] 

for i in range(100):
    for j in range(2,10):
        if i**j <= a:
            l.append(i**j)
print((max(l)))

# Optimized solution
a = int(eval(input()))
m = 1
for i in range(a//2+1):
    for j in range(1,10):
        if a>=i**j and m <i**j:
            m = i**j
        if a < i**j:
            break
print(m)
# Original solution
x = int(eval(input()))
ans = []
for b in range(1, 1000):
    for p in range(2, 10):
        tmp = b**p
        if tmp <= x:
            ans.append(tmp)
        else:
            break
print((max(*ans)))


# Optimized solution
x = int(eval(input()))
ans = 1
for b in range(1, int(1000**.5)+1):
    for p in range(2, 10):
        y = b**p
        if y <= x and ans < y:
            ans = y
print(ans)
# Original solution
import math

x = int(eval(input()))
 
max_bp = 0
for b in range(1, x + 1):
  for p in range(2, x + 2):
    bp = b ** p
    if bp > x:
      break
    max_bp = max(max_bp, bp)

print(max_bp)

# Optimized solution
# B. Exponential
# https://atcoder.jp/contests/abc097/tasks/abc097_b

x = int(eval(input()))

ans = 1
for b in range(2, int(x ** .5) + 2):
  p = 2
  while b ** p <= x:
    ans = max(ans, b ** p)
    p += 1

print(ans)
# Original solution
def judge(x):
    for i in range(2, x):
        t = x
        while t != 1:
            if t % i == 0:
                t //= i
            else:
                break
            if t == 1:
                return True
    return False


x = int(eval(input()))

ans = 1

for i in range(x, 1, -1):
    if judge(i):
        ans = i
        break

print(ans)


# Optimized solution
x = int(eval(input()))
ans = 1
for base in range(1, 101):
    for p in range(2, 10):
        if base**p > x:
            break
        ans = max(ans, base**p)

print(ans)
# Original solution
import math
X = int(eval(input()))
beki = []
beki.append(1)
Xruto = math.sqrt(X)
Xruto = math.floor(Xruto)
for i in range(2, Xruto+1):
    for j in range(10):
        a = pow(i, j)
        if a <= X:
            beki.append(a)
        else:
            break
print((max(beki)))


# Optimized solution
import math
X = int(eval(input()))
ans = 1
Y = math.floor(math.sqrt(X))
for i in range(2, Y+1):
    for j in range(2, 10):
        a = i**j
        if a <= X:
            ans = max(ans, a)
print(ans)
# Original solution
x=int(eval(input()))
for i in range(x,0,-1):
    for p in range(1,int(i**.5)+1):
        for q in range(10):
            if i==p**q:
                print(i)
                break
        else:
            continue
        break
    else:
        continue
    break


# Optimized solution
x = int(eval(input()))
res = 0
for i in range(1,int(x**.5)+1):
    for j in range(2,1000):
        if i ** j > x:
            break
        res = max(res, i ** j)
print(res)
# Original solution
x = int(eval(input()))
res = 0
for i in range(1,int(x**.5)+1):
    for j in range(2,1000):
        if i ** j > x:
            break
        res = max(res, i ** j)
print(res)


# Optimized solution
n = int(eval(input()))

def check(num):
    for i in range(2, 33):
        j = i * i
        while j < num:
            j *= i
        else:
            if j == num:
                return True
    return False

if n == 1:
    print((1))
    exit()

while True:
    if check(n):
        print(n)
        exit()
    n -= 1
    if n == 1:
        break

print((1))
# Original solution
x = int(eval(input()))
print((max([pow(i, j) for i in range(1, 32)
           for j in range(2, 10) if pow(i, j) <= x])))


# Optimized solution
x = int(eval(input()))

table = [False] * -~x
table[1] = True
for i in range(2, 32):
    j = i * i
    while j <= x:
        table[j] = True
        j *= i

print((max(i for i in range(x + 1) if table[i])))
# Original solution
x=int(eval(input()))
p=10
ans=0
for i in range(1,1+x):
    for j in range(2,p+1):
        if i**j<=x:
            ans=max(ans,i**j)
            
print(ans)

# Optimized solution
x=int(eval(input()))
maxim=0
for i in range(2,32):
    for j in range(2,10):
        temp=i**j
        if temp<=x and maxim<temp:
            maxim=temp
print((maxim if maxim>0 else 1))
# Original solution
from math import sqrt
x=int(eval(input()))
c=1
for b in range(1,int(sqrt(x))+1):
  for p in range(2,x):
    if b**p<=x:
      c=max(b**p,c)
    else:
      break
print(c)


# Optimized solution
from math import sqrt
x=int(eval(input()))
c=1
for b in range(1,int(sqrt(x))+1):
  for p in range(2,10):
    if b**p<=x:
      c=max(b**p,c)
    else:
      break
print(c)
# Original solution
X = int(eval(input()))
ans = 1
for i in range(1, X):
  for p in [2, 3, 5, 7]:
    calc = i**p
    if(calc <= X):
      ans = max(ans, calc)
print(ans)

# Optimized solution
X = int(eval(input()))
ans = 1
for i in range(1,X+1):
  for p in [2, 3, 5, 7]:
    if(i**p <= X):
      ans = max(ans, i**p)
print(ans)
# Original solution
from bisect import bisect_right


cands = []
for i in range(2, 400):
    cur = i
    while cur * i <= 1000:
        cands.append(cur * i)
        cur *= i
cands.sort()

X = int(eval(input()))
if X == 1:
    print((1))
else:
    print((cands[bisect_right(cands, X) - 1]))


# Optimized solution
X = int(eval(input()))
ans = 1
for i in range(2, 32):
    for j in range(2, 10):
        if i ** j > X:
            continue
        ans = max(ans, i ** j)
print(ans)
# Original solution
from math import sqrt
x = int(eval(input()))
cnt = 0
l = []
for i in range(1, x + 1):
    for j in range(1, int(sqrt(i)) +1):
        for k in range(2, 10):
            if j ** k == i:
                l.append(i)
print((max(l)))

# Optimized solution
from math import sqrt
x = int(eval(input()))
l = []
for i in range(1, x + 1):
    for j in range(1, int(sqrt(i)) +1):
        for k in range(2, 10):
            if j ** k == i:
                l.append(i)
print((max(l)))
# Original solution
x = int(eval(input()))
list_ = []

if x == 1:
    print((1))
else:
    b = 2
    while b**2 <= x:
        p = 2
        while b**p <= x:
            list_.append(b**p)
            p += 1
        b += 1
    print((max(list_)))

# Optimized solution
x = int(eval(input()))
ans = 1
if x == 1:
    print((1))
else:
    b = 2
    while b**2 <= x:
        p = 2
        while b**p <= x:
            ans = max(b**p, ans)
            p += 1
        b += 1
    print(ans)
# Original solution
x=int(eval(input()))
ans=[]
for i in range(int(x**(1/2))+1):
    for j in range(int(x**(1/2))+1):
        if i**j<=x:
            ans.append(i**j)
print((max(ans)))

# Optimized solution
x=int(eval(input()))
print((max([i**j for i in range(33) for j in range(2,10) if i**j<=x])))
# Original solution
import math
ans = 0
X = int(eval(input()))
if X<4:
    print((1))
else:
    for i in range(2,math.ceil(math.sqrt(X))):
        for j in range(math.ceil(math.log(X)/math.log(i))+1):
            if i**j <= X:
                ans = max(i**j,ans)
    print(ans)


# Optimized solution
ans = 0

X = int(eval(input()))
for i in range(1,33):
    for j in range(2,11):
        if i**j <= X:
            ans = max(ans,i**j)
print(ans)
# Original solution
# ABC097 B  Exponential
x = int(eval(input()))
ans = 0

for i in range(1,33):
    for j in range(2,10):
        t = i**j
        if t <= x:
            ans = max(t,ans)
print(ans)

# Optimized solution
x=int(eval(input()))
exp=[0]*(x+1)
exp[1]=1
ans=0
for i in range(2,x+1):
    t=i*i
    while t<=x:
        exp[t]=1
        t*=i

for i in range(1,x+1):
    if exp[i]:
        ans=max(i,ans)
print(ans)
# Original solution
x=int(eval(input()))
a=set()
for i in range(1,1001):
  for j in range(2,34):
    t=i**j
    if t<=x:
      a.add(i**j)
a=list(a)
a.sort()
print((a[-1]))

# Optimized solution
x=int(eval(input()))
ans=0
for i in range(1,35):
  for j in range(2,10):
    t=i**j
    if t<=x:
      ans=max(ans,t)
print(ans)
# Original solution
x=int(eval(input()))
v=[]
for i in range(1,32):
    for j in range(2,1000):
        if i**j<=x and (i+1)**j>x:
            v.append(i**j)
print((max(v)))

# Optimized solution
x=int(eval(input()))
v=[]
for j in range(2,11):
    for i in range(1,32):
        if i**j<=x and (i+1)**j>x:
            v.append(i**j)
            break
print((max(v)))
# Original solution
x = int(eval(input()))

ans = 0
for i in range(1, 1000):
    for j in range(2, 10):
        if i ** j <= x:
            ans = max(i ** j, ans)
            
print(ans)

# Optimized solution
x = int(eval(input()))

ans = 0
if x == 1:
    ans = 1
else:
    for i in range(2, 100):
        n = 2
        while i ** n <= x:
            ans = max(ans , i ** n)
            n += 1
            
print(ans)
# Original solution
X = int(eval(input()))
ans = 1
for b in range(2,X):
    for p in range(2,X):
        tmp_ans = b ** p
        if tmp_ans > X:
            break
        if tmp_ans > ans:
            ans = tmp_ans
print(ans)

# Optimized solution
X = int(eval(input()))
ans = 1
for b in range(1, X):
    for p in range(2, X):
        tmp = b ** p
        if tmp > X:
            break
        if ans < tmp:
            ans = tmp
print(ans)
# Original solution
import math
x=int(eval(input()))
ans=[1]
for i in range(2,x+1):
    #print(i)
    k=int(math.log(x,i))
    if k>=2:
        if i**(k+1) <= x:
            ans.append(i**(k+1))
        else:
            ans.append(i**k)
print((max(ans)))
#print(ans)


# Optimized solution
x=int(eval(input()))
ans=[1]
for i in range(2,x+1):
    k=2
    while True:
        a=i**k
        if a<=x:
            ans.append(a)
            k+=1
        else:
            break
print((max(ans)))
# Original solution
X = int(eval(input()))

ans = 0
for i in range(1, 100):
    for j in range(2, 100):
        if i ** j <= X:
            ans = max(ans, i ** j)

print(ans)


# Optimized solution
X = int(eval(input()))

ans = 1
for b in range(2, 40):
    p = 2
    while True:
        val = b ** p
        if val > X:
            break
        ans = max(ans, val)
        p += 1

print(ans)
# Original solution
import sys
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print((int(s)))

while True:
    X, Y, Z = list(map(int, input().split()))
    if X | Y | Z == 0:
        sys.exit()
    V = list(map(int, input().split()))
    E = [0] * 100
    A = [0] * 100
    for _ in range(Z):
        n, e, a = list(map(int, input().split()))
        E[n] = e
        if e == 3:
            A[n] = -a
        else:
            A[n] = a
    solve(X, Y, Z, V, E, A)

# Optimized solution
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = list(map(int, input().split()))
        if X | Y | Z == 0:
            sys.exit()
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = list(map(int, input().split()))
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)
# Original solution
while True:
    x, y, z = list(map(int, input().split()))
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = list(map(int, input().split()))
    for i in range(z):
        n, e, a = list(map(int, input().split()))
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(5001):
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print(int(ans)) 

# Optimized solution
while True:
    x, y, z = list(map(int, input().split()))
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = list(map(int, input().split()))
    for i in range(z):
        n, e, a = list(map(int, input().split()))
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(y*100):
            if dp[i][j] == 0.0: continue
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print(int(ans))