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

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす
first_conditions = r*g*b
# 1つ目の条件は満たすが、2つ目の条件は満たさない
second_condition = 0
sum_ = 0
# 2つ目の条件を満たすということは、(i,j,k)のときk=2j-i
for i in range(n):
    for j in range(i,n):
        if 2*j-i< n  and s[i] != s[2*j-i] and s[j] != s[2*j-i] and s[i] != s[j]:
            second_condition += 1
print(first_conditions-second_condition)

### FIXED CODE ###

n = int(input())
s = input()
r_ary = []
g_ary = []
b_ary = []
for i in (s):
    if i == 'R':
        r_ary.append(i)
    elif i == 'G':
        g_ary.append(i)
    elif i == 'B':
        b_ary.append(i)
r = len(r_ary)
g = len(g_ary)
b = len(b_ary)
first_conditions = r*g*b
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n and s[i]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[j]:
            first_conditions -= 1
print(first_conditions)
### BUGGY CODE ###

x, k, d = map(int, input().split())

past1_x = 0
past2_x = 0

result = 0

for i in range(k):
	past2_x = past1_x
	past1_x = x
	if x > 0:
		x -= d
	else:
		x += d
	
	if (past2_x == x and i != 0) or i == k - 1:
		if (k - i) % 2 == 0:
			result = abs(past1_x)
		else:
			result = abs(x)
		break

print(result)

### FIXED CODE ###

x, k, d = map(int, input().split())

result = 0

abs_x = abs(x)
firstNearestIterNum = abs_x // d

if firstNearestIterNum >= k:
	result = abs_x - (d * k)
else:
	if (k - firstNearestIterNum) % 2 == 1:
		result = abs_x - (d * (firstNearestIterNum + 1))
	else:
		result = abs_x - d * firstNearestIterNum

print(abs(result))
### BUGGY CODE ###

N, M = map(int, input().split())
AB_list = [tuple(map(int, input().split())) for i in range(N)]

sorted_AB_list = sorted(AB_list, key=lambda x:x[0], reverse=False)
sorted_AB_list = sorted(sorted_AB_list, key=lambda x:x[1], reverse=True)

money = 0

for i in range(M):
  remain_days = i+1
  
  for (A, B) in sorted_AB_list:
    if A <= remain_days:
      money += B
      sorted_AB_list.remove((A, B))
      break

print(money)

### FIXED CODE ###

from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        heappush(q, -jobs.pop(-1)[1])
    if q:
        ans -= heappop(q)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())

ans = 0
while N > 0 and M > 0:
    if M < 2:
        break
    N -= 1
    M -= 2
    ans += 1

while M >= 4:
    M -= 4
    ans += 1

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())

s, c = N, M // 2

ans = 0
if s > c:
    ans = c
else:
    ans = (M - s*2) // 4 + s
print(ans)
### BUGGY CODE ###

n=int(input())
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

def f(i,j,k):
    if i==j==k==0:
        return
    res=n
    if i>0:
        res+=dp[i-1][j][k]*i
    if j>0:
        res+=dp[i+1][j-1][k]*j
    if k>0:
        res+=dp[i][j+1][k-1]*k
    res*=1/(i+j+k)
    dp[i][j][k]=res
    return

for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            f(i,j,k)
print(dp[p][q][r])


### FIXED CODE ###

