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

s = input()
n = int(input())
for i in range(n):
  l = list(map(str, input().split()))
  if l[0] == "2":
    if l[1] == "1":
      s = l[2] + s
    else:
      s = s + l[2]
  else:
    s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
#s = input()
n = int(input())
f = 1
for i in range(n):
  l = list(map(str, input().split()))
  if l[0] == "2":
    tmp = int(l[1])*f
    if tmp == 1 or tmp == -2:
      s.appendleft(l[2])
    else:
      s.append(l[2])
  else:
    f *= -1

if f == -1:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

import sys
import math
from functools import reduce
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

N = II()
l = []
for i in range(1,N+1):
    l.append(i)
ans=0

num = 3 #生成するビット数
bit_list = list(itertools.product(l, repeat=num))

for L in bit_list:
    ans += gcd_list(L)
print(ans)







### FIXED CODE ###

import sys
#import fractions
from math import gcd
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

def euclid(p,q):
    if p%q==0:
        return q
    else:
        return euclid(q,p%q)


N = II()

ans=0

for i in range(1, N+1):
    for j in range(1, N+1):
        x = gcd(i,j)
        for k in range(1, N+1):
            ans+=gcd(x,k)


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

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = list(input())

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        bisect.insort_left(set_list[ord(s)],i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]

            for j in range(a_ord,z_ord+1):
                if i-1 in set_list[j]:
                    break

            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()


### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = list(input())

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        set_list[ord(s)].append(i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



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

import math
from functools import reduce

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

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

K=int(input())
ans=[]
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans.append(gcd(i,j,k))
#print(len(ans))
print(sum(ans))

### FIXED CODE ###

import math
from functools import reduce

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

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

K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += gcd(i,j,k)
#print(len(ans))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for b in range(60)[::-1]:
    ans <<= 1
    c = sum(a[i] >> b & 1 for i in range(n))
    ans = (ans + c * (n - c)) % MOD
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for b in range(60)[::-1]:
    ans <<= 1
    c = sum(a[i] >> b & 1 for i in range(n))
    ans = (ans + c * (n - c)) % MOD
print(ans)
### BUGGY CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
try:
    for q in range(n-1,-1,-1):

        while p<n and a[q]+a[p]<=md:
            p+=1

        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2

except:
    b=1
    while True:
        b+=1

ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    n, m, k = map(int, stdin.readline().split())
    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        g[c - 1][d - 1][1] = True
        g[d - 1][c - 1][1] = True

    def dfs(v, seen):
        seen[v] = True

        for nv in range(n):
            if g[v][nv][0]:
                if seen[nv]:
                    continue
                dfs(nv, seen)

    ans = [0] * n
    for i in range(n):
        gi = g[i]
        seen = [False] * n
        dfs(i, seen)
        for j in range(n):
            if not(gi[j][0]) and not(gi[j][1]) and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0:
            x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            x, y = sorted([x, y])
            p[x], p[y] = p[x] + p[y], x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parent[self.find(x)]


def main():
    n, m, k = map(int, stdin.readline().split())

    f = UnionFindTree(n)

    f_or_b = [0] * n

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f.union(a - 1, b - 1)
        f_or_b[a - 1] += 1
        f_or_b[b - 1] += 1

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        if f.same(c - 1, d - 1):
            f_or_b[c - 1] += 1
            f_or_b[d - 1] += 1

    print(*[f.size(i) - f_or_b[i] - 1 for i in range(n)])


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

#cited from maspy
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
#A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
#n = len(A)

ans = 0
for aa in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if aa[b-1] - aa[a-1] == c:
      score += d
  ans = max(ans,score)
print(ans)

### FIXED CODE ###

import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)
### BUGGY CODE ###

from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      if ncost <= dist[nx][ny] :
        heappush(q, (ncost, nx, ny))
        dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)
### BUGGY CODE ###

from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    arr = factorization(a[i+1])
    for i in arr:
        if i == 1: continue
        if used[i]: pair=False
        used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')


### FIXED CODE ###

import math
import sys
import random

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

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

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)

# not coprimeか判定
for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)

# pairwise coprimeか判定
used = [0] * (10**6+1)
pair = True
for _a in a:
    if _a == 1:
        continue
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))

ans = 0
for i in range(N):
  for j in range(A[i]+1,N):
    if j -i  == A[i]+A[j]:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))

L = {}
R = {}

for i in range(N):
  t = A[i]+i
  if t in L:
    L[t] += 1
  else:
    L[t] = 1
  s = i - A[i]
  if s in R:
    R[s] += 1
  else:
    R[s] = 1  
#print(L,R)
ans = 0
for i in range(N):
  t = A[i]+i
  #ans += R[t]
  if t in R.keys():
    ans += R[t]
    #print(t,R[t])
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted([a[i] - i - 1 for i in range(n)])
c = [i + (0 - b[0]) for i in b]

d = []
count = 0
while c[-1] != -1:
    d.append(sum([abs(i) for i in c]))
    for i in range(len(c)):
        c[i] -= 1
    if count > 0:
        if d[-1] >= d[-2]:
            break
    count += 1
