Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = [0] * m
c = [0] * m
ans = 0
flag = False
for i in range(m):
    b[i], c[i] = map(int, input().split())

for _ in range(n):
    ans += max(a[-1], max(c))
    if flag == False:
        cnt = b[c.index(max(c))]
    if a[-1] > max(c):
        a.pop()
    else:
        flag = True
        cnt -= 1
        if cnt == 0:
            del b[c.index(max(c))]
            del c[c.index(max(c))]
            flag = False
            

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
l = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x:x[1], reverse=True)

res = 0
pos_1 = 0
pos_2 = 0
for _ in range(n):
    if pos_2 == m or a[pos_1] > l[pos_2][1]:
        res += a[pos_1]
        pos_1 += 1
    else:
        res += l[pos_2][1]
        l[pos_2][0] -= 1
        if l[pos_2][0] == 0:
            pos_2 += 1

print(res)
N = int(input())
a = [list(map(int, input().split())) for i in range(N)]
flag = 0

for i in range(N):
  dt = a[i+1][0]-a[i][0]
  dist = abs(a[i+1][1]-a[i][1])+abs(a[i+1][2]-a[i][2])
  if dt > dist:
    flag = flag +1
  else dt % 2 != dist % 2:
    flag = flag +1

print('Yes' if flag == 0 else 'No')    

### FIXED CODE ###

n = int(input())
t=[0]
x=[0]
y=[0]
for i in range(n):
    _t, _x, _y = map(int, input().split())
    t.append(_t)
    x.append(_x)
    y.append(_y)

flag = 0
for i in range(1,n+1):
    dt = t[i] - t[i-1]
    dx = x[i] - x[i-1]
    dy = y[i] - y[i-1]
    dist = abs(dx) + abs(dy)
    if dist > dt:
        flag = flag +1
    elif dist % 2 != dt % 2:
        flag = flag +1
else:
    print("Yes" if flag ==0 else "No")
n = (int)(input())

x = []
y = []
h = []

for _ in range(n):
    a, b, c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)

for i in range(0, 100+1):
    for j in range(0, 100+1):
        tmp = [h[k] + abs(x[k]-i) + abs(y[k]-j) for k in range(n)]
        tmp.remove(0)
        if tmp.count(tmp[0]) == len(tmp) and len(set(tmp)) == 1:
            print(i, j, (lambda x: x if x >= 0 else 0)(tmp[0]))
            exit()


### FIXED CODE ###

n = (int)(input())

x = []
y = []
h = []

for _ in range(n):
    a, b, c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)

f = False
for i in range(0, 100+1):
    for j in range(0, 100+1):
        for k in range(n):
            if h[k] != 0:
                ch = h[k] + abs(i-x[k]) + abs(j-y[k])
                break
        if all(max(ch-abs(i-x[k]) - abs(j-y[k]), 0) == h[k] for k in range(n)):
            print(i, j, ch)
            exit()
import numpy as np

N, Q = map(int, input().split())
S = input()
ac_array = np.zeros(N)
ans = []

for i in range(N):
    if S[i] == 'A' and S[i+1] == 'C':
        ac_array[i] += 1
        ac_array[i+1] += 1
print(ac_array)
q_list = np.zeros([Q, 2])
for q in range(Q):
    q_list[q, 0], q_list[q, 1] = map(int, input().split())
    ans.append(np.trunc(ac_array[int(q_list[q, 0]-1):int(q_list[q,1])].sum()/2))

for a in range(Q):
    print(int(ans[a]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)
ans = []

for i in range(N):
    t[i+1] += t[i] + ( 1 if S[i:i+2] == 'AC' else 0) 

for i in range(Q):
    l, r = map(int, input().split())
    ans.append(t[r-1] - t[l-1])
    
for i in range(Q):
    print(ans[i])
X=int(input())
import numpy as np
dp=[[False]*(X+1) for _ in range(X+1)]
dp[0][0]=True
for t in range(1,X+1):
  if dp[t-1][X-t]==True:
    ans = t
    break
  for x in range(0,X+1):
    if x>=t:
      dp[t][x]=dp[t-1][x-t]
    else:
      dp[t][x]=dp[t-1][x]
print(ans)

### FIXED CODE ###

X=int(input())
s=0
for t in range(X+1):
  s+=t
  if s>=X:
    print(t)
    break
A, P =map(int,input().split())

print(int((A*3+p)/2))

### FIXED CODE ###

A, P =map(int,input().split())
 
print(int((A*3+P)/2))
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)

u = []
v = []
c = []


