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

S=list(input())
q=int(input())
Q=[input().split() for i in range(q)]

reverse=0
for i in range(q):
    if Q[i][0]=="1":
        reverse+=1
    elif Q[i][0]=="2" and reverse%2==0:
        if Q[i][1]=="1":
            S.insert(0,Q[i][2])
        elif Q[i][1]=="2":
            S.append(Q[i][2])
    elif Q[i][0]=="2" and reverse%2==1:
        if Q[i][1]=="2":
            S.insert(0,Q[i][2])
        elif Q[i][1]=="1":
            S.append(Q[i][2])
if reverse%2==1:
    S.reverse()
for i in S:
    print(i,end="")

### FIXED CODE ###

S=list(input())
q=int(input())
Q=[input().split() for i in range(q)]

reverse=0
Top=[]
Bottom=[]
for i in range(q):
    if Q[i][0]=="1":
        reverse+=1
    elif Q[i][0]=="2" and reverse%2==0:
        if Q[i][1]=="1":
            Top.append(Q[i][2])
        elif Q[i][1]=="2":
            Bottom.append(Q[i][2])
    elif Q[i][0]=="2" and reverse%2==1:
        if Q[i][1]=="2":
            Top.append(Q[i][2])
        elif Q[i][1]=="1":
            Bottom.append(Q[i][2])
if reverse%2==1:
    Top.reverse()
    SS=Top+S+Bottom
    SS.reverse()
elif reverse%2==0:
    Top.reverse()
    SS=Top+S+Bottom
for i in SS:
    print(i,end="")
### BUGGY CODE ###

N, M = [int(nm) for nm in input().split()]
A = []
for m in range(M):
  A.append(int(input()))

mod = 10**9 + 7

if N == 1:
  print(1)
else:
  i1 = 1
  if 1 in A:
    i2 = 0
  else:
    i2 = 1
  for n in range(2, N+1):
    i3 = (i1 + i2) % mod
    if n in A:
      i3 = 0
    i1, i2 = i2, i3
  ans = i3
  print(ans)

### FIXED CODE ###

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # M > 0:
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: # n == a:
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    while M > 0:
        A.sort()
        A[-1] //= 2
        M -= 1
    print(sum(A))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


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

from functools import reduce
# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

def lcm_list(numbers):
    return reduce(lcm, numbers)

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

lcm_ = lcm_list(a)
b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
print(ans%MOD)


### FIXED CODE ###

MAX = 1000001

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict()

# function to return a^n

def power(a, n):

    if n == 0:
        return 1
    p = power(a, n // 2) % mod
    p = (p * p) % mod

    if n & 1:
        p = (p * a) % mod
    return p

# function to find the smallest prime
# factors of numbers upto MAX


def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

# function to return the LCM modulo M


def lcmModuloM(arr, n):

    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:

        # LCM is product of primes to their
        # higest powers modulo M
        ans = (ans * power(i, max_map[i])) % mod
    return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)


def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

# Driver code
sieve()

# python > pypy
MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n, h = map(int, input().split())
	if n == 0: break
	f = [[[0 for k in range(3)] for c in range(500)] for r in range(500)]
	ans = n**3
	for i in range(h):
		c, a, b = input().split()
		a, b = int(a)-1, int(b)-1
		ans -= n
		if c == "xy":
			f[a][b][0] = 1
			ans += sum([(f[a][j][1] | f[a][j][2]) for j in range(n)])
		elif c == "xz":
			f[a][b][1] = 1
			ans += sum([(f[a][j][0] | f[i][b][2]) for j in range(n)])
		else:
			f[a][b][2] = 1
			ans += sum([(f[j][a][0] | f[j][b][1]) for j in range(n)])
	print(ans)


### FIXED CODE ###

# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

