Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))

def too_slow(d_pairs):
    ds = []
    for d, c in d_pairs:
        for _ in range(c):
            ds.append(d)
    d, c = 0, 0
    for next_d in ds:
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
    return c-1


def contract_list(ds):
    d, c = 0, -1
    for next_d, next_c in ds:
        c += next_c
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
        # print(d, c)
    return d, c

def contract_pair(d, orig_c):
    c = 0
    ds = [(d, c)]
    for _ in range(int(math.log(orig_c, 2)) + 1):
        d = d + d
        c = c*2 +1
        if d >= 10:
            d = d % 10 + 1
            c += 1
        ds.append((d, c))
    # print(ds)

    ds_for_calc = []
    for i, b in enumerate(reversed(bin(orig_c)[2:])):
        # print(bin(orig_c), b)
        if b == "1":
            ds_for_calc.append(ds[i])
    # print("for_cal", ds_for_calc)

    return contract_list(ds_for_calc)


ds_for_calc = []
orig_ds = []
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    orig_ds.append((d, c))
    ds_for_calc.append(contract_pair(d, c))
    # print(ds_for_calc[-1])
# print("last_list", ds_for_calc)
answer = contract_list(ds_for_calc)[1]
# print(too_slow(orig_ds), answer)
# assert too_slow(orig_ds) == answer
print(answer)

exit(0)


### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))
total_sum = 0
total_digits = 0
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    total_digits += c
    total_sum += d*c
answer = ((total_sum-1) // 9) + total_digits -1
print(answer)
exit(0)
### BUGGY CODE ###

def myAnswer(N:int,A:list) -> int:
   dic = {}
   counter = 0
   for a in A:
      if(a in dic.keys()):
         if(dic[a]==a):
            counter += 1
         else:
            dic[a]+= 1
      else:
         dic[a] = 1
   for key,value in dic.items():
      if(value < key):
         counter += value
   return counter

def modelAnswer():
   return
def main():
   N = int(input())
   A = list(map(int,input().split()))
   print(myAnswer(N,A))
if __name__ == '__main__':
   main()

### FIXED CODE ###

def myAnswer(N:int,A:list) -> int:
   dic = {}
   counter = 0
   for a in A:
      if(a in dic.keys()):
         if(dic[a]==a):
            counter += 1
         else:
            dic[a]+= 1
      else:
         dic[a] = 1
   for key,value in dic.items():
      if(value < key):
         counter += value
   return counter

def modelAnswer():
   return
def main():
   N = int(input())
   A = list(map(int,input().split()))
   print(myAnswer(N,A))
if __name__ == '__main__':
   main()
### BUGGY CODE ###

n,m = map(int, input().split())

ac_list = []
correct = 0
wrong = [0] * n
penalty = 0

for i in range(m):
    p,s = input().split()
    if s == 'AC' and p not in ac_list:
        ac_list.append(p)
        correct += 1
        penalty += wrong[int(p)-1]
    elif s == 'WA' and p not in ac_list:
        wrong[int(p)-1] += 1 
    else:
        continue

print('{} {}'.format(correct,penalty))

### FIXED CODE ###

n, m = map(int, input().split())
ac = 0
wa = 0
 
ac_tf = [0] * n
wa_num = [0] * n
 
for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if s == "AC":
        if ac_tf[p] == 0:
            ac += 1
            wa += wa_num[p]
            ac_tf[p] = 1
    else:
        wa_num[p] += 1
            
print(ac, wa)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = []
points = []
for i in range(q):
    a.append(int(input()))
for i in range(1,n+1):
    points.append(a.count(i))
tot = sum(points)
tot = -tot
for i in range(n):
    if tot + points[i] + k > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
a = {i: 0 for i in range(1,n+1)}
points = []

for i in range(1,q+1):
    x = int(input())
    if x in a:
        a[x] += 1
    else: 
        a[x] = 1

tot = sum(a.values())
tot = -tot

for i in range(1,n+1):
    if tot + a[i] + k > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

a = int(input())

ans = 0
temp = a
for i in range(1, a + 1):
  ans += (i % temp)

print(ans)

### FIXED CODE ###

a = int(input())
print(sum(range(1, a)))
### BUGGY CODE ###

K,S = map(int, input().split())
n = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k ==S:
                n=n+1
            else:
                n =n

print(n)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline


K,S = map(int, input().split())
n = 0
up = math.floor(K)
for i in range(0,K+1):
    for j in range(0, K+1):
        if(0<= S-i-j <=K):
            n +=1
        else:
                n =n

print(n)
### BUGGY CODE ###

N,M = map(int,input().split())
As = list(map(str,input().split()))

match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}


ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())

dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"

for i in range(N+1):
    for a,k in zip(ns,ks):
        if i+k <= N:
            dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))
        else:
            continue
print(dp[N])


### FIXED CODE ###

## DP問題
 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 
# test
# N, M = 10000, 9
# As = [str(i) for i in range(1,10)]
 
 
ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"
 
for i in range(N+1):
    # print(i)
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            else:
                dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))

        else:
            continue
print(dp[N])
### BUGGY CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
di.sort(key=lambda x:x[1])
di = [e for e in di if e[1] >= min(ls)]
ls.sort()
for i in range(len(di)):
    for j in range(di[i][0]):
        if di[i][1] > ls[j]:
            ls[j] = di[i][1]
        else:
            break
    ls.sort()
print(sum(ls))

### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
fi = []
for i,j in di:
    fi.append([j,i])
for k in ls:
    fi.append([k,1])
fi.sort(reverse=True)
ans = 0
cnt = 0
how = 0
while True:
    if how + fi[cnt][1] < n:
        how += fi[cnt][1]
        ans += fi[cnt][1]*fi[cnt][0]
    else:
        ans += (n-how)*fi[cnt][0]
        break
    cnt += 1
print(ans)
### BUGGY CODE ###

S = input()

s_list=[]
for i in range(len(S)):
    s_list.append(int(S[i]))

num=0
judge=1
N=len(s_list)
while judge==1:
    judge=0
    for i in range(N):
        if i+1 < len(s_list):
            while s_list[i] != s_list[i+1]:
                #print(i,len(s_list),s_list,s_list[i],s_list[i+1])
                del s_list[i:i+2]
                num+=2
                judge=1
                if i+i>=len(s_list):
                    break
        else:
            break
    N = len(s_list)
print(num)

### FIXED CODE ###

S = input()

zero = 0
one = 0
for i in range(len(S)):
	if S[i] == '0':
		zero += 1
	else:
		one += 1
print(min(zero,one)*2)
### BUGGY CODE ###

import sys
S=0
N=int(input())
L=list(map(int,input().split()))
for i in range(1,N+1):
  print(L.count(i))
  S+=L.count(i)
  if S==N:
    for j in range(N-i):
      print(0)
      sys.exit()

### FIXED CODE ###

import collections
S=0
N=int(input())
L=list(map(int,input().split()))
c = collections.Counter(L)
for i in range(1,N+1):
  print(c[i])
### BUGGY CODE ###

k,s= map(int,input().split())


count = 0

arr = []
for i in range(0,k+1):
    arr.append(i)

def binary_search(arr,i):
    x = arr
    low = 0
    high = len(x)-1
    t = (low + high) // 2 
    # 探索の下限のlowが上限のhighになるまで探索
    # lowがhighに達すると数は見つからなかったということ
    while (low<=high):
        if (i==x[t]):
            break
        elif (i > x[t]):
            low = t + 1
        elif (i < x[t]):
             high = t - 1
        t = (low + high) // 2

    if (i==x[t]):
        return t
    else:
        return -1




for i in range(0,k+1):
    for j in range(0,k+1):
        l = s - i - j
        answer = binary_search(arr,l)
        # print(i,j,l)
        if(answer!=-1):
            # print('clear',i,j,l)
            count += 1


print(count)



### FIXED CODE ###

k,s= map(int,input().split())


count = 0

# arr = []
# for i in range(0,k+1):
#     arr.append(i)

# def binary_search(arr,i):
#     x = arr
#     low = 0
#     high = len(x)-1
#     t = (low + high) // 2 
#     # 探索の下限のlowが上限のhighになるまで探索
#     # lowがhighに達すると数は見つからなかったということ
#     while (low<=high):
#         if (i==x[t]):
#             break
#         elif (i > x[t]):
#             low = t + 1
#         elif (i < x[t]):
#              high = t - 1
#         t = (low + high) // 2

#     if (i==x[t]):
#         return t
#     else:
#         return -1




# for i in range(0,k+1):
#         l = s - i - j
#         arr = arr[]
#         answer = binary_search(arr,l)
#         # print(i,j,l)
#         if(answer!=-1):
#             # print('clear',i,j,l)
#             count += 1

for i in range(0,k+1):
    for j in range(i,k+1):
        l = s-i-j
        if l>=j and l <= k:
            if i!=j and j != l and i!=l:
                # print(i,j,l)
                count += 6
            elif i == j and j == l and i == l:
                # print(i,j,l)
                count += 1
            else:
                # print(i,j,l)
                count += 3