print(min(d))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted([a[i] - i - 1 for i in range(n)])
c = [i + (0 - b[0]) for i in b]

d = []
if n == 1:
    print(0)
else:
    if n % 2 == 1:
        d.append(0 - c[n//2])
    else:
        d.append(0 - c[n//2])
        d.append(0 - c[n//2 - 1])
        d.append(1 - c[n//2])
        d.append(-1 - c[n//2 - 1])

    ans = []
    for j in d:
        e = [i + j for i in c]
        ans.append(sum([abs(i) for i in e]))

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

import sys
input = sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
l=[1]
i=0
aa=1
while True:
    aa=a[aa-1]
    if aa == 2:
        print(i+1)
        sys.exit()
    if aa in l:
        print(-1)
        sys.exit()
    l.append(aa)
    i+=1

### FIXED CODE ###

import sys
import cProfile
input = sys.stdin.readline
def main():
    n=int(input())
    a=[int(input()) for _ in range(n)]
    l=[1]
    i=0
    aa=1
    while True:
        aa=a[aa-1]
        if aa == 2:
            print(i+1)
            sys.exit()
        if i>n:
            print(-1)
            sys.exit()
        i+=1
main()
### BUGGY CODE ###

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

data = []
for i in range(n+1):
  data.append(i)

l = n+1

ans = 0

# [4, 2] -> (0 + 1 + 2), (2 + 3 + 4) 

for i in range(k, (n+1) + 1):
  # i: 2, data[:2] = [0, 1], min: 1
  min = sum(data[:i])

  # i: 2,                    max: 5
  max = sum(data[l-i:])

  diff = max - min + 1
  # print(diff)
  ans += diff

print(ans)


### FIXED CODE ###

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

MOD = 10**9 + 7

data = []
for i in range(n+1):
  data.append(i)

ans = 0

# あらかじめ累積和を求めておく
sum_data = [0] * (n + 1)
for i in range(1, n + 1): # 1..4
  sum_data[i] = sum_data[i - 1] + i

# sum_data: [0 1 3 6]

# 処理系
for i in range(k, (n+1) + 1): # 1..3
  # min
  min_ = sum_data[i-1]

  # max
  if n+1 - i - 1 == -1:
    max_ = sum_data[-1]
    # print("max :", max_)
  else:
    max_ = sum_data[-1] - sum_data[n+1 - i - 1]
    # print("max :", max_)

  diff = (max_ - min_ + 1)
  ans += diff

print(ans % MOD)
### BUGGY CODE ###

from collections import Counter as cnt
import copy
n = int(input())
s = input()

count = cnt(s)
num_rest = []
for i in range(n):
  count[s[i]] -= 1
  num_rest.append(len([i for i in count.values() if i != 0]))
#print(num_rest)

checked = set()
total = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] + s[j] not in checked:
      checked.add(s[i] + s[j])
      total += num_rest[j]
print(total)

### FIXED CODE ###

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

def search(s, c, left):
  for idx in range(left, len(s)):
    if s[idx] == c:
      return idx
  return -1

total = 0
for keta1 in range(10):
  first_keta1 = search(s, str(keta1), 0)
  if first_keta1 == -1 or first_keta1 >= n-2:
    continue
  for keta2 in range(10):
    first_keta2 = search(s, str(keta2), first_keta1 + 1)
    if first_keta2 == -1 or first_keta2 >= n-1:
      continue
    for keta3 in range(10):
      first_keta3 = search(s, str(keta3), first_keta2 + 1)
      if first_keta3 != -1:
        total += 1
print(total)
### BUGGY CODE ###

s = input()
q = int(input())

li = [input() for i in range(q)]

k= 0

for i in li:
    if i == "1":
        k += 1
    else:
        
        if (int(i[2])+k) % 2 == 0:
            s = s + i[4]
        else:
            s = i[4] + s

if k % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

li = [input() for i in range(q)]
k = 0
ans = [s]
ans = deque(ans)

for i in li:
    if i == "1":
        k += 1
    else:
        if (int(i[2]) + k) % 2 == 0:
            ans.append(i[4])
        else:
            ans.appendleft(i[4])

ans = list(ans)
s = "".join(ans)
if k % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

import math

k = int(input().rstrip())


ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                for c in range(1, k + 1):
                    if c == 1:
                        ans += 1
                    else:
                        if a == b:
                            ans += math.gcd(a, c)
                        elif a == c:
                            ans += math.gcd(b, c)
                        else:
                            tmp = math.gcd(a, b)
                            ans += math.gcd(tmp, c)

print(ans)

### FIXED CODE ###

import math

k = int(input().rstrip())


ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                if a == b:
                    tmp = a
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)
                else:
                    tmp = math.gcd(a, b)
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)

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

def main():
    import bisect
    from array import array
    B=bisect.bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=t[-q:]
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted([x,B(d,s-x),B(d,t-x)]for s,t,x in zip(t[::3],t[1::3],t[2::3]))[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()