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

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

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res
  
  #区間[L, R)
  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))


GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  while query[st][2] == i+1 and st < Q:
    ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
    st += 1
    if st == Q:
      break

print(*ans, sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

print(*ans, sep="\n")
### BUGGY CODE ###

n = int(input())
S = [input() for _ in range(n)]
max = 0
for s in set(S):
  if max < S.count(s):
    max_words = [s]
    max = S.count(s)
  elif max == S.count(s):
    max_words.append(s)
max_words.sort()
print("\n".join(max_words))

### FIXED CODE ###

from collections import Counter
n = int(input())
S = [input() for _ in range(n)]
c = Counter(S)
max = 0
for s in set(S):
  if max < c[s]:
    max_words = [s]
    max = c[s]
  elif max == c[s]:
    max_words.append(s)
max_words.sort()
print("\n".join(max_words))
### BUGGY CODE ###

from collections import defaultdict

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

d = defaultdict(int)
s = set([])
def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            s.add(i)
            s.add(n // i)

for i in range(2):
    divisor(A[i])

for num in A:
    for key in s:
        if num % key == 0:
            d[key] += 1

ans = 1
for key, val in d.items():
    if val >= N - 1:
        ans = max(ans, key)

print(ans)

### FIXED CODE ###

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

def ABC125gcd(x, y):
    if min(x, y) == 0:
        return max(x, y)
    else:
        return ABC125gcd(y, x % y)

L = [0] * N
R = [0] * N

for i in range(1, N):
    L[i] = ABC125gcd(L[i - 1], A[i - 1])
    R[N - 1 - i] = ABC125gcd(R[N - i], A[N - i])

ans = 1
for i in range(N):
    ans = max(ans, ABC125gcd(L[i], R[i]))
print(ans)
### BUGGY CODE ###

line1= input().split(' ')
n= int(line1[0])
m= int(line1[1])

line2= input().split(' ')
hs= []
for h in line2:
	hs.append(int(h))

roads= []
for _ in range(0, m):
	line= input().split(' ')
	roads.append(line)

def is_good(x):
	height= hs[x-1]
	for road in roads:
		if road[0]==str(x):
			if hs[int(road[1])-1]>=height:
				return False
		if road[1]==str(x):
			if hs[int(road[0])-1]>=height:
				return False
	return True

ans= []
for o in range(1,n+1):
	if is_good(o):
		ans.append(o)
print(len(ans))

### FIXED CODE ###

line1= input().split(' ')
n= int(line1[0])
m= int(line1[1])

line2= input().split(' ')
hs= []
for h in line2:
	hs.append(int(h))

roads= []
for _ in range(0, m):
	line= input().split(' ')
	roads.append([int(line[0]),int(line[1])])

graph= {}
for o in range(1, n+1):
	graph[o]=[]

for road in roads:
	graph[road[0]].append(road[1])
	graph[road[1]].append(road[0])


def is_good(x):
	height= hs[x-1]
	for adj in graph[x]:
		if hs[adj-1]>= height:
			return False
	return True
	'''height= hs[x-1]
	for road in roads:
		if road[0]==str(x):
			if hs[int(road[1])-1]>=height:
				return False
		if road[1]==str(x):
			if hs[int(road[0])-1]>=height:
				return False
	return True'''

ans= []
for o in range(1,n+1):
	if is_good(o):
		ans.append(o)

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

N = int(input())
A = list(map(int,input().split()))
b = []
if N%2 == 0:
    for i in range(N):
        if i%2 == 0:
            b.append(A[i])
        else:
            b.insert(0,A[i])
else:
    for i in range(N):
        if i%2 == 1:
            b.append(A[i])
        else:
            b.insert(0,A[i])
print(*b)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
B = deque()

if N % 2 == 0:
	for i in range(N):
		if i % 2 == 0:
			B.append(A[i])
		else:
			B.appendleft(A[i])
else:
	for i in range(N):
		if i % 2 == 0:
			B.appendleft(A[i])
		else:
			B.append(A[i])
			
print(*B)
### BUGGY CODE ###

import fractions
import functools

MOD = int(1e9) + 7


def lcm(a, b):
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x, MOD - 2)


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

v = functools.reduce(lcm, A)
ans = 0
for a in A:
    ans = (ans + v // a) % MOD
print(ans)


### FIXED CODE ###

import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A
p = [False] * MAX_A

def prime():

    for i in range(2, MAX_A):
        p[0] = p[1] = True
        if not p[i]:
            j = 2 * i
            while j < MAX_A:
                p[j] = True
                j += i

prime()

for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            ii = a // i
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i
            c2 = 0
            while not p[ii] and a % ii == 0:
                c2 += 1
                a //= ii
            facts[i] = max(facts[i], c1)
            facts[ii] = max(facts[ii], c2)
        i += 1
    if not p[a]:
        facts[a] = max(facts[a], 1)

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

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

import copy
import math

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

for k in range(n):
    B = copy.copy(A)
    B.pop(k)
#    print()
#    print(k, B)
    Num = list(set(B))
    
    count = 0
    for num in Num:
        count += nC2(B.count(num))
#        print(num, B.count(num))
    print(count)

### FIXED CODE ###

import copy
from collections import Counter

l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
c = Counter

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

count = 0
C = Counter(A)
for num in C.values():
    count += num*(num-1)//2
#print(count)

for a in A:
    print(count - (C[a] - 1))
### BUGGY CODE ###

n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(s + 1):
        DP[i][j] += DP[i - 1][j]
        if j >= A[i - 1]:
            DP[i][j] += DP[i - 1][j - A[i - 1]]
        if j == A[i - 1] or j == 0:
            DP[i][j] += 1
        DP[i][j] %= p
ans = 0
for i in range(1, n + 1):
    ans += DP[i][s]
    ans %= p
print(ans)


### FIXED CODE ###

n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(s + 1):
        DP[i][j] += DP[i - 1][j]
        if j >= A[i - 1]:
            DP[i][j] += DP[i - 1][j - A[i - 1]]
        if j == A[i - 1] or j == 0:
            DP[i][j] += 1
        DP[i][j] %= p
ans = 0
for i in range(1, n + 1):
    ans += DP[i][s]
    ans %= p
print(ans)
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
A = [[1000000]*N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    A[a-1][b-1] = A[b-1][a-1] = c

# Warshall-Floyd
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

res = 1000000000
for perm in itertools.permutations([x-1 for x in r]):
    cost = 0
    for i in range(R-1):
        cost += A[perm[i]][perm[i+1]]
    if cost < res:
        res = cost

print(res)


### FIXED CODE ###

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
A = [[1 << 64]*N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    A[a-1][b-1] = A[b-1][a-1] = c

# Warshall-Floyd
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

res = 1 << 64
for perm in itertools.permutations([x-1 for x in r]):
    cost = 0
    for i in range(R-1):
        cost += A[perm[i]][perm[i+1]]
    if cost < res:
        res = cost

print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
S = input()
Q = int(input())
#S = "a"*100000
#Q = 200000
pre = ""
suf = ""

rev = 0
for i in range(Q):
    q = input().split()
    '''
    if i % 3 == 0:
        q = ('1')
    if i % 3 == 1:
        q = (2,'1','b')
    if i % 3 == 2:
        q = (2,'2','b')
        '''

    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        f = f.decode()
        c = c.decode()
        if f == '1':
            if rev == 0:
                pre += c
            else:
                suf += c
        else:
            if rev == 0:
                suf += c
            else:
                pre += c

S = S.decode()[:-1]
ans = pre[::-1] + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
S = input()
Q = int(input())
#S = "a"*100000
#Q = 200000
pre = ""
suf = ""

rev = 0
for i in range(Q):
    q = input().split()
    '''
    if i % 3 == 0:
        q = ('1')
    if i % 3 == 1:
        q = (2,'1','b')
    if i % 3 == 2:
        q = (2,'2','b')
        '''

    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        f = f.decode()
        c = c.decode()
        if f == '1':
            if rev == 0:
                pre += c
            else:
                suf += c
        else:
            if rev == 0:
                suf += c
            else:
                pre += c

S = S.decode()[:-1]
ans = pre[::-1] + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

expect_value = [0]*N

for i in range(N):
    expect_value[i] = ((p[i] * (p[i]+1))/2) * (1/p[i])

ans = 0
for i in range(N - K + 1):
    if ans < sum(expect_value[i:i+K]):
        ans = sum(expect_value[i:i+K])
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))


def cal_expect(value):
    return ((value*(value+1))/2)*(1/value)

expect_value = [0]*N
expect_value[0] = cal_expect(p[0])

for i in range(1,K):
    expect_value[i] += expect_value[i-1] + cal_expect(p[i])

for i in range(K,N):
    expect_value[i] = expect_value[i-1] + cal_expect(p[i]) - cal_expect(p[i - K])

print(max(expect_value))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
counter = 0
ans = 0

for i in range(0, n):
  for j in range(0, i):
    if p[i] > p[j]:
      counter += 1
  if counter == 0:
    ans += 1
  counter = 0
print(ans)   

### FIXED CODE ###

import numpy as np

n = int(input())
P = np.array(list(map(int, input().split())))
T = np.zeros(n)
T[0] = P[0]
for i in np.arange(1,n,1):
    T[i] = min(T[i-1], P[i])
print(np.sum(P==T))
### BUGGY CODE ###

import math

def cost_compare(v,w,L,K,Z):
    if w in L:
        return min(K[v]+Z,K[w])
    elif w in K:
        return K[w]
    else:
        return K[v]+Z

T=int(input())


f=True
for t in range(T):
    N,A,B,C,D=map(int,input().split())

    K={0:0} #最小のコストの辞書
    L={0:0} #Kのうち未確定のものへの制限

    g=0
    while g<=10:
        v=min(L)

        del L[v]
        
        m=cost_compare(v,2*v,L,K,A)
        if (2*v in L) or (2*v not in K):
            L[2*v]=m
        K[2*v]=m

        m=cost_compare(v,3*v,L,K,B)
        if (3*v in L) or (3*v not in K):
            L[3*v]=m
        K[3*v]=m

        m=cost_compare(v,5*v,L,K,C)
        if (5*v in L) or (5*v not in K):
            L[5*v]=m
        K[5*v]=m

        m=cost_compare(v,v+1,L,K,D)
        if (v+1 in L) or (v+1 not in K):
            L[v+1]=m
        K[v+1]=m

        if v>=1:
            m=cost_compare(v,v-1,L,K,D)
            if (v-1 in L) or (v-1 not in K):
                L[v-1]=m
            K[v-1]=m

        if v==N:g=1
        if g!=0:
            g+=1
        
    print(K[N])


### FIXED CODE ###

T=int(input())
for i in range(T):
    N,A,B,C,D=map(int,input().split())

    M={0:0,1:D}

    def f(N):
        if N in M:
            return M[N]
        
        p,q=N//2*2,(N+1)//2*2
        r,s=N//3*3,(N+2)//3*3
        t,u=N//5*5,(N+4)//5*5
        R=min(D*N,
              D*abs(N-p)+A+f(p//2),
              D*abs(N-q)+A+f(q//2),
              
              D*abs(N-r)+B+f(r//3),
              D*abs(N-s)+B+f(s//3),
              
              D*abs(N-t)+C+f(t//5),
              D*abs(N-u)+C+f(u//5),
              )

        M[N]=R
        return R
    
    print(f(N))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(1,n+1):
    b += [a.index(i)+ 1]
print(*b)

### FIXED CODE ###

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

print(*numpy.argsort(a)+1)
### BUGGY CODE ###

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

m = n//2
INF = 10**18
dp = [[-INF]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    L = i//2-1
    R = (i+1)//2+1
    for j in range(L, R):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])


### FIXED CODE ###

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    L = i//2-1
    R = (i+1)//2+1
    for j in range(L, R):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])
### BUGGY CODE ###

N = int(input())
S = list(input())

count = 0

for first_index in range(1, N+1):
  first = S[first_index-1]
  for second_index in range(first_index, N+1):
    second = S[second_index-1]
    for third_index in range(second_index, N+1):
      third = S[third_index - 1]
      # print(first,second,third)
      if first != second and second != third and first != third and second_index - first_index != third_index-second_index:
        count += 1
      # print(count)

print(count)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count('R')*S.count('G')*S.count('B')
for i in range(N):
    for d in range(N):
        j = i+d
        k = j+d
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf]*(N)
dp[0]=0
for i in range(0,N):
  for j in range(0,K+1):
    if N<=i+j:
      break
    dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
 
print(dp[N-1])

### FIXED CODE ###

from numba import jit
import math

N, K = map(int,input().split())
h = list(map(int,input().split()))
@jit
def nya(N, K, h):
  dp=[0]*N
  for i in range(1,N):
    value=math.inf
    for j in range(1,K+1):
      if i-j<0:
        break
      value=min(value,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i]=value
  return(dp[N-1])
 
print(nya(N,K,h))
### BUGGY CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
v1 = v[::2]
v2 = v[1::2]
v1_n = Counter(v1)
v1_N =v1_n.most_common()
v2_n = Counter(v2)
v2_N = v2_n.most_common()
if len(v1_N) == 1 and len(v2_N) == 1 and v1_N[0][0] == v2_N[0][0]:
    print(int(n/2))
elif len(([k[0] for k in v1_n.items() if k[1] == max(v1_n.values())])) == 1 and len(([k[0] for k in v2_n.items() if k[1] == max(v2_n.values())])) == 1 and v1_N[0][0] == v2_N[0][0]:
    print(min(n-v1_N[0][1]-v2_N[1][1],n-v1_N[1][1]-v2_N[0][1]))
else:
    print(n-v1_N[0][1]-v2_N[0][1]) 

### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
v1 = v[::2]
v2 = v[1::2]
v1_N = Counter(v1).most_common()
v2_N = Counter(v2).most_common()
if len(v1_N) == 1 and len(v2_N) == 1 and v1_N[0][0] == v2_N[0][0]:
    print(int(n/2))
elif v1_N[0] == v2_N[0]:
    print(min(n-v1_N[0][1]-v2_N[1][1],n-v1_N[1][1]-v2_N[0][1]))
else:
    print(n-v1_N[0][1]-v2_N[0][1])
### BUGGY CODE ###

import sys
for line in sys.stdin:
    count = 0
    n = int(line)
    if n>=2: count += 1
    for i in range(3,n+1,2):
        if pow(2,i-1,i)==1: count += 1
    print(count)

### FIXED CODE ###

import sys
for line in sys.stdin:
    n = int(line)
    flag = [True]*(n+1)
    flag[0] = flag[1] = False
    for i in range(2,int(n**0.5)+1):
        if flag[i]:
            for j in range(i**2, n+1, i):
                flag[j] = False
    print(flag.count(True))
### BUGGY CODE ###

num = int(input())
ans = 0
for x in range(num):
    for y in range(num):
        val = (x+1) * (y+1)
        if val < num: ans += 1
        else: break
print(ans)

### FIXED CODE ###

num = int(input())
ans = 0
for x in range(num):
    if num % (x + 1) == 0: ans += num // (x + 1) - 1
    else: ans += num // (x + 1)
print(ans)
### BUGGY CODE ###

# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)


### FIXED CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

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

H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
N = [[-1]*W for i in range(H)]
for i in range(H):
  Bs = [-1]
  for j in range(W):
    if S[i][j] == "#":
      Bs.append(j)
  Bs.append(W)
  for k in range(1, len(Bs)):
    n = Bs[k]-Bs[k-1]-1
    for j in range(Bs[k-1]+1, Bs[k]):
      N[i][j] = n
M = [[-1]*W for i in range(H)]
for j in range(W):
  Bs = [-1]
  for i in range(H):
    if S[i][j] == "#":
      Bs.append(i)
  Bs.append(H)
  for k in range(1, len(Bs)):
    n = Bs[k]-Bs[k-1]-1
    for i in range(Bs[k-1]+1, Bs[k]):
      M[i][j] = n
rs = []
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      r = N[i][j]+M[i][j]-1
      rs.append(r)
r = max(rs)
print(r)


### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
L = [[-1]*W for i in range(H)]
R = [[-1]*W for i in range(H)]
U = [[-1]*W for i in range(H)]
D = [[-1]*W for i in range(H)]
for i in range(H):
  n = -1
  for j in range(W):
    if S[i][j] == "#":
      n = j
    L[i][j] = j-n
  n = W
  for j in reversed(range(W)):
    if S[i][j] == "#":
      n = j
    R[i][j] = n-j
for j in range(W):
  n = -1
  for i in range(H):
    if S[i][j] == "#":
      n = i
    U[i][j] = i-n
  n = H
  for i in reversed(range(H)):
    if S[i][j] == "#":
      n = i
    D[i][j] = n-i
#for i in range(H):
#  print(D[i])
r = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      r = max(r, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(r)
### BUGGY CODE ###

s = input()
n = int(input())
re = 0
for i in range(n):
    a = list(input().split())
    if a[0] == '1':
        re = 1 if re==0 else 0
    else:
        if a[1] == '1':
            s = a[2]+s if re==0 else s+a[2]
        else:
            s = a[2]+s if re==1 else s+a[2]
if re == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
n = int(input())
re = 0
st = ''
en = ''
for i in range(n):
    a = list(input().split())
    if a[0]=='1':
        re = 1 if re==0 else 0
    else:
        if a[1]=='1':
            if re==0:
                s.appendleft(a[2])
            else:
                s.append(a[2])
        else:
            if re==0:
                s.append(a[2])
            else:
                s.appendleft(a[2])
if re==1:
    s.reverse()
res = list(s)
print(''.join(res))