# n <= 500,  2^9 = 512
while True:
	n, h = map(int, input().split())
	if n == 0: break
	ans = []
	for i in range(h):
		s = input()
		c = s[:2]
		a, b = s[3:].split()
		a, b = int(a)-1, int(b)-1
		if c == "xy":
			k = a+(b<<9)
			ans += [k+(z<<18) for z in range(n)]
		elif c == "xz":
			k = a+(b<<18)
			ans += [k+(y<<9) for y in range(n)]
		else:
			k = (a<<9)+(b<<18)
			ans += [k+x for x in range(n)]
	print(n**3-len(set(ans)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod=10**9+7

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y
            w=w*(x+y)

        return b%mod,w%mod

print(sum(ANS(1))%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod=10**9+7

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y%mod
            w=w*(x+y)%mod

        return b,w

print(sum(ANS(1))%mod)
### BUGGY CODE ###



def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # どうやってxを決めるのか。
    N = int(input())
    a = list(map(int, input().split()))
    range_N = range(N)
    max_counter = 0
    set_a = set(a)
    for i in set_a:
        X = i
        tmp_count = 0
        for j in a:
            if abs(j - X) <= 1:
                tmp_count += 1

        if tmp_count > max_counter:
            max_counter = tmp_count

    print(max_counter)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

N=int(input())
A=list(map(int,input().split()))
c=i=0
j=1
while i<N:
  x=sum(A[i:j])
  if x==0:
    c+=1
    j+=1
  else:
    j+=1
  if j==N+1:
    i+=1
    j=i+1
print(c)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
b=ans=0
c=collections.Counter([0])
for a in A:
  b+=a
  ans+=c[b]
  c[b]+=1
print(ans)
### BUGGY CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0

for i in range(n):
    baes = p[i]
    flag = True
    for j in range(i):
        if p[i] > p[j]:
            flag = False
            break

    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 1
base = p[0]

for i in range(1, n):
    if p[i] < base:
        ans += 1
        base = p[i]

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

s = list(input().strip())
K = int(input())
C = {}
for i in range(len(s)):
    if s[i] not in C:
        C[s[i]] = []
    C[s[i]].append(i)
D = set()
for a in C:
    for i in C[a]:
        x=s[i]
        D.add(x)
        for j in range(i+1,len(s)):
            x += s[j]
            D.add(x)
D = sorted(list(D))
print(D[K-1])

### FIXED CODE ###

S = input().strip()
N = len(S)
K = int(input())
A = []
for k in range(1,min(6,N+1)):
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in A:
            A.append(x)
A = sorted(A)
print(A[K-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

counter = 0
for r in range(N + 1):
    for g in range(N + 1 - (r * R)):
        w_b_sum = N - ((R * r) + (G * g))

        if w_b_sum % B == 0 and w_b_sum >= 0 and w_b_sum == N - ((R * r) + (G * g)):
            # print(r, g, (w_b_sum // B))
            counter += 1
print(counter)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

counter = 0
for r in range((N // R) + 1):
    for g in range(((N - (r * R)) // G) + 1):
        w_b_sum = N - ((R * r) + (G * g))

        if w_b_sum % B == 0 and w_b_sum >= 0:
            # print(r, g, (w_b_sum // B))
            counter += 1
print(counter)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int,input().split()))
output = 1
for i in range(N):
    output *= A_list[i]
if (output > 10 ** 18):
    print(-1)
else:
    print(output)

### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
output = 1
flug = 0

if 0 in A_list:
    print(0)
    flug = 1
if flug != 1:
    for i in range(N):
        output *= A_list[i]
        
        if (output > 10 ** 18):
            print(-1)
            flug = 1
            break
if(flug != 1):
    print(output)
### BUGGY CODE ###

N=int(input())
cnt=0

for i in range(1, N+1):
    i=str(i)
    if "1" in i or "2" in i or "4" in i or "6" in i or "8" in i or "9" in i or "0" in i:
        continue
    elif "3" in i and "5" in i and "7" in i:
        cnt+=1

print(cnt)

### FIXED CODE ###

n = int(input())
def f(s):
  if int(s) > n:
    return 0 #再帰終了
  if s.count("3") > 0 and s.count("5") > 0 and s.count("7") > 0:
  	cnt = 1
  else:
  	cnt = 0
  cnt += f(s + "3")
  cnt += f(s + "5")
  cnt += f(s + "7")
  return cnt
  
result = f("0")
print(result)
### BUGGY CODE ###

a, b = map(int, input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def common_divisors(k,j):
  c = make_divisors(k) + make_divisors(j)
  return [x for x in set(c) if c.count(x) > 1]
  
kouyakusuu = common_divisors(a,b)
count = 0
for k in kouyakusuu:
  if len(make_divisors(k)) == 1 or make_divisors(k)==[1,k]:      
   	count+=1

print(count)


### FIXED CODE ###

a, b = map(int, input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def common_divisors(k,j):
  c = make_divisors(k) + make_divisors(j)
  return [x for x in set(c) if c.count(x) > 1]

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)
    return fct
  
kouyakusuu = common_divisors(a,b)

aa=factorize(a)
bb=factorize(b)
l = list(set(aa))+list(set(bb))
ll = [x for x in set(l) if l.count(x) > 1]

print(len(ll)+1)
### BUGGY CODE ###

a,b,x = map(int,input().split())
count = 0

for i in range(a,b+1):
    if i % x == 0:
        count += 1
    else:
        pass

print(count)

### FIXED CODE ###

a,b,x = map(int,input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for p in range(1,k+1):
            ans += gcd(i,j,p)
print(ans)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(i,k+1):
        for p in range(j,k+1):
            if (i!=j) and (j!=p) and (i!=p):
                #print(i,j,p, 'pattern3')
                ans += gcd(i,j,p) * 6
            elif (i==j) and (j==p):
                #print(i,j,p, 'pattern1')
                ans += gcd(i,j,p)
            else:
                #elif (i==j) or (j==k) or (i==k):
                #print(i,j,p, 'pattern2')
                ans += gcd(i,j,p) * 3

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

from sys import stdin

def num():
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] == float('inf'):
            continue
        else:
            for j in magic:
                if i-j[0] < 0:
                    if ans[0] > ans[i]+j[1]:
                        ans[0] = ans[i]+j[1]
                elif ans[i-j[0]] > ans[i]+j[1]:
                    ans[i-j[0]] = ans[i]+j[1]
    return ans[0]
print(num())




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

import sys

input=sys.stdin.readline

R,C,K=map(int,input().split())
item={}
for i in range(K):
    r,c,v=map(int,input().split())
    item[r-1,c-1]=0
    item[r-1,c-1]=v

dp=[[0 for i in range(3)] for j in range(C)]

if (R-1,C-1) in item:
    dp[C-1][0]=item[R-1,C-1]
    dp[C-1][1]=item[R-1,C-1]
    dp[C-1][2]=item[R-1,C-1]

for j in range(C-2,-1,-1):
    if (R-1,j) in item:
        dp[j][0]=max(dp[j+1][1]+item[R-1,j],dp[j+1][0])
        dp[j][1]=max(dp[j+1][2]+item[R-1,j],dp[j+1][1])
        dp[j][2]=max(item[R-1,j],dp[j+1][2])
    else:
        dp[j][0]=dp[j+1][0]
        dp[j][1]=dp[j+1][1]
        dp[j][2]=dp[j+1][2]

for i in range(R-2,-1,-1):
    ndp=[[0 for i in range(3)] for j in range(C)]
    if (i,C-1) in item:
        ndp[C-1][0]=dp[C-1][0]+item[i,C-1]
        ndp[C-1][1]=dp[C-1][0]+item[i,C-1]
        ndp[C-1][2]=dp[C-1][0]+item[i,C-1]
    else:
        ndp[C-1][0]=dp[C-1][0]
        ndp[C-1][1]=dp[C-1][0]
        ndp[C-1][2]=dp[C-1][0]
    for j in range(C-2,-1,-1):
        if (i,j) in item:
            ndp[j][0]=max(max(dp[j][0],ndp[j+1][1])+item[i,j],ndp[j+1][0])
            ndp[j][1]=max(max(dp[j][0],ndp[j+1][2])+item[i,j],ndp[j+1][1])
            ndp[j][2]=max(dp[j][0]+item[i,j],ndp[j+1][2])
        else:
            ndp[j][0]=max(dp[j][0],ndp[j+1][0])
            ndp[j][1]=max(dp[j][0],ndp[j+1][1])
            ndp[j][2]=max(dp[j][0],ndp[j+1][2])
    dp=ndp

print(dp[0][0])


### FIXED CODE ###

import sys

input=sys.stdin.readline

R,C,K=map(int,input().split())
item=[[0 for i in range(C)] for j in range(R)]
for i in range(K):
    r,c,v=map(int,input().split())
    item[r-1][c-1]=v

dp=[[0 for i in range(3)] for j in range(C)]
dp[C-1][0]=item[R-1][C-1]
dp[C-1][1]=item[R-1][C-1]
dp[C-1][2]=item[R-1][C-1]

for j in range(C-2,-1,-1):
    dp[j][0]=max(dp[j+1][1]+item[R-1][j],dp[j+1][0])
    dp[j][1]=max(dp[j+1][2]+item[R-1][j],dp[j+1][1])
    dp[j][2]=max(item[R-1][j],dp[j+1][2])


for i in range(R-2,-1,-1):
    ndp=[[0 for i in range(3)] for j in range(C)]
    ndp[C-1][0]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][1]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][2]=dp[C-1][0]+item[i][C-1]
    for j in range(C-2,-1,-1):
        ndp[j][0]=max(max(dp[j][0],ndp[j+1][1])+item[i][j],ndp[j+1][0])
        ndp[j][1]=max(max(dp[j][0],ndp[j+1][2])+item[i][j],ndp[j+1][1])
        ndp[j][2]=max(dp[j][0]+item[i][j],ndp[j+1][2])
    dp=ndp

print(dp[0][0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nd = cnd[0] # node
    if visited[nd-1]==0:
        ko = tree[nd-1]
        for i in range(len(ko)):
            k = ko[i]
            if visited[k-1]==0:
                c[k-1] += c[nd-1]
                cnd.append(k)
    visited[nd-1]=1
    cnd.pop(0)
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
### BUGGY CODE ###

from itertools import product
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    K=int(input())
    KK=[i for i in range(1,K+1)]
    from functools import reduce
    from math import gcd

    I=list(product(KK,repeat=3))
    for i in I:
        ans+=reduce(gcd,i)
    print(ans)


resolve()

### FIXED CODE ###

from itertools import combinations_with_replacement
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    K=int(input())
    KK=[i for i in range(1,K+1)]
    from functools import reduce
    from math import gcd

    I=list(combinations_with_replacement(KK,3))
    for i in I:
        ls=len(set(i))
        if ls==1:
            ans+=reduce(gcd,i)
        elif ls == 2:
            ans+=reduce(gcd,i)*3
        else:
            ans+=reduce(gcd,i)*6





    print(ans)


resolve()
### BUGGY CODE ###

N , M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    data.append([int(i) for i in input().split()])
sorted_data = dict()
for i in data:
    if sorted_data.get(i[0]) is None:
        sorted_data[i[0]] = []
    sorted_data[i[0]].append(i[1])
sorted_data = {i:sorted(j) for i,j in sorted_data.items()}

def num2str(num, len_str=6):
    return "0" * (len_str - len(str(num))) + str(num)

for i in range(M):
    rank = sorted_data[data[i][0]].index(data[i][1]) + 1
    print(num2str(data[i][0]) + num2str(rank))

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if data[j-1][1] != p:
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))
### BUGGY CODE ###

from bisect import bisect_left
from operator import itemgetter
import sys

input = sys.stdin.readline

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for i, ans in enumerate(time[left:right]):
        if ans == -1:
            time[i+left] = x

for t in time:
    print(t)


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)