Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
a = list(map(int, input().split()))
a.sort()
s = []
for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        s.append(c)
s.sort()
s.reverse()
d = max(n,len(s))

for i in range(n):
    if s[0] > a[i]:
        a[i] = s[0]
        s.remove(s[0])
    if i == d-1:
        break


print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int, input().split()))
a.sort()
e =0
bc = []
for i in range(m):
    d = list(map(int,input().split()))
    bc.append([d[1],d[0]])
    e += d[0] 
#print(a)  
 
 
bc.sort()
bc.reverse()
#print(bc)
 
#print(e)
#print(a[n-1])
j = 0
for i in range(n):
    if j == bc[0][1] :
        bc.remove(bc[0])
        j = 0
    if bc[0][0] > a[i]:
        a[i] = bc[0][0]
        j += 1
    else:
        break
    if i == e-1:
        break
 
 
#print(a)
print(sum(a))
from string import ascii_lowercase
import heapq

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}


def solve(s):
    queue = [(0, s)]
    while queue:
        n, s = heapq.heappop(queue)
        if not s:
            return n
        b = 0
        for i, c in enumerate(s):
            b ^= cd[c]
            if bin(b).count('1') <= 1:
                heapq.heappush(queue, (n + 1, s[i + 1:]))


print(solve(input()))


### FIXED CODE ###

from string import ascii_lowercase

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}
bt = set(cd.values())
bt.add(0)


def solve(s):
    a, b = [], 0
    for c in s:
        b ^= cd[c]
        a.append(b)
    if a[-1] == 0:
        return 1

    dp = {0: 0}
    for b1 in a:
        for b2 in bt:
            b3 = b1 ^ b2
            if b3 not in dp:
                continue
            if b1 in dp:
                dp[b1] = min(dp[b1], dp[b3] + 1)
            else:
                dp[b1] = dp[b3] + 1
    return dp[a[-1]]


print(solve(input()))
def main():
    a=int(input())
    for w in range(1,a+1):
        if w<5:
            print(0)
        else:
            total=0
            for i in range(1,w):
                for j in range(1,w):
                    for k in range(1,w):
                        if (i**2)+(j**2)+(k**2)+i*k+i*j+k*j==w:
                            total+=1
            print(total)

if __name__ == '__main__':
    main()

### FIXED CODE ###

a,b,c=map(int,input().split())
total=0
for i in range(a,b+1):
    if i%c==0:
        total+=1
print(total)
def solve(n, y):
    for man in range(0, n + 1):
        for gosen in range(0, n - man + 1):
            sen = n - man - gosen
            if 10000*man + gosen*5000 + sen*1000 == y and man + gosen + sen == n:
                print(man, gosen, sen)
                return 0

    print("-1 -1 -1")
    return 0            

#main
n = int(input())
y = int(input())
solve(n, y)




### FIXED CODE ###

def solve(n, y):
    for man in range(n + 1):
        for gosen in range(n - man + 1):
            sen = n - man - gosen
            if 10000*man + gosen*5000 + sen*1000 == y and man + gosen + sen == n:
                print('{} {} {}'.format(man, gosen, sen))
                return
    print("-1 -1 -1")
    return            

#main
n, y = map(int, raw_input().split())
solve(n, y)
import math

# from functools import lru_cache


# from decimal import Decimal, ROUND_HALF_UP
# def quantize(f):
#     return int(Decimal(str(f)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))


# @lru_cache(maxsize=4096)
def get_cost(x, y):
    return int(math.pow(x - y, 2))


def get_costs(target, numbers):
    return sum([get_cost(target, n) for n in numbers])


def check(n, numbers):
    n_max = max(numbers)
    n_min = min(numbers)
    costs = []
    for target in range(n_min, n_max + 1):
        costs.append(get_costs(target=target, numbers=numbers))

    return min(costs)


def main():
    N = int(input())
    numbers = map(int, input().split())
    print(check(n=N, numbers=numbers))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math

from functools import lru_cache


@lru_cache(maxsize=4096)
def get_cost(x, y):
    return int(math.pow((x - y), 2))


