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

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                print(v + 1, i + 1)
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        print(v + 1, p + 1)
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)
### BUGGY CODE ###

N=int(input())
print(0,flush=True)
s=input()
if s=="Vacant":
    exit()
cap=0
if s=="Female":
    cap=1
lo=0
hi=N
while(1):
    mid=(lo+hi)//2
    print(mid,flush=True)
    s=input()
    if s=="Vacant":
        exit()
    gen=0
    if s=="Female":
        gen=1
    if (cap+mid)%2==gen:
        lo=mid
    else:
        hi=mid

### FIXED CODE ###

N=int(input())
print(0,flush=True)
s=input()
if s=="Vacant":
    exit()
cap=0
if s=="Female":
    cap=1
lo=0
hi=N
while(1):
    mid=(lo+hi)//2
    print(mid,flush=True)
    s=input()
    if s=="Vacant":
        exit()
    gen=0
    if s=="Female":
        gen=1
    if (cap+mid)%2==gen:
        lo=mid
    else:
        hi=mid
### BUGGY CODE ###

from itertools import combinations as comb
from copy import deepcopy
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    As = list(map(int, input().split()))

    for a in As:
        Bs = deepcopy(As)
        Bs.remove(a)
        b_set = set(Bs)
        ans = 0
        for b in b_set:
            ans += len(list(comb(range(Bs.count(b)), 2)))
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    arr = list(map(int, input().split()))

    cnt = Counter(arr)
    total = 0
    for key in cnt.keys():
        total += cnt[key]*(cnt[key]-1)//2

    for i in range(n):
        tmp = total
        tmp -= cnt[arr[i]]*(cnt[arr[i]]-1)//2
        tmp += (cnt[arr[i]]-1)*(cnt[arr[i]]-2)//2
        print(tmp)


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

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dp=[[[0]*4 for i in range(c+1)] for j in range(r+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dp[i+1][j+1][0]=max(dp[i+1][j+1][0],max(dp[i][j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k]+dic[(i+1,j+1)],dp[i+1][j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i+1][j][k])
    print(max(dp[-1][-1]))

main()

### FIXED CODE ###

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpn[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
    print(max(dpn[-1]))

main()
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for i in range(N+1):
    for j in range(N+1):
        if N >= G*i+B*j:
            if (N-(G*i+B*j))%R == 0:
               ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for i in range(N+1):
    for j in range(N+1):
        if N >= G*i+B*j:
            if (N-(G*i+B*j))%R == 0:
               ans += 1
 
print(ans)
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
task = []
for i in range(N):
    a, b = map(int, input().split())
    task.append((a, b))

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        bisect.insort_right(wa, task[j][1])
        j += 1
    if wa:
        ans += wa[-1]
        del (wa[-1])

print(ans)


### FIXED CODE ###

import bisect
import heapq

N, M = map(int, input().split())
task = []
for i in range(N):
    a, b = map(int, input().split())
    task.append((a, b))

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        heapq.heappush(wa,-task[j][1])
        j += 1
    if wa:
        ans -= heapq.heappop(wa)

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

import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人

    # if l == r:
    #     return a[l]
    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


n = int(input())
a = tuple(int(x) for x in input().split())

memo = [[None] * n for _ in range(n)]
for i, aa in enumerate(a):
    memo[i][i] = aa

print(func(0, n - 1))


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

S = input()
pre = S
while True:
    t = pre.replace('01', '')
    t = t.replace('10', '')
    if pre == t:
        break
    pre = t
print(len(S)-len(t))

### FIXED CODE ###

S = input()
t = []
for s in S:
    if len(t) == 0:
        t += s
    elif t[-1] != s:
        t.pop()
    else:
        t += s
print(len(S)-len(t))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
if True:
    n = int(input())
    an= list(map(int, input().split()))

else:
   n=5
   an=[1,1,2,1,2]


for k in range(0,n):
    an2 = an[:]
    del an2[k]
    # print(an2)
    ans = 0
    for b1 in range(0,n-1):
        for b2 in range(0,n-1):
            if b1 == b2:
                continue
            if an2[b1] == an2[b2]:
                ans += 1
    print(int(ans/2))

### FIXED CODE ###

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

datas = [0] * (n+1)
for a in an:
    datas[a] += 1

ans = 0
for i in range(1,n+1):
    if datas[i] > 1:
        ans += datas[i] * (datas[i]-1)/2
ans = int(ans)

for k in range(0,n):
    if datas[an[k]] > 1:
        print(int(ans - datas[an[k]] * (datas[an[k]]-1)/2 + (datas[an[k]]-1) * (datas[an[k]]-2)/2))
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
lst = [int(input()) for _ in range(n)]
lst_rev = lst[::-1]

visited = [False]*n
cnt = 0

for i in range(n):
    if visited[i]:
        continue
    else:
        visited[i] = True
        cnt += 1
        tmp = lst_rev[i]
        for j in range(i+1, n):
            if not visited[j] and lst_rev[j] < tmp:
                visited[j] = True
                tmp = lst_rev[j]
print(cnt)

### FIXED CODE ###

import bisect
from collections import deque

n = int(input())
la = [int(input()) for _ in range(n)]
result = deque([])

for a in la:
    idx = bisect.bisect_left(result, a)
    if idx==0:
        result.appendleft(a)
    else:
        result[idx - 1] = a
print(len(result))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    inst.append((tcnt % 2, fcnt))

f_total = sum([f for (_, f) in inst])
f_rem = [0] * (len(inst) + 1)
f_rem[len(inst)] = 0
for i in range(len(inst) - 1, -1, -1):
    f_rem[i] = f_rem[i + 1] + inst[i][1]
assert f_rem[0] == f_total


visited = set()


def reach(i, x, y, dx, dy):
    dist = abs(gx - x) + abs(gy - y)
    # print(f"i={i} ({x},{y}) dist={dist}: inst={inst[i:]}")
    if i == len(inst):
        return dist == 0
    if (i, x, y, dx, dy) in visited:
        return False
    visited.add((i, x, y, dx, dy))
    if dist > f_rem[i]:
        return False
    t, f = inst[i]
    if t:
        dy, dx = dx, -dy
    if reach(i + 1, x + f * dx, y + f * dy, dx, dy):
        return True
    if reach(i + 1, x - f * dx, y - f * dy, -dx, -dy):
        return True
    return False


print("Yes" if reach(0, rx, ry, 1, 0) else "No")


### FIXED CODE ###

"""Knapsack"""
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1

xlist, ylist = [], []
heading_x = True
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    if head == len(s):
        break
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    if ((tcnt % 2) == 1) ^ heading_x:
        heading_x = True
        xlist.append(fcnt)
    else:
        heading_x = False
        ylist.append(fcnt)


def fill(fs, goal_offset):
    f_total = sum(fs)
    if f_total < goal_offset:
        return False
    if f_total == goal_offset:
        return True
    f_diff = f_total - goal_offset
    if f_diff % 2 == 1:
        return False
    f_diff //= 2
    diffs = {0}
    for f in fs:
        for d in list(diffs):
            d2 = f + d
            if d2 > f_diff:
                continue
            if d2 == f_diff:
                return True
            diffs.add(d2)
    return False


if fill(xlist, abs(gx - rx)) and fill(ylist, abs(gy - ry)):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i] != S[j]:
            for k in range(j+1,N):
                if S[i] != S[k] and S[j] != S[k] and j-i != k-j:
                    ans += 1
print(ans)
            

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
count = [[0 for i in range(N)] for j in range(3)]
for i in range(N):
    if S[i] == 'R':
        count[0][i] = 1
    if S[i] == 'G':
        count[1][i] = 1
    if S[i] == 'B':
        count[2][i] = 1
for i in range(3):
    for j in range(N-1,0,-1):
        count[i][j-1] += count[i][j]
for i in range(N-2):
    a = S[i]
    for j in range(i+1,N-1):
        b = S[j]
        if a != b:
            if a != 'R' and b != 'R':
                ans += count[0][j]
                if 2*j-i < N and S[j+j-i] == 'R':
                    ans -= 1
            if a != 'G' and b != 'G':
                ans += count[1][j]
                if 2*j-i < N and S[j+j-i] == 'G':
                    ans -= 1
            if a != 'B' and b != 'B':
                ans += count[2][j]
                if 2*j-i < N and S[j+j-i] == 'B':
                    ans -= 1
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [0]*Q, [0]*Q
    for i in range(Q):
        B[i], C[i] = map(int, input().split())

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        if a not in d:
            d[a] = ()
        d[a] += (i,)

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        ans += len(d[b]) * (c-b)
        if c not in d:
            d[c] = ()
        d[c] = d[c] + d[b]
        d[b] = ()
        print(ans)

main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [0]*Q, [0]*Q
    for i in range(Q):
        B[i], C[i] = map(int, input().split())

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        d[a] = d.get(a, 0) + 1

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        ans += d[b] * (c-b)
        if c not in d:
            d[c] = 0
        d[c] = d[c] + d[b]
        d[b] = 0
        print(ans)

main()
### BUGGY CODE ###

import copy
import math
import string

S = input()
Q = int(input())

is_reverse = False
front = ""
back = ""
for i in range(Q):
    A = list(map(str,input().split()))
    A[0] = int(A[0])
    if A[0] == 1:
        is_reverse = (not is_reverse)
    elif A[0] == 2:
        A[1] = int(A[1])
        if A[1] == 1:
            if is_reverse:
                back += A[2]
            else:
                front += A[2]
        else:
            if is_reverse:
                front += A[2]
            else:
                back += A[2]
front = front[::-1]
S = front + S + back
if is_reverse:
    S = S[::-1]
print(S)


### FIXED CODE ###

import copy
import math
import string

S = input()
Q = int(input())

is_reverse = False
front = ""
back = ""
for i in range(Q):
    A = list(map(str,input().split()))
    A[0] = int(A[0])
    if A[0] == 1:
        is_reverse = (not is_reverse)
    elif A[0] == 2:
        A[1] = int(A[1])
        if A[1] == 1:
            if is_reverse:
                back += A[2]
            else:
                front += A[2]
        else:
            if is_reverse:
                front += A[2]
            else:
                back += A[2]
front = front[::-1]
S = front + S + back
if is_reverse:
    S = S[::-1]
print(S)
### BUGGY CODE ###

mod = 10**9+7
def comb_mod(n,r,mod):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans

A, B, C, D = map(int, input().split())

ans = comb_mod(C+D+2,C+1,mod)-comb_mod(B+C+1,B,mod)-comb_mod(A+D+1,A,mod)+comb_mod(A+B,A,mod)
print(ans%mod)

### FIXED CODE ###

mod = 10**9+7
def comb_mod(n,r,mod,invs):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    ans *= invs[r]
    ans %= mod
    return ans

A, B, C, D = map(int, input().split())

invs = [1]*(C+2)
for i in range(1,C+2):
    invs[i] = invs[i-1]*pow(i,mod-2,mod)
    invs[i] %= mod
ans = comb_mod(C+D+2,C+1,mod,invs)-comb_mod(B+C+1,B,mod,invs)-comb_mod(A+D+1,A,mod,invs)+comb_mod(A+B,A,mod,invs)
print(ans%mod)
### BUGGY CODE ###

import math
N=int(input())
total=[]

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      lis=[i,j,k]
      ans = lis[0]
      for l in range(1,3):
        ans = math.gcd(ans,lis[l])
      else:
        total.append(ans)
        
print(sum(total))  

### FIXED CODE ###

from math import gcd
N=int(input())
total=0

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      total+=gcd(gcd(i,j),k)
      
print(total)
### BUGGY CODE ###

s = input()
q = int(input())
r = False
for _ in range(q):
  d = list(input().split())
  if len(d)==1:
    r = ~r
  else:
    if (d[1]=='1' and ~r) or (d[1]=='2' and r):
      s = d[2] + s
    else:
      s += d[2]
if r:
  s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
r = False
S = deque(s)
for _ in range(q):
  d = list(input().split())
  if len(d)==1:
    r = ~r
  else:
    if (d[1]=='1' and ~r) or (d[1]=='2' and r):
      S.appendleft(d[2])
    else:
      S.append(d[2])
s = ''.join(S)
if r:
  s = s[::-1]
print(s)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

def nibutan(min_, max_):
	if min_+1 >= max_:
		if is_ok(min_):
			return min_
		else:
			return max_
	else:
		search = (min_+max_)//2
		# print(min_, max_, search)
		if is_ok(search):
			max_ = search
		else:
			min_ = search
		return nibutan(min_, max_)

print(nibutan(0, 10**18))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

news = set()
news.add((Ch, Cw))
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2,-1,0,1,2]
while True:
  # 行けるところすべて追加
  targets = set()
  while len(news) > 0:
    olds = set(news)
    targets |= olds
    news = set()
    for Th, Tw in olds:
      for i,j in a:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not (_p) in s and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          news.add(_p)
          s.add((Th,Tw))
  # クリアしてるか確認
  if (Dh,Dw) in targets:
    print(ans)
    exit()
  else:
    news = set()
    ans += 1
    for Th,Tw in targets:
      for i in b:
        for j in b:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          if not (_p) in s and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            news.add(_p)
            s.add((Th,Tw))
    if len(news) == 0:
      print('-1')
      exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7

n=int(data())
s=0
while n:
    s+=n%10
    n//=10
print("Yes" if s%9==0 else "No")


### FIXED CODE ###

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7

n=int(data())
print("Yes" if n%9==0 else "No")
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    Q = input().split()
    if(Q[0] == '1'):s = s[::-1]
    elif(Q[0] == '2'):
        if(Q[1] == '1'):s = Q[2] + s
        elif(Q[1] == '2'):s = s + Q[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
m = 0
t = ''
l = ''
for i in range(q):
    Q = input().split()
    if(Q[0] == '1'):
        m = m ^ 1
        # t,l = l[::-1],t[::-1]
    elif(Q[0] == '2'):
        if(Q[1] == '1'):
            if(m == 0):t += Q[2]
            else:l += Q[2]
        elif(Q[1] == '2'):
            if(m == 0):l += Q[2]
            else:t += Q[2]
# print(t,s,l)
s = t[::-1] + s + l

if(m == 1):s = s[::-1]
print(s)