Harryxun/sft_time huggingface dataset:
### 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

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 = INT()
ab = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

edge = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

K = 0
for i in graph:
	K = max(K, len(graph[i]))
color = list(range(1, K+1))

def DFS(i, color_from):  # color_fromからきた色を使わない
	tmp = -1
	for node in graph[i]:	
		if not edge[i][node]:
			use_color = color[tmp]
			if use_color == color_from:
				use_color = color[tmp-1]
				tmp -= 1
			tmp -= 1
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

print(K)
for a, b in ab:
	print(edge[a-1][b-1])


### 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

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

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

	# edge = [[0]*N for _ in range(N)]
	edge = defaultdict(int)
	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


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

n,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

l = [1]
now = 1
next = a[0]
notloop = 0
dupl = -1

for i in range(k):
  now = next
  next = a[now-1]
  
  if now in l:
    dupl = now
    break
  else:
    l.append(now)
    
if(dupl == -1):
  print(now)

else:
  notloop = l.index(dupl)
  length = len(l)-notloop
  print(l[(k-notloop)%length+notloop])


### FIXED CODE ###

n,k = (int(x) for x in input().split())
a = tuple([int(x) for x in input().split()])
 
c = [0] + [-1]*(n)
l = [1]
now = 1
dupl = -1

for i in range(k):
  now = a[now - 1]
  c[now - 1] += 1
   
  if c[now - 1] == 1:
    dupl = now
    break
  else:
    l.append(now)
    
if dupl == -1:
  print(now)
  exit()
       
notloop = l.index(dupl)
length = len(l)-notloop
print(l[(k-notloop)%length+notloop])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import *

"""
とりあえず何通りあるかを数える：各頂点を通る時点での場合の数
最後に衝突する方法を除外する：頂点での衝突、辺での衝突
辺での衝突：距離を見れば分かる
"""

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,d = map(int,input().split())
    graph[u].append((v,d))
    graph[v].append((u,d))

def dijkstra(S,T):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[0] = 1
    q = [(0,S,0)] # 距離、場所、直前
    while q:
        d,x,pred = heappop(q)
        if dist[T] < d:
            break
        if dist[x] < d:
            continue
        if dist[x] == d:
            cnt_path[x] += cnt_path[pred]
            cnt_path[x] %= MOD
            continue
        dist[x] = d
        cnt_path[x] = cnt_path[pred]
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            heappush(q,(d+dy,y,x))
    return dist, cnt_path

dist_S, cnt_path_S = dijkstra(S,T)
dist_T, cnt_path_T = dijkstra(T,S)

D = dist_S[T]
# 最短路の組
answer = cnt_path_S[T] * cnt_path_T[S]
# 頂点での衝突
for x in range(1,N+1):
    if dist_S[x] == dist_T[x]:
        t = cnt_path_S[x] * cnt_path_T[x] % MOD
        answer -= t * t % MOD
# 辺での衝突。S側がx、T側がy
for x in range(1,N+1):
    for y,d in graph[x]:
        dx = dist_S[x]
        dy = dist_T[y]
        if dx + dy + d == D and dx + d > dy and dy + d > dx:
            t = cnt_path_S[x] * cnt_path_T[y] % MOD
            answer -= t * t % MOD

answer %= MOD
print(answer)



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import *

"""
とりあえず何通りあるかを数える：各頂点を通る時点での場合の数
最後に衝突する方法を除外する：頂点での衝突、辺での衝突
辺での衝突：距離を見れば分かる
"""

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,d = map(int,input().split())
    graph[u].append((v,d))
    graph[v].append((u,d))

def dijkstra(S):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[S] = 1
    q = [(0,S)] # 距離、場所
    while q:
        d,x = heappop(q)
        if dist[x] < d:
            continue
        dist[x] = d
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            if d + dy == dist[y]:
                cnt_path[y] += cnt_path[x]
                continue
            cnt_path[y] = cnt_path[x]
            dist[y] = d + dy
            heappush(q,(d+dy,y))
    return dist, cnt_path

dist_S, cnt_path_S = dijkstra(S)
dist_T, cnt_path_T = dijkstra(T)

D = dist_S[T]
# 最短路の組
answer = cnt_path_S[T] * cnt_path_T[S]
# 頂点での衝突
for x in range(1,N+1):
    if dist_S[x] == dist_T[x]:
        t = cnt_path_S[x] * cnt_path_T[x] % MOD
        answer -= t * t % MOD
# 辺での衝突。S側がx、T側がy
for x in range(1,N+1):
    for y,d in graph[x]:
        dx = dist_S[x]
        dy = dist_T[y]
        if dx + dy + d == D and dx + d > dy and dy + d > dx:
            t = cnt_path_S[x] * cnt_path_T[y] % MOD
            answer -= t * t % MOD