def dfs(start, now, depth):
    if depth == 3:
        u.append(start)
        v.append(now)
        c.append(1)
        return

    for nxt in adj[now]:
        dfs(start, nxt, depth + 1)


for i in range(n):
    dfs(i, i, 0)

graph = csr_matrix((c, (u, v)), shape=(n, n))
dist = dijkstra(graph).astype(int)
ans = dist[s-1][t-1]
if ans < 0:
    ans = -1
print(ans)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

adj = [[] for _ in range(3 * n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v + n)
    adj[u + n].append(v + 2 * n)
    adj[u + 2 * n].append(v)


def bfs(s):
    q = deque([s])
    d = [-1] * (3 * n)
    d[s] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                q.append(v)

    return d


dist = bfs(s - 1)
ans = dist[t - 1]
print(ans // 3)
r=input(int())
g=input(int())

print(2*g-r)

### FIXED CODE ###

a=int(input())
b=int(input())


print(int(2*b-a))
s=input()
i=1
s0=s[0]
ct=1
while i<len(s)-1:
  if s0==s[i]:
    s0=s[i:i+2]
    i+=2
  else:
    s0=s[i]
    i+=1
  ct+=1
if i>len(s):
  print(ct)
elif s0==s[i]:
  print(ct)
else:
  print(ct+1)

### FIXED CODE ###

s=input()
i=1
s0=s[0]
ct=1
while i<len(s)-1:
  if s0==s[i]:
    s0=s[i:i+2]
    i+=2
  else:
    s0=s[i]
    i+=1
  ct+=1
if i>=len(s):
  print(ct)
elif s0==s[i]:
  print(ct)
else:
  print(ct+1)
x,y,z,k=map(int,input().split())
*a,=map(int,input().split())
*b,=map(int,input().split())
*c,=map(int,input().split())
 
def merge_sort(array):
    if len(array) <= 1:
        return array
    cnt=len(array)//2
    left=array[:cnt]
    right=array[cnt:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    array = [0]*3000
    l,r,ind=0,0,0
    while l < len(left) and r < len(right):
        if left[l] >= right[r]:
            array[ind]=left[l]
            l+=1
            ind+=1
        else:
            array[ind]=right[r]
            r+=1
            ind+=1
        if ind>=3000:
            return array
    if l < len(left):
        return array[:ind]+left[l:3000-ind+l]
    if r < len(right):
        return array[:ind]+right[r:3000-ind+r]

a=merge_sort(a)
b=merge_sort(b)
c=merge_sort(c)
l,r=[],[]
for i in a:
    for j in b:
    l.append(i+j)
l=merge_sort(l)
for i in l:
    for j in c:
    r.append(i+j)
r=merge_sort(r)
for i in range(k):
    print(r[i])

### FIXED CODE ###

x,y,z,q=map(int,input().split())
a=sorted(map(int,input().split()),reverse=True)
b=sorted(map(int,input().split()),reverse=True)
c=sorted(map(int,input().split()),reverse=True)
 
def bisect(l,r):
  cnt=(l+r)//2
  if cnt==l:
    return l-1+judge(l)
  if judge(cnt):
    return bisect(cnt+1,r)
  else:
    return bisect(l,cnt)
def judge(thr):
  m=0
  for i in range(x):
    for j in range(y):
      if i*j>q:
        break
      for k in range(z):
        if i*j*k>q or a[i]+b[j]+c[k]<thr:
          break
        m+=1
        if m>=q:
          return True
  return False
def make(thr):
  m=0
  l=[]
  for i in a:
    for j in b:
      for k in c:
        n=i+j+k
        if n<thr+1:
          break
        m+=1
        l+=[n]
  l.sort(reverse=True)
  return l+[thr]*(q-len(l))
thr=bisect(0,a[0]+b[0]+c[0]+1)
ans=make(thr)
for w in ans:
  print(w)
N = int(input())
a = map(int, input().split())

SUM = 0
for i in range(N):
  while a[i] >= 2 and a % 2 == 0:
    SUM += 1
    a[i] //= 2
    
print(SUM)






### FIXED CODE ###

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

SUM = 0
for i in range(N):
  while a[i] >= 2 and a[i] % 2 == 0:
    SUM += 1
    a[i] //= 2
    
print(SUM)
n, m = map(int, input().split())
k = m//n
ans = 0
for i in range(1, int(m**0.5)+1):
  if m%i == 0:
    if i <= k:
      if i <= k:
      ans = max(ans, i)
    if m//i <= k:
      ans = max(ans, m//i)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i == 0:
    print(i)
    break
N = int(input())
 
for i in range(1,10):
  for j in range(1,10):
    if i*j==N:
      break
  if i*j==N:
    print("Yes")
    break
  elif i==9 and i*j!=N:
    print("No")

### FIXED CODE ###

A,B = map(int,input().split())
if A>=10 or B>=10:
   print(-1)
else:
   print(A*B)
import math,bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,d,a = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()

#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        if (lst1[i][1]-r)/a%1==0:
            need = (lst1[i][1]-r)//a
        else:
            need = (lst1[i][1]-r)//a+1
        ans += need
        update(i,need*a)

print(ans)


### FIXED CODE ###

#n = int(input())
h,a = map(int,input().split())
#lst1 = list(map(int,input().split()))
import math
print(math.ceil(h/a))
import sys
S = input()
Q = int(input())
key = 1

for i in sys.stdin:
    if i[0] == '0':
        break

    if i[0] == '1':
        key = -key
    
    if key == 1:
        if i[2] == '1':
            S = i[4] + S
        else:
            S = S + i[4]

    else:
        if i[2] == '2':
            S = i[4] + S
        else:
            S = S + i[4]


print(S[::key])


### FIXED CODE ###

import sys
S = input()
Q = int(input())
key = 1

for i in sys.stdin:
    if i[0] == '0':
        break

    if i[0] == '1':
        key = -key
    
    elif key == 1:
        if i[2] == '1':
            S = i[4] + S
        else:
            S = S + i[4]

    else:
        if i[2] == '2':
            S = i[4] + S
        else:
            S = S + i[4]


print(S[::key])
N=int(input())
a =list(map(int,input().split()))
def myFunction(int i):
    if (i == N-2):
        print((a[i-1]+a[i])/2)
    a[i] = (a[i-1]+a[i])/2
    myFunction(i+1)    
a.sort()
myFunction(1)        

### FIXED CODE ###

a = int(input())
s= input()

if (a<3200):
    print('red')
else:
    print(s)
N,K=map(int, input().split())
td=[list(map(int,input().split())) for i in range(N)]
best=[0]*(N+1)
other=[]
from heapq import heappop,heappush
td.sort(key=lambda x: x[1],reverse=True)
shurui=0
for i in range(K):
    if best[td[i][0]]==0:
        best[td[i][0]]=td[i][1]
        shurui+=1
    elif best[td[i][0]]<td[i][1]:
        heappush(other,best[td[i][0]])
        best[td[i][0]]=td[i][1]
    else:
        heappush(other,td[i][1])

ans=sum(best)+sum(other)+shurui**2

for i in range(K,N):
    if best[td[i][0]]==0:
        best[td[i][0]]=td[i][1]
        shurui+=1
        heappop(other)
        ans=max(ans,sum(best)+sum(other)+shurui**2)

print(ans)


### FIXED CODE ###

N,K=map(int, input().split())
td=[list(map(int,input().split())) for i in range(N)]
best=[0]*(N+1)
other=[]
from heapq import heappop,heappush
td.sort(key=lambda x: x[1],reverse=True)
shurui=0
for i in range(K):
    if best[td[i][0]]==0:
        best[td[i][0]]=td[i][1]
        shurui+=1
    elif best[td[i][0]]<td[i][1]:
        heappush(other,best[td[i][0]])
        best[td[i][0]]=td[i][1]
    else:
        heappush(other,td[i][1])

sumbest=sum(best)
sumother=sum(other)
ans=sumbest+sumother+shurui**2

for i in range(K,N):
    if best[td[i][0]]==0 and len(other)>0:
        best[td[i][0]]=td[i][1]
        shurui+=1
        sumbest+=td[i][1]
        sumother-=heappop(other)
        ans=max(ans,sumbest+sumother+shurui**2)

print(ans)
from sympy import nextprime
x = int(input())
print(nextprime(x-1))

### FIXED CODE ###

x = int(input())
for i in range(x,10**5 +4):
    for p in range(2, int(x**(1/2)+1)):
        if i%p == 0 :
            break
    else:
        print(i)
        break
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

light = [0] * 4 * (W + 1) * (H + 1)

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = (W + 1) * h + 4 * w
            light[(W + 1) * (h + 1) + 4 * w + 1] = light[here + 1] + 1
            light[(W + 1) * h + 4 * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = (W + 1) * h + 4 * w
            light[(W + 1) * (h - 1) + 4 * w + 0] = light[here + 0] + 1
            light[(W + 1) * h + 4 * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, light[here: here + 4])

print(ans)


### FIXED CODE ###

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

light = [0] * 4 * (W + 1) * (H + 1)

row = 4 * (W + 1)
col = 4

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h + 1) + col * w + 1] = light[here + 1] + 1
            light[row * h + col * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h - 1) + col * w + 0] = light[here + 0] + 1
            light[row * h + col * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, sum(light[here: here + 4]) + 1)

print(ans)
n, h, w = map(int, input().split())
tup_list = []
for i in n:
    tup_list.append((input().split()))
count = 0
for tuple in tup_list:
    if tuple[0] > h and tuple[1] > w:
        count += 1
print(count)


### FIXED CODE ###

nhw_list = list(map(int, input().split()))
tup_list = []
for i in range(nhw_list[0]):
    tup_list.append(list(map(int, input().split())))
count = 0
for tuple in tup_list:
    if tuple[0] >= nhw_list[1] and tuple[1] >= nhw_list[2]:
        count += 1
print(count)
s=input()
a=[]
b=[]
now=True
q=int(input())
for i in range(q):
    x=list(input().split())
    if x[0]=="1":
        now=not now
    else:
        if now and x[1]=="2" or not now and x[1]=="1":
            b.append(x[2])
        else:
            a.append(x[2])
if now:
    print(*a[::-1],s,*b,sep="")
else:
    print(*b[::-1],s[::-1],*a,sep="")

### FIXED CODE ###

'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
s=input()
a=[]
b=[]
now=1
q=int(input())
for i in range(q):
    x=list(input().split())
    if x[0]=="1":
        now*=-1
    else:
        if now==1 and x[1]=="2" or now==-1 and x[1]=="1":
            b.append(x[2])
        else:
            a.append(x[2])
if now==-1:
    ans=b[::-1]+list(s[::-1])+a
    print(*ans,sep="")
else:
    ans=a[::-1]+list(s)+b
    print(*ans,sep="")
S = input()
if len(S) < 26:
    for i in range(26):
        c = chr(i + ord('a'))
        if c not in S:
            print(S + c)
            break
else:
    tmp = 26
    for i in range(len(S) - 1, 0, -1):
        if ord(S[i - 1]) < ord(S[i]):
            break
        tmp = i
    tmp -= 1
    if tmp == 0:
        print(-1)
    c = ord(S[:tmp][-1])
    suf = S[tmp:]
    print(S[:tmp - 1] + chr(min([ord(si) for si in suf if ord(si) > c])))


### FIXED CODE ###

S = input()
if len(S) < 26:
    for i in range(26):
        c = chr(i + ord('a'))
        if c not in S:
            print(S + c)
            break
else:
    tmp = 26
    for i in range(len(S) - 1, 0, -1):
        if ord(S[i - 1]) < ord(S[i]):
            break
        tmp = i
    tmp -= 1
    if tmp == 0:
        print(-1)
    else:
        c = ord(S[:tmp][-1])
        suf = S[tmp:]
        print(S[:tmp - 1] + chr(min([ord(si) for si in suf if ord(si) > c])))
#2-1-1 #ABC045C
s=input()
lenth=len(s)
kugiri=set()
def roop(before,now,kugiri):
    if now==lenth:
        kugiri|={before,}
        return kugiri
    kugiri = roop(before+(0,),now+1,kugiri)
    kugiri = roop(before+(1,),now+1,kugiri)
    return kugiri
kugiri = roop((0,),2,kugiri)
kugiri = roop((1,),2,kugiri)
def calc(ans,kugiri,s):
    test=s
    now=test[0]
    test=test[1:]
    for i in range(len(s)-1):
        k=kugiri[i]
        if k==0:
            now+=test[0]
        elif k==1:
            ans+=int(now)
            now=test[0]
        test=test[1:]
        if i==len(s)-2:ans+=int(now)
    return ans
            
ans=0
for i in kugiri:
    ans=calc(ans,i,s)
print(ans)

### FIXED CODE ###

#2-1-1 #ARC061C
s=input()
lenth=len(s)
kugiri=set()
def roop(before,now,kugiri):
    if now==lenth:
        kugiri|={before,}
        return kugiri
    kugiri = roop(before+(0,),now+1,kugiri)
    kugiri = roop(before+(1,),now+1,kugiri)
    return kugiri


def calc(ans,kugiri,s):
    test=s
    now=test[0]
    test=test[1:]
    for i in range(len(s)-1):
        k=kugiri[i]
        if k==0:
            now+=test[0]
        elif k==1:
            ans+=int(now)
            now=test[0]
        test=test[1:]
        if i==len(s)-2:ans+=int(now)
    return ans
            
ans=0
if len(s)!=1:
    kugiri = roop((0,),2,kugiri)
    kugiri = roop((1,),2,kugiri)
    for i in kugiri:
        ans=calc(ans,i,s)
    print(ans)
elif len(s)==1:print(int(s))
n = int(raw_input())

for i in range(n):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float, raw_input().split())
    a = (y2-y1)/(x2-x1)
    c = (y4-y3)/(x3-x1)
    if a == c:
        print "YES"
    else:
        print "NO"

### FIXED CODE ###

n = int(raw_input())

for i in range(n):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float, raw_input().split())
    if abs((y4-y3)*(x2-x1)-(y2-y1)*(x4-x3)) < 1e-10:
        print "YES"
    else:
        print "NO"
