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

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

ans = N
N = N - X
while N:
  if X < N:
    ans += X * 2
    N, X = X, N - X
  else:
    d, m = divmod(N, X)
    ans += d * X + m * 2
    N, X = m, X - m

print(ans)

### FIXED CODE ###

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

ans = N
N, X = X, N - X
while N and X:
  if X > N:
    d, m = divmod(X, N)
    if m == 0:
      ans += (d * 2 - 1) * N
    else:
      ans += d * 2 * N
    N, X = N, m
  else:
    d, m = divmod(N, X)
    if m == 0:
      ans += (d * 2 - 1) * X
    else:
      ans += d * 2 * X + m * 2
    N, X = m, X - m

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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)

				

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

N, M = LI()
S = input()
T = input()

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
#  XS = ['X' for i in range(L+1)]
#  XT = ['X' for i in range(L+1)]
XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    #  print(key, value)
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()
#  print(XS, XT)
#  for i in range(0, L+1):
#      if XS[i] != 'X' and XT[i] != 'X':
#          if XT[i] != XS[i]:
#              print(-1)
#              exit()
print(L)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
nr=n//r
ng=n//g
nb=n//b
ans=0
lst=[b*k for k in range(nb+1)]
l=len(lst)
import bisect
for i in range(nr+1):
  for j in range(ng+1):
    res=n-i*r-j*g
    idx=bisect.bisect_left(lst,res)
    if idx<l and lst[idx]==res:
      ans+=1
        
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
nr=n//r
ans=0
for i in range(nr+1):
  ng=(n-i*r)//g
  for j in range(ng+1):
    res=n-r*i-g*j
    if res%b==0:
      ans+=1
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s, *a = map(int, read().split())
dp = [0] * (s + 1)
dp[0] = 1
mod = 998244353
for aa in a:
    for j in range(s, -1, -1):
        ss = j + aa
        if ss <= s:
            dp[ss] += dp[j]
            dp[ss] %= mod
        dp[j] *= 2
        dp[j] %= mod
print(dp[-1])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s, *a = map(int, read().split())
dp = [0] * (s + 1)
dp[0] = 1
mod = 998244353
for aa in a:
    for j in range(s, -1, -1):
        ss = j + aa
        if ss <= s:
            dp[ss] += dp[j]
            dp[ss] %= mod
        dp[j] *= 2
        dp[j] %= mod
print(dp[-1])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)

p = [0 for _ in range(x * y)]
t = 0
for ai in a:
    for bi in b:
        p[t] = ai + bi
        t += 1
p.sort(reverse=True)
q = [0 for _ in range(k * z)]
t = 0
for pi in p[:k]:
    for ci in c[:k]:
        q[t] = pi + ci
        t += 1
q.sort(reverse=True)
for qi in q[:k]:
    print(qi)


### FIXED CODE ###

x, y, z, kk = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

p = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i + 1) * (j + 1) * (k + 1) <= kk:
                p.append(a[i] + b[j] + c[k])
            else:
                break
p.sort(reverse=True)
for i in range(kk):
    print(p[i])
### BUGGY CODE ###

import string

ALPHABETS = string.ascii_lowercase


def is_avairable(a):
    return bin(a).count('1') <= 1

s = input()
N = len(s)
a = [0] * (N + 1)
for i, c in enumerate(s):
    idx = ALPHABETS.index(c)
    a[i+1] = a[i] ^ (2 ** idx)

opt = [0] * (N + 1)
dp = [2 * (10 ** 5) + 1] * (2 ** 26)
dp[0] = 0
for i in range(1, N + 1):
    ns = [dp[a[i] ^ 2 ** j] if not j == -1 else dp[a[i] ^ 0] for j in range(-1, 26)]
    mn = min(ns)
    opt[i] = mn + 1
    if dp[a[i]] > opt[i]:
        dp[a[i]] = opt[i]

print(opt[N])


### FIXED CODE ###