n=int(input())
dp=[[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

l=[1]
for i in range(1,1000):
    l.append(1.0/i)

for k in range(r+1):
    for j in range(q+r-k+1):
        for i in range(n-k-j+1):
            if i==j==k==0:
                continue
            res=n
            if i>0:
                res+=i*dp[i-1][j][k]
            if j>0:
                res+=j*dp[i+1][j-1][k]
            if k>0:
                res+=k*dp[i][j+1][k-1]
            res*=1/(i+j+k)
            dp[i][j][k]=res

print(dp[p][q][r])
### BUGGY CODE ###

H, W = map(int, input().split())
e = [[False for _ in range(W)] for _ in range(H)]
cnt = 0
for r in range(H):
    a = input()
    for c in range(W):
        if a[c] == '#':
            cnt += 1
            e[r][c] = True

ans = 0
while cnt < H * W:
    st = set()
    for r in range(H):
        for c in range(W):
            if e[r][c]:
                for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
                    nr = r + dr
                    if not (0 <= nr < H): continue
                    nc = c + dc
                    if not (0 <= nc < W): continue
                    if e[nr][nc]: continue
                    st.add((nr, nc))
    for nr, nc in st:
        e[nr][nc] = True
        cnt += 1
    ans += 1
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r][c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = list(set(A))
res = 0
num = []

if len(L) <= K:
    res = 0

else:
    for i in L:
        num.append(A.count(i))
    
    num.sort()

    for i in range(len(L) - K):
        res += num[i]

print(res)

### FIXED CODE ###

from collections import Counter
d = Counter() 
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = list(set(A))
res = 0
num = []
d.update(A)
if len(L) <= K:
    res = 0

else:
    for i in L:
        num.append(d[i])
    
    num.sort()

    for i in range(len(L) - K):
        res += num[i]

print(res)
### BUGGY CODE ###

n = int(input())
a= list(map(int, input().split()))

ans = 1
for i in range(n):
    ans = ans * a[i]

if ans > 10 ** 18:
    ans = -1

print(ans)

### FIXED CODE ###

n = int(input())
a= list(map(int, input().split()))

for i in range(0, n):
    if a[i] == 0:
        print(0)
        exit(0)

ans = 1
for i in range(0, n):
    ans = ans * a[i]
    if ans > 10 ** 18:
        print(-1)
        exit(0)

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

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
    n,k = readInts()
    A = readInts()

    setA = list(set(A))
    if len(setA) <= k:
        print(0)
        exit()

    ALL = []
    for i in setA:
        ALL.append(A.count(i))
    ALL = sorted(ALL)
    ans = 0
    sLen = len(setA)
    #print(*ALL)
    for i in range(sLen-k):
        ans += ALL[i]
    print(ans)
if __name__ == '__main__':
  main()


### FIXED CODE ###

import collections
#aa = collections.Counter(a) # list to list

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
    n,k = readInts()
    A = readInts()
    A_qu = collections.Counter(A)
    ALL = []
    for i in A_qu:
        ALL.append(A_qu[i])
    ALL = sorted(ALL)
    ans = 0
    for i in range(len(ALL) - k):
        ans += ALL[i]
    print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

N, M = map(int,input().split())
count = yen = 0
li = [list(map(int,input().split())) for i in range(N)]
li.sort() 
for i in range(0,len(li),1):
  count += li[i][1] 
  yen += li[i][0]*li[i][1] 
  if count > M: 
    for j in range(0,li[i][1],1):
      count -= 1
      yen -= li[i][0]
      if count == M: 
        break
print(yen)

### FIXED CODE ###

N, M = map(int,input().split())
count = yen = imp = 0
li = [list(map(int,input().split())) for i in range(N)]
li.sort()
for i in range(0,len(li),1):
  count += li[i][1] 
  yen += li[i][0]*li[i][1] 
  if count > M:
    imp = abs(M-count)
    count -= abs(M-count)
    yen -= li[i][0]*imp
  if count == M: 
    break
print(yen)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_acc = [0]
B_acc = [0]
acc = 0
for a in A:
    acc += a
    A_acc.append(acc)
acc = 0
for b in B:
    acc += b
    B_acc.append(acc)
ans = 0
for i in range(N + 1):
    if A_acc[i] > K:
        break
    for j in range(M,-1,-1):
        if A_acc[i] + B_acc[j] <= K:
            ans = max(ans, i + j)
            break
print(ans)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if K >= sum(A) + sum(B):
    print(M + N)
    exit()
acc = 0
ans = 0
for j, b in enumerate(B):
    acc += b
    if K >= acc:
        ans = j + 1
for i in range(N):
    acc += A[i]
    if K >= acc:
        ans = max(ans, i + j + 2)
        continue
    else:
        while (K < acc) & (j > -1):
            acc -= B[j]
            j -= 1
        if K >= acc:
            ans = max(ans, i + j + 2)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import accumulate
n,m,s,t= map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]

g = defaultdict(list)
c = {}
for i in range(1,n+1):
    g[i].append(n+i)
    c[(i,n+i)] = 0
for u,v,a,b in uvab:
    g[u].append(v)
    g[v].append(u)
    g[n+u].append(n+v)
    g[n+v].append(n+u)
    c[(u,v)] = a
    c[(v,u)] = a
    c[(n+u,n+v)] = b
    c[(n+v,n+u)] = b

inf = 10**15
ds2t = [inf for i in range(2*n+1)]
ds2t[s] = 0

dq = deque([s])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if ds2t[nv] > ds2t[v] + c[(v,nv)]:
            ds2t[nv] = ds2t[v] + c[(v,nv)]
            dq.append(nv)


dt2s = [inf for i in range(2*n+1)]
dt2s[n+t] = 0

dq = deque([n+t])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if dt2s[nv] > dt2s[v] + c[(v,nv)]:
            dt2s[nv] = dt2s[v] + c[(v,nv)]
            dq.append(nv)

ds = []
for i in range(1,n+1):
    ds.append(ds2t[i] + dt2s[n+i])

ds = accumulate(ds[::-1], min)

for d in reversed(list(ds)): 
    print(10**15-d)




### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import accumulate
n,m,s,t= map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]