def get_costs(target, numbers):
    return sum([get_cost(target, n) for n in numbers])


def check(n, numbers):
    n_max = max(numbers)
    n_min = min(numbers)
    costs = []
    for target in range(n_min, n_max + 1):
        costs.append(get_costs(target=target, numbers=numbers))

    return min(costs)


def main():
    N = int(input())
    numbers = list(map(int, input().split()))
    print(check(n=N, numbers=numbers))


if __name__ == '__main__':
    main()
if K <= A:
  print(K)
if A < K <= A + B:
  print(A)
if A + B < K <= A + B + C:
  print(A * 2 + B - K)

### FIXED CODE ###

import math
A, B, C, K = list(map(int, input().split()))
if K <= A:
  print(K)
if A < K <= A + B:
  print(A)
if A + B < K <= A + B + C:
  print(A * 2 + B - K)
x,y = input().split()
x = int(x)
y = int(y)
i = 0
if x == 0 asd y == 0:
    if x > y:
        i = x
        x = y
        y = i

    fmt = "{a} {b}"
    s = fmt.format(a = x,b = y)
    print(s)

### FIXED CODE ###


i = 0
j = 0
lis = []
while True:
    x,y = input().split()
    x = int(x)
    y = int(y)
    if x > y:
        i = x
        x = y
        y = i

    if x == 0 and y == 0:
        break
    fmt = "{a} {b}"
    s = fmt.format(a = x,b = y)
    lis.append(s)
    j += 1

for i in range(j):
    print(lis[i])