s = input()
N = len(s)
a = 0
dp = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]

for c in s:
    a = a ^ bits[ord(c)-ord('a')]
    dp[a] = min(dp.get(a, N), min([dp.get(a ^ bit, N) for bit in bits]) + 1)

print(dp[a] if dp[a] != 0 else 1)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list( map(int,input().split()) )

dp = [0] * n
dp[0] = 0

for i in range(1,n):
  s = max(0,i-k)
  x = [ dp[j] + abs(h[j] - h[i]) for j in range(s,i) ]
  dp[i] = min([ dp[j] + abs(h[j] - h[i]) for j in range(s,i) ])

print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list( map(int,input().split()) )

dp = [0] * n
dp[0] = 0

for i in range(1,n):
  s = max(0,i-k)
  x = [ dp[j] + abs(h[j] - h[i]) for j in range(s,i) ]
  dp[i] = min([ dp[j] + abs(h[j] - h[i]) for j in range(s,i) ])

print(dp[n-1])
### BUGGY CODE ###

from functools import reduce
INF = int(1e18)


def main():
    N, *A = map(int, open(0).read().split())
    ans = reduce(lambda Ai, x: Ai * x, A)
    print(-1 if INF < ans else ans)
    return


main()


### FIXED CODE ###

INF = int(1e18)


def main():
    N, *A, = map(int, open(0).read().split())
    ans = 1
    if 0 in A:
        print(0)
        return
    for a in A:
        ans *= a
        if INF < ans:
            print(-1)
            break
    else:
        print(ans)
    return


main()
### BUGGY CODE ###


N=int(input())
A=list(map(int,input().split()))
setA=set(A)
number1={}#-1
number2={}
ans={}
for i in setA:
    tmp=A.count(i) - 1
    souwa=(tmp - 1)*(tmp)//2
    number1[i]=souwa
    souwa=tmp*(tmp+1)//2
    number2[i]=souwa
t=sum(number2.values())
for a in setA:
    total=number1[a]
    total+=t
    total-=number2[a]
    ans[a]=total

for a in A:
    print(ans[a])






### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
d=Counter(A)
dic={}
total=0
for item in d.items():
    counter=item[1]
    s1=(counter - 1)*(counter - 2)/2 #1個少ない
    s2=(counter)*(counter - 1)/2
    dic[item[0]]=int(s1 - s2)
    total+=int(s2)

for a in A:
    print(total + dic[a])
### BUGGY CODE ###

def main():
  import collections
  s = list(map(int,input()))
  r = []
  x = 0
  for i in range(len(s)):
    x += s[-i-1]*(10**i)
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

### FIXED CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

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

#logging.debug("デバッグスタート") #
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] != s[j]:
            if (s[i] == "R" and s[j]=="G") or (s[i] == "G" and s[j]=="R"):
                ans += s[j + 1 :].count("B")
                if (j - i + j) < n:
                    if s[j - i + j] == "B":
                        ans -= 1
                    continue
            if (s[i] == "R" and s[j]=="B") or (s[i] == "B" and s[j]=="R"):
                ans += s[j + 1 :].count("G")
                if (j - i + j) < n:
                    if s[j - i + j] == "G":
                        ans -= 1
                    continue
            if (s[i] == "B" and s[j]=="G") or (s[i] == "G" and s[j]=="B"):
                ans += s[j + 1 :].count("R")
                if (j - i + j) < n:
                    if s[j - i + j] == "R":
                        ans -= 1
                    continue

print(ans)

### FIXED CODE ###

N = int(input())  #数字
S = list(input()) #スペース抜きの複数行,１文字ずつ

cou = 0

for i in range(0,N):
    j = 1
    while i + (2 * j) <= N-1:
        if S[i] != S[i + j] and S[i + j] != S[i + (2*j)] and S[i] != S[i + (2*j)]:
            cou += 1
        j += 1

print(S.count("R")*S.count("G")*S.count("B")-cou)
### BUGGY CODE ###