g = defaultdict(list)
c = {}
'''
for i in range(1,n+1):
    g[i].append(n+i)
    c[(i,n+i)] = 0
    '''
for u,v,a,b in uvab:
    g[u].append(v)
    g[v].append(u)
    g[n+u].append(n+v)
    g[n+v].append(n+u)
    c[(u,v)] = a
    c[(v,u)] = a
    c[(n+u,n+v)] = b
    c[(n+v,n+u)] = b

inf = 10**15
ds2t = [inf for i in range(2*n+1)]
ds2t[s] = 0

dq = deque([s])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if ds2t[nv] > ds2t[v] + c[(v,nv)]:
            ds2t[nv] = ds2t[v] + c[(v,nv)]
            dq.append(nv)


dt2s = [inf for i in range(2*n+1)]
dt2s[n+t] = 0

dq = deque([n+t])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if dt2s[nv] > dt2s[v] + c[(v,nv)]:
            dt2s[nv] = dt2s[v] + c[(v,nv)]
            dq.append(nv)

ds = []
for i in range(1,n+1):
    ds.append(ds2t[i] + dt2s[n+i])

ds = accumulate(ds[::-1], min)

for d in reversed(list(ds)): 
    print(10**15-d)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E
# dp[[i][j]で、(i,j)で可能な偏りをリストとして格納していく

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[[] for _ in range(W)] for _ in range(H)]
dp[0][0].append(x[0][0])
for i in range(H):
    for j in range(W):
        candidate = []
        if i > 0:
            candidate += dp[i-1][j]
        if j > 0:
            candidate += dp[i][j-1]

        if len(candidate) > 0:
            candidate = list(set(candidate))

        for num in candidate:
            dp[i][j].append(num + x[i][j])
            dp[i][j].append(abs(num - x[i][j]))