answer %= MOD
print(answer)
### BUGGY CODE ###

N, Q = map(int, input().split())
C = list(map(int, input().split()))

I = [[] for _ in range(N)]#各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [-1 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [(tuple(map(lambda a: int(a)-1, input().split())), i) for i in range(Q)] #クエリ
S.sort(key = lambda a: (a[0][1], a[0][0])) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  while S and S[-1][0][1] == j:#クエリへの返答
    s = S.pop()
    ans[s[1]] = BIT_query(s[0][1]+1) - BIT_query(s[0][0])
    
    
  if loc[j] >= 0: #最右端の玉である場合
    c = loc[j]
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c
       
for a in ans:
  print(a)


### FIXED CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

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

n=int(input())
L=list(map(int,input().split()))
count=0
import itertools
Lists=list(itertools.combinations(L,3))
for abc in Lists:
    if (abs(abc[0]-abc[1])<abc[2]) and (abc[2]<abc[1]+abc[0]):
        count+=1
print(count)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
L = list(map(int, input().split()))
L.sort()
# a,b,cの順序に大きいとして、6倍…はしなくていいのか。組み合わせらしい
# a-c<b<a+c
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        p = L[i]
        q = L[j]
        hidari = max(i + 1, bisect_left(L, q - p + 1))
        migi = min(j - 1, bisect_right(L, p + q - 1))
        delta = migi - hidari
        if delta >= 0:
            cnt += delta + 1
print(cnt)
### BUGGY CODE ###

def m():  
    N = int(input())
    A = list(map(int, input().split()))
    times = 1
    c = 0
    while times < 10**18 and c < N:
        for i in A: 
            times *= i
            c += 1
    if times > 10**18:
        print(-1)
    else:
        print(times)
m()

### FIXED CODE ###

def m():  
    N = int(input())
    A = list(map(int, input().split()))
    times = 1
    c = 0

    for i in A: 
        if times <= 10**18 and c < N:
            times *= i
            c += 1   
    if times > 10 ** 18:
        times = -1
    if 0 in A:
        times = 0
    print(times)
m()
### BUGGY CODE ###

import numpy as np

n = int(input())
c = np.array([[0] * n] * n, dtype=np.uint8)
for i in range(n - 1):
    s = list(map(int, input().split()))
    c[s[0] - 1, s[1] - 1] = s[2]
    c[s[1] - 1, s[0] - 1] = s[2]


def calDistance_dfs(c, d, start=0):
    d[start] = 0
    stack = []
    stack.append(start)
    while len(stack) != 0:
        current = stack.pop()
        for idx, val in enumerate(c[current, :]):
            if val != 0 and d[idx] == -1:
                stack.append(idx)
                d[idx] = d[current] + val



d = np.array([-1] * n)
calDistance_dfs(c, d, 0)

for i in d:
    print(i % 2)


### FIXED CODE ###

import numpy as np


def calDistance_dfs(aList, d, node):
    stack = [node]
    d[node] = 0
    while len(stack) != 0:
        current = stack.pop()
        for v in aList[current]:
            if d[v[0]] == -1:
                stack.append(v[0])
                d[v[0]] = d[current]+v[1]


n = int(input())
adjacencyList = [[] for i in range(n)]
d = [-1] * n

for i in range(n - 1):
    s = list(map(int, input().split()))
    adjacencyList[s[0] - 1].append((s[1] - 1, s[2]))
    adjacencyList[s[1] - 1].append((s[0] - 1, s[2]))


d[0] = 0
calDistance_dfs(adjacencyList, d, 0)
for i in d:
    print(i % 2)
### BUGGY CODE ###

from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = min(distant[v]+1, distant[e])
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)


### FIXED CODE ###

from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = distant[v]+1
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = [int(a) for a in input().split()]

    score = 0
    is_high = True
    for i in range(k - 1, n):
        tmp = 1
        for j in range(k):
            tmp *= A[i - j]

        if i >= k:
            if tmp > score:
                print("Yes")
            else:
                print("No")

        score = tmp

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = [int(a) for a in input().split()]
        
    for i in range(n - k):
        if A[i + k] > A[i]:
            print("Yes")
        else:
            print("No")

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

N = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
else:
  for i in range(N):
    ans = ans*lis[i]
  if ans > 1000000000000000000:
    print(-1)
  else:
    print(ans)


### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
ans = 1
flag = True
if 0 in lis:
  print(0)
else:
  for i in range(N):
    ans = ans*lis[i]
    if ans > 1000000000000000000:
      print(-1)
      flag = False
      break
  if flag == True:
    print(ans)
