Harryxun/stf_run huggingface dataset:
#122-C
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for i in range(q)]
m=[0]*(n+1)
for i in range(n):
    if s[i]=='A' and s[i+1]=='C':
        m[i+1]=m[i]+1
    else:
        m[i+1]=m[i]

for j in range(q):
    ans=m[l[j][1]-1]-m[l[j][0]-1]
    print(ans)

### FIXED CODE ###

#122-C
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for i in range(q)]
m=[0]*(n+1)
for i in range(len(s)-1):
    
    if s[i]=='A' and s[i+1]=='C':
        m[i+1]=m[i]+1
    else:
        m[i+1]=m[i]

for i in l:
    print(m[i[1]-1]-m[i[0]-1])
i = list( map( int, input().split()))
if i[0]*i[1]<=i[2]:
  return i[0]*i[1]
else:
  return i[2]


### FIXED CODE ###

a = [int(i) for i in input().split()]

if a[0]*a[1]<=a[2]:
  print(a[0]*a[1])
  
else:
  print(a[2])
s = str(input())
ans = []
for i in range(len(s) - 2):
    ans.append(abs(s[i:i+3]) - 753)
print(min(ans))

### FIXED CODE ###

s = str(input())
ans = 1000
for i in range(len(s)-2):
    x = int(s[i:i+3])
    ans = min(ans, abs(x-753))
print(ans)
a,b = map(int,input().split())

if (a＊b)%2==1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

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

if (a*b)%2==1:
  print('Yes')
else:
  print('No')
for e in iter(input,'0'):
 a=sorted([list(map(int,input().split()))for _ in[0]*int(e)],key=lambda x:x[0])
 b=sorted([list(map(int,input().split()))for _ in[0]*int(input())],key=lambda x:x[0])
 for s,t in b:
  u,v=a[0]
  x,y=s-u,t-v
  for u,v in a:
   if[u+x,v+y]not in b:break
  else:print(x,y)


### FIXED CODE ###

for e in iter(input,'0'):
 a=[[*map(int,input().split())]for _ in[0]*int(e)]
 s,t=min(a)
 b={tuple(map(int,input().split()))for _ in[0]*int(input())}
 m=max(b)[0]-max(a)[0]+s
 for x,y in b:
  if x<=m:
   for u,v in a:
    if(x+u-s,y+v-t)not in b:break
   else:print(x-s,y-t);break
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
i: int
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)


def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color

    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color


print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)
 
 
def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color
 
    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color
 
 
print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])
n = int(input())
n_p = 0
for i in range(n):
    a = int(input())
    if a == 2:
        n_p += 1
        continue
    elif a % 2 == 0:
        continue
    else:
        j = 3
        while j =< math.sqrt(a)
            if a%j == 0:
                break
            j += 2
        else:
            n_p += 1
print n_p

### FIXED CODE ###

import math
n = int(input())
n_p = 0
for i in range(n):
    a = int(input())
    if a == 2:
        n_p += 1
        continue
    elif a % 2 == 0:
        continue
    else:
        j = 3
        while j <= math.sqrt(a):
            if a%j == 0:
                break
            j += 2
        else:
            n_p += 1
print(n_p)
import numpy as np


H, N, *AB = map(int, open(0).read().split())
A = np.array(AB[::2])
B = np.array(AB[1::2])
max_A = A.max()

dp = np.zeros(H, dtype=np.int64)
for h in range(H):
    dp[h] = np.min(dp[h - A] + B)

print(dp[-1])


### FIXED CODE ###

H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
 
dp1 = np.array([[0]*T for _ in range(N+1)])
rev_AB = AB[::-1]
dp2 = np.array([[0]*T for _ in range(N+1)])


for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  
  dp1[i,:a] = dp1[i-1,:a]
  dp2[i,:rev_a] = dp2[i-1,:rev_a]
  dp1[i,a:] = np.fmax(dp1[i-1,a:],dp1[i-1,:-a]+b)
  dp2[i,rev_a:] = np.fmax(dp2[i-1,rev_a:],dp2[i-1,:-rev_a]+rev_b)

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])
 
    
print(max(lis))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))
def f(n):
    if n == 0:
        return 0
    else:
        return n + f(n-1)
a, b = list(map(int,input().split()))
i1 = 1
i2 = 2
while True:
    if b - a == f(i2) - f(i1):
        break
    i1 += 1
    i2 += 1
print(f(i1) -a)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 
def f(n):
    if n == 0:
        return 0
    else:
        return n + f(n-1)
a, b = list(map(int,input().split()))
i1 = 1
i2 = 2
while True:
    if b - a == f(i2) - f(i1):
        break
    i1 += 1
    i2 += 1
print(f(i1) -a)
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=1
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if data[i]:
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:continue
				if taisenzumi[aite-1]:continue				
				aite=data[i][0]
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
else:
	print(count)
	exit()