def count_max(road):
    num = len(road)
    used = [False for i in range(num)]
    res = 0
    for i in range(num):
        if used[i]:
            continue
        used[i] = True
        line = road[i][:]
        for j in line:
            used[j] = True
        count = 1 + len(line)
        while line:
            now_point = line.pop()
            next = [j for j in road[now_point] if not used[j]]
            for j in next:
                used[j] = True
            count += len(next)
            line += next
        res += count * (count - 1) // 2
    return res


def getparent(parent, place):
    my_parent = parent[place]
    if my_parent == place:
        return place
    parent[place] = getparent(parent, my_parent)
    return parent[place]


def main():
    ans = []
    n, m = list(map(int, input().split()))
    broad = [[] for i in range(n)]
    b_pair = []
    parent = [i for i in range(n)]
    parent_sum = [1 for i in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        broad[a].append(b)
        broad[b].append(a)
        b_pair.append((a, b))
    sum_count = count_max(broad)
    ans.append(sum_count)
    b_pair.reverse()
    b_pair.pop()
    for p, q in b_pair:
        np, nq = getparent(parent, p), getparent(parent, q)
        if np != nq:
            sum_count -= parent_sum[np] * parent_sum[nq]
            parent_sum[np] += parent_sum[nq]
            parent[nq] = np
        ans.append(sum_count)
    ans.reverse()
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def getparent(parent, place):
    childrens = [place]
    while place != parent[place]:
        place = parent[place]
        childrens.append(place)
    for i in childrens:
        parent[i] = place
    return place


def main():
    ans = []
    n, m = list(map(int, input().split()))
    pairs = []
    parent = [i for i in range(n)]
    parent_sum = [1 for _ in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        pairs.append((a - 1, b - 1))
    sum_count = n * (n - 1) // 2
    ans.append(sum_count)
    for p, q in reversed(pairs[1:]):
        np, nq = getparent(parent, p), getparent(parent, q)
        if np != nq:
            sum_count -= parent_sum[np] * parent_sum[nq]
            parent_sum[np] += parent_sum[nq]
            parent[nq] = np
        ans.append(sum_count)
    ans.reverse()
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()
S= input()
count=0
if S[0]!='A':
  print('WA')
  return
S.lower(0)
for i in range(3,len(S)-1):
  if S[i]=='C':
    count+=1
    S.lower(i)
if count==1 && S.islower():
  print('AC')

### FIXED CODE ###

s = input()
flag = False

if s[0]=="A":
	if s[2:-1].count("C")==1:
		if (s[1:s.index("C")].islower() and s[s.index("C")+1:].islower()):
			flag = True
print("AC" if flag else "WA")
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
if oks[1]:
    dp[1] = 1
if oks[2]:
    print("a")
    dp[2] = 1
for i in range(3, N+1):
    if oks[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % (1e9+7))


print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
lst=[0]
now=0
memo=0
town=[0]*n
town[0]=1
for i in range(k):
	now=a[now]
	if town[now]==1:
		memo=now
		break
	lst.append(now)
	town[now]=1
i=a.index(memo)
l=len(lst)
if memo!=0:
	lst=lst[i:]
print(lst[(k-l)%len(lst)]+1)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
lst=[0]
now=0
memo=0
town=[0]*n
town[0]=1
b=0
for i in range(k):
	now=a[now]
	if town[now]==1:
		memo=now
		b=1
		break
	lst.append(now)
	town[now]=1
if b==1:
	i=lst.index(memo)
	l=len(lst)
	if memo!=0:
		lst=lst[i:]
		l-=len(lst)
		print(lst[(k-l)%len(lst)]+1)
	else:
		print(lst[k%l]+1)
else:
	print(now+1)
a = input()
print(a**3)

### FIXED CODE ###

a=int(input())
print(a**3)