|AB|, |BC|, |CB| = map(int, input().split())
print(|AB|*|BC|//2)

### FIXED CODE ###

AB, BC, CB = map(int, input().split())
print(AB*BC//2)
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % ((cnt1 - 1) if cnt1 - 1 > 0 else 0)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)

### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)
lst = int(input().split())
print((lst[0]+2*lst[1])//(2*lst[1]+1))

### FIXED CODE ###

lst = list(map(int,input().split()))
print((lst[0]+2*lst[1])//(2*lst[1]+1))
N, A, B = map(int, input().split())
ans = 0

AplusB = A+B

try:
    action_num = N // AplusB
except:
    action_num = 0
ans += action_num * A

try:
    action_mod = N % AplusB
except:
    action_mod = 0

# one_action = "B"*A + "R"*B
for i in range(action_mod):
    if one_action[i] == "B":
        ans += 1

print(ans)


### FIXED CODE ###

N, A, B = map(int, input().split())
ans = 0

AplusB = A+B

action_num = N // AplusB
ans += action_num * A

action_mod = N % AplusB

if action_mod <= A:
    ans += action_mod
else:
    ans += A

print(ans)
N = int(input())
A = list(map(int, input().split()))
A.sort()
Q = int(input())

for i in range(Q):
    b, c = map(int, input().split())
    s = 0
    e = N
    h = int((s+e)/2)
    while A[h] != b and s != h :
        if A[h] < b:
            s = h
            h = int((s+e)/2)
        elif A[h] > b:
            e = h
            h = int((s+e)/2)
    X = []
    for j in range(s, e):
        if A[j] == b:
            X.append(j)
            A[j] = c
    print(sum(A))
    if len(X) > 0:
        A = A[:X[0]] + A[X[-1]:]
        s = 0
        e = len(A)
        h = int((s+e)/2)
        while A[h] != c and s != h :
            if A[h] < c:
                s = h
                h = int((s+e)/2)
            elif A[h] > c:
                e = h
                h = int((s+e)/2)
        A = A[:h] + [c]*len(X) + A[h+1:]

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
X = [0] * (10**5)

for i in range(N):
    X[A[i]-1] += 1

ans = sum(A)

for j in range(Q):
    b, c = map(int, input().split())
    a = X[b-1]
    X[b-1] = 0
    X[c-1] += a
    ans = ans - a*b + c*a
    print(ans)
a, b = map(int, input().split())

if (a * b) % 2 == 0
    print("Even")
else:
    print("Odd")


### FIXED CODE ###

a, b = map(int, input().split())

if (a * b) % 2 == 0:
    print("Even")
else:
    print("Odd")
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N*3+5)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v+N+1)
        adj[u+N+1].append(v+2*N+2)
        adj[u+2*N+2].append(v)

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        assert seen[t] % 3 == 0
        print(seen[t] // 3)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N*3+5)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v+N+1)
        adj[u+N+1].append(v+2*N+2)
        adj[u+2*N+2].append(v)

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[s] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        assert seen[t] % 3 == 0
        print(seen[t] // 3)


if __name__ == '__main__':
    main()
from decimal import *
A, B = input().strip().split()
A, B = [int(A), float(B)]
if A>=0 and A<=10**15:
    if B>=0 and B<10 :
        Decimal(str(B)).quantize(Decimal('0.01'),round(ROUND_DOWN))
        result=A*B
        new=round(result)
        print(new)

### FIXED CODE ###

from decimal import Decimal
import math
a,b = map(Decimal,input().split())
ans = a*b
print(math.floor(ans))
n, m = map(int, input().split())
if 2 * n >= m:
    print(m // 2)
else:
    a = m - 2 * n
    b = a // 4
    print(n + b)

### FIXED CODE ###

n = int(input())
pi = 1
for i in range(1, n + 1):
    pi = (pi * i) % 1000000007
print(pi)
import sys
sys.setrecursionlimit(3001)

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(li):
    if len(li) == 2:
        return lcm(li[0], li[1])

    else:
        li = [lcm(li[0], li[1])] + li[2:]
        return lcm_list(li)

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


i = max(lcm_list(a) - 1, 1)
print(sum([i % j for j in a]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(30000)

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(li):
    if len(li) == 2:
        return lcm(li[0], li[1])

    else:
        li = [lcm(li[0], li[1])] + li[2:]
        return lcm_list(li)

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


i = max(lcm_list(a) - 1, 1)
print(sum([i % j for j in a]))
while True
    n,x = map(int, raw_input().split()
    if n == 0 and x == 0: break
    c = 0
    for i in range(1, n/3 +1):
        for j in range(i+1, n/2 +1):
            ij = i + j
            for k in range(j+1, n+1):
                if ij+k == x:
                    c += 1
    print c    

### FIXED CODE ###

def count(n, x):
    c = 0
    for i in range(1, n-1):
        for j in range(i+1, n,):
            for k in range(j+1, n+1):
                s = i + j + k
                if s == x:
                    c += 1
                    break
                elif s > x: break
    return c

while True:
    p = map(int, raw_input().split())
    if p == [0, 0]: break
    print count(*p)
N = int(input())
S = input()
K = int(input())
a = ""
b = S[K]
for i in range(N):
  a = S[i]
  if (a == b):
    print(a,end = "")
  else:
    print("*",end = "")

### FIXED CODE ###

N = int(input())
S = input()
K = int(input())
a = ""
b = S[K - 1]
for i in range(N):
  a = S[i]
  if (a == b):
    print(a,end = "")
  else:
    print("*",end = "")
a,b,c,d=map(int,input().split())
gcdc=[]
gcdd=[]
for i in range(1,int(c**(1/2))+1):
  if c%i==0:
    gcdc.append(i)
    if i!=c//i:
      gcdc.append(c//i)
for i in range(1,int(d**(1/2))+1):
  if d%i==0:
    gcdd.append(i)
    if i!=d//i:
      gcdd.append(d//i)
E=[]
for i in range(len(gcdc)):
  if gcdc[i] in gcdd:
    E.append(gcdc[i])
e=1
for i in range(len(E)):
  e*=E[i]
f=c*d//e
g=0
h=0
i=0
if a%c==0:
  g=b//c-a//c+1
else:
  g=b//c-a//c
if a%d==0:
  h=b//d-a//d+1
else:
  h=b//d-a//d
if a%f==0:
  i=b//f-a//f+1
else:
  i=b//f-a//f
print(b-a+1-g-h+i)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
gcdc=[]
gcdd=[]
for i in range(1,int(c**(1/2))+1):
  if c%i==0:
    gcdc.append(i)
    if i!=c//i:
      gcdc.append(c//i)
for i in range(1,int(d**(1/2))+1):
  if d%i==0:
    gcdd.append(i)
    if i!=d//i:
      gcdd.append(d//i)
E=[]
for i in range(len(gcdc)):
  if gcdc[i] in gcdd:
    E.append(gcdc[i])
e=max(E)
f=c*d//e
if a%c==0:
  g=b//c-a//c+1
else:
  g=b//c-a//c
if a%d==0:
  h=b//d-a//d+1
else:
  h=b//d-a//d
if a%f==0:
  i=b//f-a//f+1
else:
  i=b//f-a//f
print(b-a+1-g-h+i)
N=int(input())
def f(N):
  i=0#桁数
  while N>1:
    N=N/10
    i+=1
  return i

x=f(N)
if N%x==0:
  print("Yes")
else: print("No")

### FIXED CODE ###

import math
N=int(input())
def g(N):#桁数を返す
  i=0#桁数
  while N>=1:
    N=N/10
    i+=1
  return i

def f(N):
  j=g(N)
  S=0
  while j!=0:
    d=math.floor(N/(10**(j-1)))
    S+=d
    N-=d*(10**(j-1))
    j-=1
  return S
  
if N%f(N)==0:
  print("Yes")
else: print("No")
N, K, S = map(int,input().split())
L = [S]*K
for i in range(N-K):
  if S < 10*9:
  	L.append(S+1)
  else:
    L.append(1)
  
print(' '.join(map(int, L)))

### FIXED CODE ###

N, K, S = map(int,input().split())
L = [S]*K
for i in range(N-K):
  if S < 10**9:
  	L.append(S+1)
  else:
    L.append(1)
  
print(' '.join(map(str, L)))
import math
n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
miti=[a,b,c,d,e]
mini=min(miti)
retu=n//miti
if n<=mini:
  print(5)
else:
  print(4+retu)

### FIXED CODE ###

import math
n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
miti=[a,b,c,d,e]
mini=min(miti)
retu=math.ceil(n/mini)
print(4+retu)
N = int(input())

import math
from collections import defaultdict
from itertools import product
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return 'prime number'
    else:
        factor.append(n)
        return factor

fac = trial_division(N)
dic = defaultdict(int)
for n in fac:
    if n != 1:
        dic[n] += 1

a = []
for k, v in dic.items():
    a.append([k**j for j in range(v+1)])

tmp = list(product(*a))

ans = 0
for t in tmp:
    b = 1
    for j in t:
        b *= j
    if b >= 2:
        xx, yy = divmod(N, b-1)
        if xx == yy:
            ans += b - 1

print(ans)

### FIXED CODE ###

from collections import Counter
from itertools import product

N = int(input())

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

# 素因数分解で約数を計算する
primes = prime_decomposition(N)

# 素因数の種類と個数を数え上げる
counter = Counter(primes)
values = [[k**i for i in range(v+1)] for k, v in counter.items()]
p = product(*values)

# 全ての種類の素数×個数を計算して、約数の組み合わせを格納する
divisors = []
for v in p:
    div = 1
    for w in v:
        div *= w
    divisors.append(div)

# 条件にあう約数を選別してmを求め、答えに加算する
ans = 0
for i in divisors:
    j = N / i
    if (i > j + 1) & (i >= 1) & (j >= 1):
        ans += i - 1
print(ans)
import collections
n = int(input())

for i in range(1,n+1):
    t *= i
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(t))
ans = 1
for _, v in c.items():
    ans *= (v + 1)
print(ans%(10**9+7))

### FIXED CODE ###

import collections
n = int(input())
t = 1
for i in range(1,n+1):
    t *= i
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(t))
ans = 1
for _, v in c.items():
    ans *= (v + 1)
print(ans%(10**9+7))
iptA=list(map(int,input().split()))
X=list(map(int,input().split())).append(iptA[2])
Y=list(map(int,input().split())).append(iptA[3])
     
xmax,ymax=max(X),max(Y)
if xmax>=ymax:
    print('War')
else:
    print('No War')

### FIXED CODE ###

iptA=list(map(int,input().split()))
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
X.append(iptA[2])
Y.append(iptA[3])
     
xmax,ymin=max(X),min(Y)
if xmax>=ymin:
    print('War')
else:
    print('No War')
n=int(input())
a=[]
v=list(map(int,input().split()))
c=list(map(int,input().split()))
if n==1:
    if v[0]-c[0]<=0:
        print("0")
    else:
        print(v[0]-c[0])
    exit()
for i in range(n):
    if v[i]-c[i]>0:
        a.append(v[i]-c[i])
a.sort()
print(a[-1]+a[0])

### FIXED CODE ###

n=int(input())
a=[]
v=list(map(int,input().split()))
c=list(map(int,input().split()))

for i in range(n):
    if v[i]-c[i]>0:
        a.append(v[i]-c[i])
print(sum(a))
import sys
s = set(input())
t = set(input())

if len(s) != len(t):
    print("No")
    sys.exit()

if all(s.count(t[i]) ==1 for i in range(len(t))):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
t = input()

for i in range(len(s)):
    if s == t:
        print("Yes")
        sys.exit()
    else:
        tmp = s[0]
        s = s[1:] + tmp
print("No")
X,Y = int(input())
print(int(X+(1/2)*Y))

### FIXED CODE ###

X,Y = map(int,input().split(" "))
print(int(X+(1/2)*Y))
from collections import defaultdict
from functools import lru_cache

N, M = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]

dp = [-1 for _ in range(N + 1)]

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths))


### FIXED CODE ###

from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)


N, M = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]

dp = [-1 for _ in range(N + 1)]

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths))
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
l=[lnii() for i in range(n)]

for tx in range(101):
  for ty in range(101):
    t_h=0
    for x,y,h in l:
      dist=abs(tx-x)+abs(ty-y)
      if t_h==0:
        t_h=h+dist
      else:
        if t_h!=h+dist:
          break
    else:
      ans_x=tx
      ans_y=ty
      ans_h=t_h
      break

print(ans_x,ans_y,ans_h)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
l=[]
for i in range(n):
  x,y,h=nii()
  l.append([x,y,h])
  if h!=0:
    ini_x=x
    ini_y=y
    ini_h=h

for tx in range(101):
  for ty in range(101):
    n_h=abs(tx-ini_x)+abs(ty-ini_y)+ini_h
    for x,y,h in l:
      t_h=max(n_h-(abs(tx-x)+abs(ty-y)),0)
      if h!=t_h:
        break
    else:
      print(tx,ty,n_h)
      exit()
n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ -1 for i in range(10**5)] 
for i in range(n):
    color = int(input()) - 1

    if color_list[color] not in [-1,i-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7

    color_list[color] = i
print(ans_list[-1])

### FIXED CODE ###


n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ -1 for i in range(2*(10**5))] 
for i in range(n):
    color = int(input()) - 1

    if color_list[color] not in [-1,i-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7

    color_list[color] = i
print(ans_list[-1])
while True:
    s = input()
    if s == '.':break
    while True:
        if s.find('+') == -1 and s.find('-') == -1:
            index = s.rfind('[')
            if index == -1:break
            e = s.find(']', index, len(s))
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            index = s.find('+')
            if index == -1:
                index = s.find('-')
            if s.find('-') != -1
                index = min(index, s.find('-'))
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                f += [-1, 1][s[e] == '+']
                e += 1
            r = s[e]
            if r != '?':
                r = chr((ord(r) - ord('A') + f) % 26 + ord('A'))
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?', 'A'))


### FIXED CODE ###

while True:
    s = input()
    if s == '.':break
    while True:
        if s.find('+') == -1 and s.find('-') == -1:
            index = s.rfind('[')
            if index == -1:break
            e = s.find(']', index)
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            index = s.find('+')
            if index == -1:
                index = s.find('-')
            if s.find('-') != -1:
                index = min(index, s.find('-'))
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                f += [-1, 1][s[e] == '+']
                e += 1
            r = s[e]
            if r != '?':
                r = chr((ord(r) - ord('A') + f) % 26 + ord('A'))
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?', 'A'))