print(count)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      if k != 2 * j - i:
        a, b, c = S[i], S[j], S[k]
        if a != b and b != c and c != a:
          count += 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

print(ans)
### BUGGY CODE ###

K = int(input())

a = [1, 1]

for i in range(K):
    min_ind = a.index(min(a))
    a[min_ind] += 2
    a[1-min_ind] -= 1

print(2)
print(*a)

### FIXED CODE ###

K = int(input())

a = [49 for i in range(50)]

for i in range(50):
    a[i] += K//50
    
for i in range(50):
    mod = K % 50
#     if mod != 0:
    if mod >= i+1:
        a[i] = a[i] + 50 - (mod)
    else:
        a[i] = a[i] - (mod)

print(50)
print(*a)
### BUGGY CODE ###

import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = cl.deque()
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

n,l,T = map(int,input().split())
s = [0 for i in range(n)]
for i in range(n):
    s[i] = list(map(int, input().split()))

def f(w):
    if w == 1:
        return 1
    elif w == 2:
        return -1
    
t = 0
d = l

while t < T:
    for i in range(n):
        if i < n-1 :
            if s[i][0] < s[i+1][0] and s[i][1] == 1 and s[i+1][1] == 2:
                if s[i+1][0] - s[i][0] < d:
                    d = s[i+1][0] - s[i][0]
    
            elif s[i][0] > s[i+1][0] and s[i][1] == 1 and s[i+1][1] == 2:
                if s[i+1][0] + l - s[i][0] < d:
                    d = s[i+1][0] + l - s[i][0]
                    
        elif i == n-1:
            if s[i][0] < s[0][0] and s[i][1] == 1 and s[0][1] == 2:
                if s[0][0] - s[i][0] < d:
                    d = s[0][0] - s[i][0]
                    
            elif s[i][0] > s[0][0] and s[i][1] == 1 and s[0][1] == 2:
                if s[0][0] + l - s[i][0] < d:
                    d = s[0][0] + l - s[i][0]
                    
                    
    for j in range(n):
        if t + d/2 <= T:
            s[j][0] += f(s[j][1]) * (d/2)
            if s[j][0] >= l:
                s[j][0] -= l
            elif s[j][0] < 0:
                s[j][0] += l
            
        else:
            s[j][0] += f(s[j][1]) * (T-t)
            if s[j][0] >= l:
                s[j][0] -= l
            elif s[j][0] < 0:
                s[j][0] += l
        if j > 0 and s[j][0] == s[j-1][0]:
            s[j][1], s[j-1][1] = s[j-1][1], s[j][1]
        if j == n-1 and s[j][0] == s[0][0] :
            s[j][1], s[0][1] = s[0][1], s[j][1]
            
    t = t + d/2
    d = l
    
import math

for i in range(n):
    print(math.floor(s[i][0]))

### FIXED CODE ###

from math import floor
n,l,t = map(int,input().split())
ants = []
touch = 0

for i in range(n):
    x, w = map(int,input().split())
    if w == 1:
        touch += (x + t) // l
        x1 = (x + t) % l
    else:
        touch += (x - t) // l
        x1 = (x - t) % l
    ants.append(x1)
touch = touch % n
ants.sort()
ants = ants[touch:]+ants[:touch]

for i in range(n):
    print(ants[i])
### BUGGY CODE ###

s = input()
n, a, b = s.split()
n, a, b =  int(n), int(a), int(b)


a0 = 1
a1 = 1 
for i in range(1, a+1):
  a0 = a0 * (n - i + 1) % 1000000007
  a1 = a1 * i % 1000000007

b0 = 1
b1 = 1 
for i in range(1, b+1):
  b0 = b0 * (n - i + 1) % 1000000007
  b1 = b1 * i % 1000000007

A = (pow(2, n) - 1 - a0 * pow(a1, 1000000005) - b0 * pow(b1, 1000000005)) % 1000000007

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans = ans * x % 1000000007
        x *= x % 1000000007
        n >>= 1
    return ans % 1000000007

print(A)

### FIXED CODE ###

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans = ans * x % 1000000007
        x *= x % 1000000007
        n >>= 1
    return ans % 1000000007

s = input()
n, a, b = s.split()
n, a, b =  int(n), int(a), int(b)


a0 = 1
a1 = 1 
for i in range(1, a+1):
  a0 = a0 * (n - i + 1) % 1000000007
  a1 = a1 * i % 1000000007

b0 = 1
b1 = 1 
for i in range(1, b+1):
  b0 = b0 * (n - i + 1) % 1000000007
  b1 = b1 * i % 1000000007