N = int(input())
edge = [[] for _ in range(N + 1)]
E = [-1] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))

cmax = max(len(e) for e in edge)
cand = set(i for i in range(cmax))
seenV = [-1] * (N + 1)
seenE = [-1] * N
node = [(1, cand)]
seenV[1] = 1
while node:
    s, color = node.pop()
    x = 0
    for t, i in edge[s]:
        if seenV[t] != -1:
            continue
        if seenE[i] != -1:
            continue
        seenV[t] = 1
        c = list(color)[x]
        seenE[i] = c
        node.append((t, cand - {c}))
        x += 1

print(cmax)
for i in range(N - 1):
    print(seenE[i]+1)

### FIXED CODE ###

from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    edge.append((a, b))


# serch max number of color
for i in range(n):
    if i == 0:
        color = len(tree[i])
    else:
        color = max(color, len(tree[i])+1)

upper = [0 for _ in range(n)]

for i in range(n):
    if not tree[i]:
        continue

    top = upper[i]
    tmp = tree[i].copy()
    cnt = 1
    while tmp:
        if cnt == top:
            cnt += 1
        upper[tmp.pop()] = cnt
        cnt += 1

ans = []
for x, y in edge:
    ans.append(upper[y])
print(color)
print(*ans, sep="\n")
### BUGGY CODE ###

"""
import sys
input = sys.stdin.readline
#"""

N=int(input())
A = [list(map(int,input().split())) for _ in [0]*N]

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    a0 = B[0]-1
    k1 = (i,a0) if i<a0 else (a0,i)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
### BUGGY CODE ###

n = int(input())
ans = [0]*n

for l in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      for k in range(1,n+1):
        if i**2 + j**2 + k**2 + i*j + j*k + k*i == l:
          ans[(l-1)] += 1
        elif i**2 + j**2 + k**2 + i*j + j*k + k*i > l:
          break      
  print(ans[(l-1)])

### FIXED CODE ###

n = int(input())
ans = [0]*n

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      l = i**2 + j**2 + k**2 + i*j + j*k + k*i
      if l <= n:
        ans[l-1] += 1
      
for m in range(n): 
  print(ans[m])
### BUGGY CODE ###

h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+max(l)[0])
dp[0]=0
for i in range(1,len(dp)):
  for a,b in l:
    if i-a>=0:
      dp[i]=min(dp[i],dp[i-a]+b)
print(min(dp[h:]))

### FIXED CODE ###

h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+max(l)[0])
dp[0]=0
for i in range(1,len(dp)):
  for a,b in l:
    if i-a>=0:
      dp[i]=min(dp[i],dp[i-a]+b)
print(min(dp[h:]))
### BUGGY CODE ###

n,k = map(int,input().split())
l = []
a = list(map(int,input().split()))
for i in range(len(a)):
  for j in range(len(a)-i):
    l.append(sum(a[j:j+i+1]))
m = len(bin(sum(a)))-2
x = 0
for i in range(m-1,-1,-1):
  c = 0
  cu = 2**i
  for j in l:
    if x+cu & j == x+cu:
      c += 1
    if c == k:
      x += cu
      break
print(x)

### FIXED CODE ###

n,k = map(int,input().split())
l = []
a = list(map(int,input().split()))
for i in range(len(a)):
  c = 0
  for j in range(len(a)-i):
    c += a[i+j]
    l.append(c)
m = len(bin(sum(a)))-2
x = 0
for i in range(m-1,-1,-1):
  c = 0
  cu = 2**i
  for j in l:
    if x+cu & j == x+cu:
      c += 1
    if c == k:
      x += cu
      break
print(x)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    for a in A:
        ans += D // a
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce


def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    D %= MOD
    for a in A:
        ans += D * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


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

N = int(input())
A = list(map(int,input().split(" ")))
total = 1

for i in A:
  total = total * i
if total > 10**18:
  print("-1")