### BUGGY CODE ###

import collections
import itertools
n = int(input())
s = list(input())
count = collections.Counter(s).most_common()

ans = 0
for p in itertools.product([0,1],repeat=len(count)):
  tmp =1
  for i,x in enumerate(p):
    tmp = tmp*count[i][1]**x
  ans += tmp
print((ans-1)%(10**9+7))

### FIXED CODE ###

import collections
n = int(input())
s = list(input())
count = collections.Counter(s).most_common()
ans = 1
for x in count:
  ans = ans*(x[1]+1)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
ans=0
for i in range(1,M//N+1):
    if M%i==0:
        ans=max(i,ans)

print(ans)

### FIXED CODE ###

import  fractions
import math
import bisect
N,M=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

ans=0
cnt=make_divisors(M)
tmp=bisect.bisect_right(cnt,M/N)

print(cnt[tmp-1])
### BUGGY CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from time import time
from collections import deque

# reduce q.append()
# (constant-factor optimization)


def append(d, i, j):
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        return
    dists[i][j] = d
    q.append((d, i, j))


q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            append(0, i, j)

while len(q):
    d, i, j = q.popleft()
    append(d+1, i-1, j)
    append(d+1, i+1, j)
    append(d+1, i, j-1)
    append(d+1, i, j+1)

# fast (0.01s)
ans = max(map(max, dists))
# very slow (4.2s)
# ans = max(sum(dists, []))

print(ans)


### FIXED CODE ###

from time import time
from collections import deque

# reduce q.append()
# (constant-factor optimization)


def append(d, i, j):
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        return
    dists[i][j] = d
    q.append((d, i, j))


q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            append(0, i, j)

while len(q):
    d, i, j = q.popleft()
    append(d+1, i-1, j)
    append(d+1, i+1, j)
    append(d+1, i, j-1)
    append(d+1, i, j+1)

# fast (0.01s)
ans = max(map(max, dists))
# very slow (4.2s)
# ans = max(sum(dists, []))

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

def abc176_e():
    h, w, m = map(int, input().split())
    ch = [0]*h
    cw = [0]*w
    bs = dict()
    for _ in range(m):
        hi, wi = map(lambda x: int(x)-1, input().split())
        ch[hi] += 1
        cw[wi] += 1
        bs[(hi,wi)] = 1
    mch = max(ch)
    mcw = max(cw)
    if mch == h and mcw == w:
        ans = h + w - 1
    else:
        flag = False
        for i in [x for x in range(h) if ch[x] == mch]:
            for j in [x for x in range(w) if cw[x] == mcw]:
                if bs.get((i,j)) == None:
                    flag = True
                    break
            if flag: break
        if flag: ans = mch + mcw
        else: ans = mch + mcw - 1
    print(ans)

if __name__ == '__main__':
    abc176_e()

### FIXED CODE ###

# https://atcoder.jp/contests/abc176/submissions/16124424
from collections import Counter
def abc176_e():
  h, w, m = map(int, input().split())
  H = []
  W = []
  for _ in range(m):
    hi, wi = map(int, input().split())
    H.append(hi)
    W.append(wi)
  mosth = Counter(H).most_common()[0]
  mostw = Counter(W).most_common()[0]
  ans1 = mosth[1]
  ans2 = mostw[1]
  wpair = []
  hpair = []
  for i, hi in enumerate(H):
    if hi == mosth[0]: continue
    wpair.append(W[i])
  for i, wi in enumerate(W):
    if wi == mostw[0]: continue
    hpair.append(H[i])
  if wpair:
    ans1 += Counter(wpair).most_common()[0][1]
  if hpair:
    ans2 += Counter(hpair).most_common()[0][1]
  ans = max(ans1, ans2)
  print(ans)

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

s1 = input()
s2 = s1[::-1]
q = int(input())
x = 0
for i in range(q):
    query = input().split()
    if query[0] == '1':
        x += 1
    else :
        y = x + int(query[1])
        if y % 2 == 0:
            s1 = s1 + query[2]
            s2 = query[2] + s2
        else :
            s1 = query[2] + s1
            s2 = s2 + query[2]
if x % 2 == 0:
    print(s1)
else :
    print(s2)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
flag = True
for i in range(q):
    x = input()
    if x == '1':
        flag = not flag
    else :
        if x[2] == '1' and flag :
            s.appendleft(x[4])
        elif x[2] == '2' and not flag :
            s.appendleft(x[4])
        else :
            s.append(x[4])
if flag:
    for i in s :
        print(i, end='')
else :
    for i in range(1, len(s)+1):
        print(s[-i], end='')
print('')