print(-1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()
a,b = (long(x) for x in input().split())
if a > b:#b対象
    anb1 = long(b * b) 
    anb2 = (long((a-b) * b))
    if (anb1 % 2) == 0:#偶数
        if  anb2 % 2 == 0:#anb2 偶数
            print(long(anb1/2) + long(anb2/2))
        else:#奇数
            print(long(anb1/2) + long(anb2/2))
    else:#奇数
        if  anb2 % 2 == 0:#anb2 偶数
            print(long(anb1/2 + 1) + long(anb2/2))
        else:#奇数
            print(long(anb1/2 + 1) + long(anb2/2))
            
elif a < b:#a対象            
    anb1 = long(a * a )
    anb2 = long((b-a) * a)
    if (anb1 % 2) == 0:#偶数
        if  anb2 % 2 == 0:#anb2 偶数
            print(long(anb1/2) + long(anb2/2))
        else:#奇数
            print(long(anb1/2) + long(anb2/2))
    else:#奇数
        if  anb2 % 2 == 0:#anb2 偶数
            print(long(anb1/2 + 1) + long(anb2/2))
        else:#奇数
            print(long(anb1/2 + 1) + long(anb2/2))
elif a == b:
    if a % 2 == 0:
        print(long(a / 2) * a)
    else:
        print(long((a * a) / 2) + 1)
    

### FIXED CODE ###

a,b = (int(x) for x in input().split())

            
if a == 1 or b == 1:
    print(1)
elif a > b:#b対象
    anb1 = int(b * b) 
    anb2 = (int((a-b) * b))
    if (anb1 % 2) == 0:#偶数
            print(int(anb1/2) + int(anb2/2))
    else:#奇数
            print(int(anb1/2 + 1) + int(anb2/2))
elif a < b:#a対象            
    anb1 = int(a * a)
    anb2 = int((b-a) * a)
    if (anb1 % 2) == 0:#偶数
            print(int(anb1/2) + int(anb2/2))
    else:#奇数
            print(int(anb1/2 + 1) + int(anb2/2))
elif a == b:
    if a % 2 == 0:
        print(int(a / 2) * a)
    else:
        print(int((a * a) / 2) + 1)
N=int(input())
v=list(map(int,input().split()))
v.sort()
if len(v)==1:
    print(v[0])
elif len(v)==2:
    print(float((v[0]+v[1])/2))
else:
    s=(float((v[0]+v[1])/2))
    for j in range(2,N):
        s=float((s+v[j])/2) 
print(s)

### FIXED CODE ###

N=int(input())
v=list(map(int,input().split()))
v.sort()
s=v[0]
for j in range(1,N):
    s=(s+v[j])/2
print(s)
num, capacity = list(map(int, input().split()))
dp = [[0 for i in range(capacity + 1)] for j in range(num + 1)]

for i in range(1, num + 1):
    weight, value = list(map(int, input().split())
    for w in range(capacity + 1):
        if w - weight >= 0:
            dp[i][w] = max( dp[i-1][w - weight] + value,  dp[i-1][w] )
        else:
            dp[i][w] = dp[i-1][w]
print(max( dp[num] ))

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
N = int(input())
XY_list = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        XY_list[i].append([person - 1, state])
ans = 0
for i in range(1 << N):
    bool = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for person, state in XY_list[j]:
                if (i >> person) & 1 != state:
                    bool = False
                    break
"""
        else:
            for person, state in XY_list[j]:
                if (i >> person) & 1 == state:
                    bool = False
                    break
"""
    if bool:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)


### FIXED CODE ###

N = int(input())
XY_list = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        XY_list[i].append([person - 1, state])
ans = 0
for i in range(1 << N):
    bool = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for person, state in XY_list[j]:
                if (i >> person) & 1 != state:
                    bool = False
                    break

    if bool:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)
n=int(input())
a=[]

x,y,k=-1,-1,-1
n=-1
for _ in range(n):
    a.append(list(map(int,input().split())))
    if a[_][2] != 0:
        n=i
for i in range(101):
    for j in range(101):
        h=a[0][2]+abs(a[0][0]-i)+abs(a[0][1]-j)
        d=True

        for l in range(n):
            if a[l][2] > 0 and h != a[l][2]+abs(a[l][0]-i)+abs(a[l][1]-j):
                d=False
            if a[l][2]==0 and h>abs(a[l][0]-i)+abs(a[l][1]-j):
                d=False
            
        if d:
            x,y,k=i,j,h
            print(x,y,k)
            exit()



### FIXED CODE ###

N = int(input())

if N == 1:
    print('Hello World')
else:
    A=int(input())
    B=int(input())
    print(A+B)
import sys,string
a = string.ascii_lowercase
t = string.maketrans(a,a[1:]+a[0])
        