else:
  print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split(" ")))
total = 1
A.sort()

for i in A:
  if i == 0:
    total = 0
    break
  elif total > 10**18:
    break
  total = total * i
if total > 10**18:
  print(-1)
else:
  print(total)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.append(0)
for i in range(0, N):
    cost = 0
    pos = 0
    for p in range(0, N+1):
        if p != i:
            cost += abs(pos - A[p])
            pos = A[p]
    print(cost)


### FIXED CODE ###

N = int(input())
A = [0] + [int(i) for i in input().split()] + [0]

cost = 0
pos = 0
for p in range(0, len(A)):
    cost += abs(pos - A[p])
    pos = A[p]

for i in range(1, len(A)-1):
    n_cost = 0
    if A[i-1] <= A[i] and A[i] <= A[i + 1]:
        n_cost = cost
    elif A[i] <= A[i - 1] and A[i] <= A[i + 1]:
        n_cost = cost - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1])
    elif A[i] >= A[i - 1] and A[i] >= A[i + 1]:
        n_cost = cost - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1])
    elif A[i-1] >= A[i] and A[i] >= A[i + 1]:
        n_cost = cost

    print(n_cost)
### BUGGY CODE ###

S = list(input())
Q = int(input())
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        S = S[::-1]
    elif int(query[0]) == 2:
        if int(query[1]) == 1:
            S.insert(0,query[2])
        elif int(query[1]) == 2:
            S.append(query[2])
print(*S ,sep='')

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
reversecount = 0
d = deque(S)
for x in query:
    if int(x[0]) == 1:
        reversecount += 1
    else:
        if (int(x[1]) == 1 and (reversecount % 2 == 0)) or (int(x[1]) == 2 and (reversecount % 2 == 1)):
            d.appendleft(x[2])
        else:
            d.append(x[2])
if reversecount % 2 == 1:
    d.reverse()
print(*d, sep='')
### BUGGY CODE ###

inp = list(map(int, input().split(" ")))
N, K = inp[0], inp[1]
h_arr = list(map(int, input().split(" ")))
dp = [0 for _ in range(N)]

for i in range(1, N):
	dp[i] = min([abs(h_arr[i]-h_arr[j]) + dp[j] for j in range(max(i-K, 0), i)])
print(dp[-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

l = int(input())
sum = 0
c = 0

for i in range(1,l):
  for ii in range(1,l):
    sum = i * ii
    if sum >= l:
      break
    else:
      c+=1

print(c)

### FIXED CODE ###

l = int(input())
sum = 0
c = 0

for i in range(1,l):
  for ii in range(i,l):
    sum = i * ii
    if sum >= l:
      break
    else:
      if i != ii:
        c+=2
      else:
        c+=1

print(c)
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

def func(v,c):
    if nodes_color[v] == c:
        return True
    if nodes_color[v] == -c:
        return False
    
    if nodes_color[v] == 0:
        nodes_color[v] = c
    for node in l[v]:
        if not func(node, -c):
            return False
    
    return True

chk = func(1,1)

if chk:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))
### BUGGY CODE ###

S=input()
N=int(input())
for i in range(N):
  A=list(map(str,input().split()))
  if A[0]=='1':
     S=S[::-1]
  else:
     if A[1]=='1':
       S=A[2]+S
     if A[1]=='2':
       S=S+A[2]
print(S)


### FIXED CODE ###

from collections import deque
S=input()
N=int(input())
q=deque([S[i] for i in range(len(S))])

c=0
for i in range(N):
  A=list(map(str,input().split()))
  if A[0]=='1':
     c+=1
     c%=2
  else:
     if (c+int(A[1]))%2==1:
       q.appendleft(A[2])
     if (c+int(A[1]))%2==0:
       q.append(A[2])
s=''
if c==0:
  for i in range(len(q)):
    r=q.popleft()
    s+=r
if c==1:
  for i in range(len(q)):
    d=q.pop()
    s+=d
print(s)