print(min(dp[H-1][W-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# E: bit演算を活用して効率的に計算しないとTLEになる

# dp[[i][j]で、(i,j)で可能な偏りを格納していく
# 1, 2, 3が可能な場合は"00000111"と表現する
# n + m を可能にするには、n << mにすれば良い
# (1, 2, 3)に2を足して(3, 4, 5)を可能にするなら、
# "00011100"としたいので、n << mで良い
# (3, 4, 5)に±4する場合；
# 求めたいのは(7, 8, 9) | (-1, 0, 1)
# −１を1としたい

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << x[0][0]
# print(bin(dp[0][0]))


def reverse(d, x):
    res = 0
    for i in range(x+1):
        res <<= 1
        if (1<<i) & d:
            res |= 1
    return res


for i in range(H):
    for j in range(W):
        g = x[i][j]
        if i > 0:
            d1 = dp[i-1][j]
            dp[i][j] |= d1 << g | d1 >> g | reverse(d1, g)
        if j > 0:
            d2 = dp[i][j-1]
            dp[i][j] |= d2 << g | d2 >> g | reverse(d2, g)


a = dp[H-1][W-1]
for i in range(a.bit_length()):
    if a >> i & 1 == 1:
        print(i)
        sys.exit()
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
for i in range(m):
  if t[i] in d:
    d.remove(t[i])
  else:
    print("NO")
    exit()
print("YES")


### FIXED CODE ###

import collections

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
dc = collections.Counter(d)
tc = collections.Counter(t)
for i in tc:
    if tc[i] > dc[i]:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N = int(input())
C = 10 ** 9 + 7
B = 0
A = list(map(int, input().split()))
for i in range(N):
    for j in range(i+1, N):
        B += A[i] * A[j]        
print(B % C)        



### FIXED CODE ###

N = int(input())
C = 10 ** 9 + 7
B = 0
a = 0
ans = 0
A = list(map(int, input().split()))
for i in range(N):
    a += A[i]
for i in range(N-1):
    a -= A[i]
    B = A[i] * a
    ans += B
    B = 0    
print(ans % C)
### BUGGY CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    for x in range(l_k):
        check_tmp =0
        check_tmp =check1(x,l_s,l_k)
        if check_tmp == 1:
            break
        elif check_tmp  == 2:
            continue
        for y in range(l_k):
            check_tmp =check2(x,y,l_s,l_k)
            if check_tmp == 1:
              break
            elif check_tmp  == 2:
                continue
            for z in range(l_k):
                check_tmp =check3(x,y,z,l_s) 
                if check_tmp == 1:
                    break
#                print("x=",x,"y=",y,"z=",z)
                sum = x+y+z
                if l_s == sum:
                    l_combi +=1
                    
    return l_combi

def check1(x,s,k):
    if s<x:
        return 1
    if x+k*2 < s:
        return 2
    return 0

def check2(x,y,s,k):
    sum = x+y
    if s<sum:
        return 1
    if x+y+k < s:
        return 2
    return 0

def check3(x,y,z,s):
    sum = x+y+z
    if s<sum:
        return 1
    return 0    

k,s=nyu()
print(calc(k+1,s))









### FIXED CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    for x in range(l_k):
#        check_tmp =0
#        check_tmp =check1(x,l_s,l_k)
#        if check_tmp == 1:
#            break
#        elif check_tmp  == 2:
#            continue
        for y in range(l_k):
#            check_tmp =check2(x,y,l_s,l_k)
#            if check_tmp == 1:
#                break
#            elif check_tmp  == 2:
#                continue2
#            sum = x+y+l_k 
            sum = l_s- x-y 
            if 0<=sum and sum <= k:
#                print("x=",x,"y="   ,y) 
                l_combi +=1
    return l_combi

def check1(x,s,k):
    if s<x:
        return 1
    if x+(k-1)*2 < s:
        return 2
    return 0

def check2(x,y,s,k):
    sum = x+y
    if s<sum:
        return 1
    if x+y+k-1 < s:
       return 2
    return 0

def check3(x,y,z,s):
    sum = x+y+z
    if s<sum:
        return 1
    return 0    

def check_ini(k,s):
    if k*3 < s:
        return True
    return False


k,s=nyu()
if check_ini == True:
    print("0")
else :
    print(calc(k+1,s))
### BUGGY CODE ###

K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    i = 1
    W = 7 % K
    while True:
        if W % K == 0:
            print(i)
            break
        W += 7 * 10**i % K
        i += 1

### FIXED CODE ###

K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    
else:
    if K % 7 == 0:
        L = 9 * K // 7
    else:
        L = 9 * K
    n = 1
    P = 10 % L
    while True:
        if P == 1:
            print(n)
            break
        n += 1
        P = (10 * P) % L
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    heap = []
    for a in map(int, input().split()):
        heappush(heap, a)

    for _ in range(M):
        B, C = map(int, input().split())
        for _ in range(B):
            a = heappop(heap)
            if a < C:
                heappush(heap, C)
            else:
                heappush(heap, a)
                break

    return sum(heap)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    heap = []
    ans = 0
    for a in map(int, input().split()):
        heappush(heap, a)
        ans += a

    BC = []
    for _ in range(M):
        B, C = map(int, input().split())
        BC.append((B, C))

    BC = sorted(BC, key=lambda x: -x[1])
    for B, C in BC:
        for _ in range(B):
            a = heappop(heap)
            if a < C:
                heappush(heap, C)
                ans += C - a
            else:
                heappush(heap, a)
                break

    return ans


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

n = int(input())
ans = float('inf')
temp = 0
for i in range(1,n+1):
    if n%i == 0:
        temp = max(len(str(i)), len(str(n//i)))
        ans = min(temp, ans)
print(ans)

### FIXED CODE ###

n = int(input())
ans = float('inf')
temp = 0
for i in range(int(n**(1/2)), 0, -1):
    if n%i == 0:
        temp = max(i, n//i)
        ans = min(temp, ans)
print(len(str(ans)))
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)

n,k=mdata()
H=list(mdata())
d=[1e9]*n
d[0]=0
for i in range(1,n):
    for j in range(i-1,max(i-k-1,-1),-1):
        d[i]=min(d[i],d[j]+abs(H[i]-H[j]))
print(d[-1])


### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)

n,k=mdata()
H=list(mdata())
d=[1e9]*n
d[0]=0
for i in range(1,n):
    for j in range(i-1,max(i-k-1,-1),-1):
        d[i]=min(d[i],d[j]+abs(H[i]-H[j]))
print(d[-1])
### BUGGY CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)

dp = [["" for i in range(lt+1)] for j in range(ls+1)]



for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            if len(dp[i][j+1]) > len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
print(dp[ls][lt])



### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])
### BUGGY CODE ###

import collections

n,m=map(int,input().split())
a,b,c=[],[],[]
for i in range(m):
    A=list(map(int,input().split()))
    a.append(A)
for i in range(m):
    if a[i][1]==n:
        b.append(a[i][0])
    elif a[i][0]==1:
        c.append(a[i][1])
if len(b)>0:
    b=list(set(b))
    c=list(set(c))
    for i in b:
        for j in c:
            if i==j:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")


### FIXED CODE ###

import collections

n,m=map(int,input().split())
a,b,c=[],[],[]
for i in range(m):
    A=list(map(int,input().split()))
    a.append(A)
for i in range(m):
    if a[i][1]==n:
        b.append(a[i][0])
    elif a[i][0]==1:
        c.append(a[i][1])
if len(set(b)&set(c))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  s = input().strip()
  q = int(input())
  state = 1
  swap = [0, 2, 1]
  for _ in range(q):
    x = input().strip()
    if x == '1':
      state *= -1
    else:
      _, f, c = x.split(' ')
      f = int(f)
      if state == -1:
        f = swap[int(f)]
      if f == 1:
        s = c + s
      else:
        s += c
  if state == -1:
    s = s[::-1]
  print(s)


  pass

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  s = input().strip()
  q = int(input())
  state = 1
  swap = [0, 2, 1]
  ss = []
  es = []
  for _ in range(q):
    x = input().strip()
    if x == '1':
      state *= -1
    else:
      _, f, c = x.split(' ')
      f = int(f)
      if state == -1:
        f = swap[int(f)]
      if f == 1:
        ss.append(c)
      else:
        es.append(c)
  s = ''.join(ss[::-1]) + s + ''.join(es)
  if state == -1:
    s = s[::-1]
  print(s)

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# A.sort(reverse=True)
# B.sort(reverse=True)

rowrange = 0
colrange = 0
ans = 1
for i in reversed(range(1, N * M + 1)):
    r = i in A
    c = i in B
    if r is True and c is True:
        rowrange += 1
        colrange += 1
    elif r is True and c is False:
        rowrange += 1
        ans = (colrange * ans) % (10 ** 9 + 7)
    elif r is False and c is True:
        colrange += 1
        ans = (rowrange * ans) % (10 ** 9 + 7)
    else:
        ans = ((rowrange * colrange - (N * M - i)) * ans) % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# A.sort(reverse=True)
# B.sort(reverse=True)

rowrange = 0
colrange = 0
ans = 1
for i in reversed(range(1, N * M + 1)):
    r = i in A
    c = i in B
    if r is True and c is True:
        rowrange += 1
        colrange += 1
        A.remove(i)
        B.remove(i)
    elif r is True and c is False:
        rowrange += 1
        ans = (colrange * ans) % (10 ** 9 + 7)
        A.remove(i)
    elif r is False and c is True:
        colrange += 1
        ans = (rowrange * ans) % (10 ** 9 + 7)
        B.remove(i)
    else:
        ans = ((rowrange * colrange - (N * M - i)) * ans) % (10 ** 9 + 7)
print(ans)