A = (pow(2, n) - 1 - a0 * pow(a1, 1000000005) - b0 * pow(b1, 1000000005)) % 1000000007

print(A)
### BUGGY CODE ###

s = input()

mod = 1000000007
n = 13

dp = [0] * 13
dp[0] = 1

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
                # nextDp[(k * mul + j) % n] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] += dp[j]
            # nextDp[(k * mul + j) % n] %= mod

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5] % mod)


### FIXED CODE ###

s = input()

mod = 1000000007
n = 13

dp = [0] * 13
dp[0] = 1

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
        for j in range(n):
            nextDp[j] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] = dp[j]

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5])
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

class Node:
    def __init__(self, num, parent=None):
        self.num = num
        self.parent = parent
        self.hp = 0

def main():
    N = int(input())
    a= sorted(list(map(int, input().split())))
    # print(a)
    choose = [a.pop(-1)]
    ok = True
    for i in range(N):
        ok = True
        tmp = []
        for c in choose:
            # print(i, c)
            ok = False
            for i in range(len(a)-1, -1, -1):
                if a[i] < c:
                    # print(a[i])
                    tmp.append(a.pop(i))
                    ok = True
                    break
            if not ok:
                break
        choose += tmp
        if not ok:
            break
    
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = sorted(list(map(int, input().strip().split())), reverse=True)
    check = [False] * (2**N)
    now = []
    now.append([s[0], 1])
    check[0] = True
    ok = True
    for i in range(N):
        next_ = []
        tmp = 0
        for j in range(len(now)):
            hp, start = now[j]
            start = max(start, tmp)
            ok = False
            for k in range(start, 2**N):
                if s[k] < hp and not check[k]:
                    tmp = k+1
                    now[j][1] = k+1
                    check[k] = True
                    next_.append([s[k], k+1])
                    ok = True
                    break
            if not ok:
                break
        now += next_
        now = sorted(now, reverse=True)
        if not ok:
            break
    
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()
### BUGGY CODE ###

K, S = map(int, input().split())
a = 0
for x in range(K+1):
  for y in range(K+1):
    if x+y>S :
      continue
    for z in range(K+1):
      if x+y+z == S :
        a +=1
      
      
print(a)

### FIXED CODE ###

K, S = map(int, input().split())
a = 0
for x in range(K+1):
  for y in range(K+1):
    if 0<=S-x-y<=K :
      a+=1   
print(a)
### BUGGY CODE ###

# Problem D - String Formation

# input process
S = input().replace("\n", "")
S = list(S)
Q = int(input()) # query number

# initialization
sento = 1

# process
for i in range(Q):
    query_num = input()
    # クエリが１の時
    if query_num[0]=="1":
        # 反転処理
        if sento==1:
            sento = 10
        elif sento==10:
            sento = 1
    elif query_num[0]=="2":
        n, f, c = query_num.split()
        f = int(f)
        if f==1: # 先頭追加処理
            # 先頭の位置によって変わる
            if sento==1:
                S.insert(0,c)
            elif sento==10:
                S.append(c)
        elif f==2: # 末尾追加処理
            if sento==1:
                S.append(c)
            elif sento==10:
                S.insert(0,c)

# output process
if sento==1:
    print("".join(S))
else:
    print("".join(S[::-1]))


### FIXED CODE ###

# Problem D - String Formation

from collections import deque

# input process
S = input().replace("\n", "")
S = deque(list(S))
Q = int(input()) # query number

# initialization
sento = 1

# process
for i in range(Q):
    query_num = input()
    # クエリが１の時
    if query_num[0]=="1":
        # 反転処理
        if sento==1:
            sento = 10
        elif sento==10:
            sento = 1
    elif query_num[0]=="2":
        n, f, c = query_num.split()
        f = int(f)
        if f==1: # 先頭追加処理
            # 先頭の位置によって変わる
            if sento==1:
                S.appendleft(c)
            elif sento==10:
                S.append(c)
        elif f==2: # 末尾追加処理
            if sento==1:
                S.append(c)
            elif sento==10:
                S.appendleft(c)

# output process
if sento==1:
    print("".join(S))
else:
    print("".join(list(S)[::-1]))
### BUGGY CODE ###

n, m, d = map(int, input().split())
sum = 0
patt = (n-d)
if d != 0:
    patt = 2 * patt
totyu = n ** (m-2)
beau = totyu * (m-1)
print(patt * beau / (totyu * n * n))

### FIXED CODE ###

n, m, d = map(int, input().split())
sum = 0
patt = n-d
if d != 0:
    patt = 2 * patt
print(patt * (m-1) / (n * n))