for s in sys.stdin:
    s = s.strip()
    while not ('the' in s or 'this' in s or 'that' in s):
        s = s.translate(t)
    print s

### FIXED CODE ###

import sys,string
t = string.maketrans('abcdefghijklmnopqrstuvwxyz','bcdefghijklmnopqrstuvwxyza')
for s in sys.stdin:
	s = s.strip()
	while not ('the' in s or 'this' in s or 'that' in s):
		s = s.translate(t)
	print s
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, Q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(N-1)]
    px = [list(map(int, input().split())) for _ in range(Q)]

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    # while len(stk):
    #     print(stk, visited)
    #     v = stk.pop()
    #     if not v in visited:
    #         visited.add(v)
    #     if v>0:
    #         cnt[v] += cnt[par]
    #     for i in edge[v]:
    #         if not i in visited:
    #             stk.append(i)
    #     par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**6)

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    print(*cnt)

if __name__ == '__main__':
    resolve()
N = int(input())
A = list(map(int,input().split()))

from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

b = 0

for i in A:
    b += lcm_list(A)/i
print(int(b)%(10**9+7))


### FIXED CODE ###

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

import fractions

##def lcm_base(x, y):
##    return (x * y) // fractions.gcd(x, y)

##def lcm_list(numbers):
##    return reduce(lcm_base, numbers, 1)

ans = A[0]
for i in range(1, N):
    ans = ans * A[i] // fractions.gcd(ans, A[i])

b = 0

for i in A:
##    b += lcm_list(A)/i
    b += ans//i
print(int(b)%(10**9+7))
s = list(input())
i = len(s)
o = s.count('o')

if o >= 8:
    print('YES')
else:
    s = 15 - s
    if 8 - o <= s:
        print('YES')
    else:
        print('NO')

### FIXED CODE ###

s = list(input())
i = len(s)
o = s.count('o')

if o >= 8:
    print('YES')
else:
    i = 15 - i
    if 8 - o <= i:
        print('YES')
    else:
        print('NO')
import statistics

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

for i in range(n):
  a[i] = a[i] - (i + 1)


a.sort()
med = statistics.median(a)

n = 0

for ai in a:
  n += abs(ai - med)

print(n)


### FIXED CODE ###

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

for i in range(n):
  a[i] = a[i] - (i + 1)


a.sort()
med = a[len(a) // 2]

n = 0

for ai in a:
  n += abs(ai - med)

print(n)
s = input()
k = int(input())

count = 0
change = False

for i in range(1, len(s)):
    if s[i-1] == s[i] and not change
        count += 1
        change = True
    else:
        change = False

count2 = 0
change2 = False
for i in range(2, len(s)):
    if s[i-1] == s[i] and not change2:
        count2 += 1
        change2 = True
    else:
        change2 = False


if len(s) == 1:
    print(k//2)
elif s[0] == s[-1] and not change:
    if change2:
        print((count+count2+1)*(k//2)+count*(k%2))
    else:
        print(count+(count2+1)*(k-1))
else:
    print(count*k)

### FIXED CODE ###

s = input()
k = int(input())

count = 0
change = False
for i in range(1, len(s)):
    if s[i-1] == s[i] and not change:
        count += 1
        change = True
    else:
        change = False

count2 = 0
change2 = False
for i in range(2, len(s)):
    if s[i-1] == s[i] and not change2:
        count2 += 1
        change2 = True
    else:
        change2 = False

if len(s) == 1:
    print(k//2)
elif s[0] == s[-1] and not change:
    if change2:
        print((count+count2+1)*(k//2)+count)
    else:
        print(count+(count2+1)*(k-1))
else:
    print(count*k)
#Problem C
n, m = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(m)] #s_i, c_i

for i in range(10**n): #ぜんぶやる
    st = str(i)
    if len(i) == n and all(st[s-1] == str(c) for s, c in L): #長さ＝桁数がiで、かつ全てにおいて[s=c]すなわち[stのs番目の文字＝c]となるとき
        print(i)
        exit()

print(-1)

### FIXED CODE ###

#Problem C
n, m = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(m)] #s_i, c_i

for i in range(10**n): #ぜんぶやる
    st = str(i)
    if len(st) == n and all(st[s-1] == str(c) for s, c in L): #長さ＝桁数がiで、かつ全てにおいて[s=c]すなわち[stのs番目の文字＝c]となるとき
        print(i)
        exit()

print(-1)
import math
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	# d=1
	# rr=1
	# nr=1
	# for i in range(1,dansu+1):
		# d=d*(i%(10**9+7))
	# for i in range(1,r+1):
		# rr=rr*(i%(10**9+7))
	# for i in range(1,dansu-r+1):
		# nr=nr*(i%(10**9+7))
	
	# kotae=int(d/(rr*nr))
	kotae=math.factorial(dansu)/(math.factorial(dansu-r)*math.factorial(r))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

### FIXED CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)
import math
a,b=map(int,input().split())
g=math.gcd(a,b)
print((a*b)//g)

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
g=fractions.gcd(a,b)
print((a*b)//g)
from collections import deque
q = deque()
for _ in range(int(input())):
    c, *k = input().split()
    k = k[0] if k else None
    if c == 'insert':
        q.appendleft(k)
    elif c == 'delete':
        q.remove(k)
    elif c == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(*q)


### FIXED CODE ###

from collections import deque
from sys import stdin
q = deque()
input()
for s in stdin:
    if s == '\n':
        break
    c, *k = s.split()
    k = k[0] if k else None
    if c == 'insert':
        q.appendleft(k)
    elif c == 'delete':
        if k in q:
            q.remove(k)
    elif c == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(*q)
import math
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]

def explode(x):
    global n
    c=0
    for i in range(n):
        if h[i]-x*b>0:
            c+=math.ceil((h[i]-x*b)/(a-b))
    return c<=x

#二分探索用のコード

#(1)l,rは両端点でl<=r
l,r=1,10**9
#(2)l=rもしくはl=r-1のときにbreak
while l+1<r:
    #(3)その閉区間の中点(の小数部分を切り捨てたもの)
    #オーバーフローを考慮すると以下の書き方になる
    k=l+.round((r-l)/2)
    #ここでは境目以上のxで真になるので、
    #x=kで真の場合は大きい方の端点をkにし、x=kで偽の場合は小さい方の端点をkにする
    if explode(k):
        r=k
    else:
        l=k

print(l if explode(l) else r)

### FIXED CODE ###

import math
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]


def explode(x):
    global n
    c=0
    for i in range(n):
        if h[i]-x*b>0:
            c+=math.ceil((h[i]-x*b)/(a-b))
    return c<=x

l,r=1,10**9
while l+1<r:
    k=(l+r)//2
    if explode(k):
        r=k
    else:
        l=k

print(l if explode(l) else r)
def solve2(aa,bb,cc,dd,lv):
  a,b,c,d=aa,bb,cc,dd
  m=3**(lv-1)
  mm=2*m+1
  ab=(0--b//m)*3+(0--a//m)
  cd=(0--d//m)*3+(0--c//m)
  if ab>cd:
    ab,cd=cd,ab
    a,b,c,d=c,d,a,b
  if ab==cd:
    mx=m*((0--a//m)-1)
    my=m*((0--b//m)-1)
    a-=mx
    b-=my
    c-=mx
    d-=my
    return [2,[a,b,c,d]]
  if ab==2 and cd==8:
    ans=abs(b-d)+min(abs(a-m)+abs(c-m),abs(a-mm)+abs(c-mm))
    return [0,ans]
  if ab==4 and cd==6:
    ans=abs(a-c)+min(abs(b-m)+abs(d-m),abs(b-mm)+abs(d-mm))
    return [0,ans]
  if ab==1:
    if cd==4 or cd==7:
      ans=abs(m-d)
      d=m
    if cd==2 or cd==3:
      ans=abs(m-c)
      c=m
    return [1,ans,[a,b,c,d]]
  if ab==2 and cd==3:
    a-=m
    c-=m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==3 and (cd==6 or cd==9):
    a-=mm
    c-=mm
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==4 and cd==7:
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==6 and cd==9:
    a-=mm
    c-=mm
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==7 and (cd==8 or cd==9):
    b-=mm
    d-=mm
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==8 and cd==9:
    a-=m
    c-=m
    b-=mm
    d-=mm
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  ans=abs(a-c)+abs(b-d)
  return [0,ans]

def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  ans=0
  for lv in range(30,0,-1):
    re=solve2(a,b,c,d,lv)
    if re[0]==2:
      a,b,c,d=re[1]
    if re[0]==1:
      ans+=re[1]
      a,b,c,d=re[2]
    if re[0]==0:
      return ans+re[1]

q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

### FIXED CODE ###

def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx=my=0
  for i in range(1,31):
    if a==c and a%3==2 and abs(b-d)>=2:mx=i
    if b==d and b%3==2 and abs(a-c)>=2:my=i
    a=0--a//3
    b=0--b//3
    c=0--c//3
    d=0--d//3
  a,b,c,d=aa,bb,cc,dd
  if mx==my==0:return abs(a-c)+abs(b-d)
  if mx<my:
    ans=abs(a-c)
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    bd=(3**my)*((0--b//(3**my))-1)
    b-=bd
    d-=bd
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  if mx>my:
    ans=abs(b-d)
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ac=(3**mx)*((0--a//(3**mx))-1)
    a-=ac
    c-=ac
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))