Harryxun/stf_run huggingface dataset:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,0))

  ind=0
  while len(q)>0:
    ind+=1
    if ind>10**8:
      break

    y,x,cnt=q.pop()
    counter[y][x]=cnt
    visit_counter[y][x]+=1

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())
import sys

class Deque:
    class Cell2:
        def __init__(self, x, y = None, z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = Deque.Cell2(None)
        head.next = head        
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self, x):
        h = self.head
        q = h.next
        p = Deque.Cell2(x, q, h)
        h.next = p
        q.prev = p
        self.size += 1

    def pop_back(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.prev
        p = q.prev
        p.next = h
        h.prev = p
        self.size -= 1
        del gc.garbage[:]
        return q.data

    def pop_front(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.next
        p = q.next
        p.prev = h
        h.next = p
        self.size -= 1
        del gc.garbage[:]
        return q.data

    def delete(self,x):
        h=self.head.next
        while h.data!=x:
            h=h.next
            if h==self.head: return
        q=h.next
        p=h.prev
        q.prev=p
        p.next=q
        self.size -= 1
        del gc.garbage[:]
        return

    def __str__(self):
        if self.size == 0: return
        buff = ''
        n = self.size
        cp = self.head.next
        while n > 1:
            buff += '%s ' % cp.data
            cp = cp.next
            n -= 1
        buff += '%s' % cp.data
        return buff
    
A=Deque()
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.push_front(int(s[1]))
    elif s[0] == 'delete':
        A.delete(int(s[1]))
    elif s[0] == 'deleteFirst':
        A.pop_front()
    elif s[0] == 'deleteLast':
        A.pop_back()
    n -=1
    
    print A
    print

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
s = input().split()
print(s)
if s[0][-1]==s[1][0] and s[1][-1]==s[2][1]:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s = input().split()
if s[0][-1]==s[1][0] and s[1][-1]==s[2][0]:
    print("YES")
else:
    print("NO")
n,x = map(int,input().split())
l = list(map(int,input().split()))
d = 0
cnt = 0
for i in range(n+1):
	cnt += 1
	d += l[i]
	if x < d:
		print(cnt)
		exit()




### FIXED CODE ###

n,x = map(int,input().split())
l = list(map(int,input().split()))
d = [0]

for i in range(n):
	d.append(d[i] + l[i])

ans  = 0
for i in range(n+1):
	if d[i] <= x:
		ans += 1

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

A.sort(reverse=True)
if A[M]>=sum(A)/(4*M):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

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

A.sort(reverse=True)
if A[M-1]>=sum(A)/(4*M):
  print('Yes')
else:
  print('No')
N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    w=1/(4/N-1/h-1/n)
    if abs(w-int(w))<10**(-6) and w>0:
      print(h,n,int(w),sep=" ")
      exit(0)

### FIXED CODE ###

N=int(input())
for h in range(int(N/4),3501):
  for n in range(h,3501):
    a=(4*h*n-N*(n+h))
    if a!=0:
      w=N*h*n/a
      if w==int(w) and 0<w<1000000000000:
        print(h,n,int(w),sep=" ")
        exit(0)
import math

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

ans = 1

if N == 1 :
    ans = A[0]
else :
    for i in range(N) :
        B = A[:i-1] + A[i:] # i番目を除く
        gcd = B[0]
        for b in B[1:] :
            gcd = math.gcd(gcd,b)
            if gcd == 1:
                break
        else :
            ans = max(ans,gcd)

print(ans)


### FIXED CODE ###

def gcd(a,b) :
    r = a % b
    if r == 0 :
        return b
    else :
        return gcd(b,r)

N = int(input())

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

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

for i in range(N) :  # iより左(右)
    if i == 0 :
        L[i] = A[i]
        R[-i-1] = A[-i-1]
    else :
        L[i] = gcd(L[i-1], A[i-1])
        R[-i-1] = gcd(R[-i],A[-i])

ans = 1

for i in range(N) :
    if i == 0 :
        new = R[i]
    elif i == N-1 :
        new = L[i]
    else :
        new = gcd(L[i],R[i])
    if ans < new :
        ans = new

print(ans)
S , W = (int(a) for a in input().split())
if S <= W :
    prit("unsafe")
else : print("safe")

### FIXED CODE ###

S , W = (int(a) for a in input().split())
if S <= W :
    print("unsafe")
else : print("safe")
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

left = 0
right = 10 ** 9

# able(X) を、すべての丸太を X 以下の長さに切れる場合 1 , そうでない場合 0 を返す関数とする
# 二分探索によって、able(X) が 1 に切り替わる X 点を見つける


def able(x):
    count = 0
    for i in range(N):
        if A[i] % x:
            count += A[i] // x
        else:
            count += A[i] // x - 1

    if count <= K:
        return True
    else:
        return False


while left < right:
    mid = left + (right - left) // 2
    if able(mid):
        right = mid
    else:
        left = mid + 1

print(left)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

ng = 0
ok = 10 ** 9

# able(X) を、すべての丸太を X 以下の長さに切れる場合 1 , そうでない場合 0 を返す関数とする
# 二分探索によって、able(X) が 1 に切り替わる X 点を見つける


def able(x):
    count = 0
    for i in range(N):
        if A[i] % x:
            count += A[i] // x
        else:
            count += A[i] // x - 1

    if count <= K:
        return True
    else:
        return False


while ok - ng > 1:
    mid = ng + (ok - ng) // 2
    if able(mid):
        ok = mid
    else:
        ng = mid

print(ok)
import math

def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

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

if len(A) == 1:
  print(N)
  exit()

if A[0] == 1 and A[1] == 1:
  print(N)
  exit()
if A[0] == 1 and A[1] != 1:
  print(N - 1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      if x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N:
      if x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(i):
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)


### FIXED CODE ###

X = list(map(int, input().split()))

for i in range(len(X)):
  if X[i] == 0:
    print(i + 1)
N, A, B = list(map(int, input().split()))
res = 0
for i in range(N+1):
  if A <= sum([int(s) for s in int(i)]) <= B:
    res += i
print(res)

### FIXED CODE ###

N, A, B = list(map(int, input().split()))
print(sum(i for i in range(1,N+1) if A<=sum(map(int,str(i)))<=B))
# coding: utf-8
# Here your code !
N=int(input())
b=input()
c=b.split(" ")
d=map(int,c)
a=list(d)
sum_a=abs(sum(a))
ans=sum_a%2
if sum_a==0:
    A=map(abs,a)
    B=list(A)
    ans2=min(B)
    print(ans2*2)
else:
    print(ans)

### FIXED CODE ###

# coding: utf-8
# Here your code !
a=input()
b=a.split(" ")
A=int(b[0])
B=int(b[1])

C=A+B
if C%3==0 or A%3==0 or B%3==0:
    print("Possible")
else:
    print("Impossible")
while True:
 a,b=sorted([int(x) for x in input().split])
 if a==0 and b == 0 : break
 print(a,b)


### FIXED CODE ###

while True:
 a,b=sorted([int(x) for x in input().split()])
 if a==0 and b == 0 : break
 print(a,b)
N=int(input())
h=[0 for i in n+1]
h=list(map(int,input().split()))



### FIXED CODE ###

N=int(input())
h=[0 for i in range(N+1)]
h=list(map(int,input().split()))
dp=[0 for i in range(N+1)]
for i in range(1,N):
  if(i==1):
    dp[i]=dp[i]+abs(h[i]-h[i-1])
  else:
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])
N, X, D = map(int, input().split())

M = (N * (N+1)) // 2 + 1
print(M) if X // D != 0 else 0


### FIXED CODE ###

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

    N, x, d = map(int, input().split())

    if d == 0:
        if x:
            print(N+1)
        else:
            print(1)
        exit()

    if d < 0:
        x = x + d * (N-1)
        d *= -1
    dic = defaultdict(list)

    for i in range(N+1):
        mod = (x * i) % d
        st = (i * (i+1)) // 2
        ed = (i * (N + N-i+1)) // 2
        st = st * d + (x-d) * i
        ed = ed * d + (x-d) * i
        dic[mod].append((st, ed))
    ans = 0
    for mod in dic:
        L = dic[mod]
        L.sort(key=lambda t: t[0])
        ed_prev = L[0][0] - 1
        for st, ed in L:
            if st > ed_prev:
                ans += (ed - st) // d + 1
                ed_prev = ed
            elif ed > ed_prev:
                ans += (ed - ed_prev) // d
                ed_prev = ed
    print(ans)


if __name__ == '__main__':
    main()
a,b,c,k = map(int,input().split())

if a+b>=k:
  print(a)
else:
  print(a-(k-a-b))


### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
  print('Yes')
else:
  print('No')
from numpy import cumsum
n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
p=cumsum(p)
print((p[k-1]))

### FIXED CODE ###

from numpy import cumsum
n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
p=cumsum(p)
print((p[k-1]))
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(sum(score, []))
  
h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si  in range(h):
    for sj in range(w):
        memo.append((si, sj))
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

### FIXED CODE ###

print(chr(ord(input())+1))
n,k=map(int,input().split())
a=list(map(int,input()split()))
s=max(a)
print(max(2*s-n-1))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=max(a)
print(max(2*s-n-1,0))
n=int(input())
n=list(str(n))
if n[0]==n[1] or n[1]==n[2] or n[2]==n[3]:
  print("Bad")
else:
  print("Good")


### FIXED CODE ###

n=str(input())
n=list(n)
if n[0]==n[1] or n[1]==n[2] or n[2]==n[3]:
  print("Bad")
else:
  print("Good")
import math
while(True):
    if input() == '0':
        break
    a = list(map(int, input().split()))
    m = sum(a) / len(a)
    b = 0
    for i in a:
        b += (i - m) ** 2.0
    stddev = math.sqrt(b / n)
    print(stddev)


### FIXED CODE ###

import math
while(True):
    if input() == '0':
        break
    a = list(map(int, input().split()))
    m = sum(a) / len(a)
    b = 0
    for i in a:
        b += (i - m) ** 2.0
    stddev = math.sqrt(b / len(a))
    print(stddev)
a,b = input().split()
t = int(a+b)
print("Yes" if t == int(c**0.5)**2 else "No")


### FIXED CODE ###

a,b = input().split()
t = int(a+b)
flag = False
for i in range(t//2 + 1):
    if i**2 == t:
        flag = True
        break
if flag: print("Yes")
else: print("No")
(A, V) = map(lambda a: double(a), input().split())
(B, W) = map(lambda a: double(a), input().split())
T = double(input())

D = abs(A - B)
X = abs(V - W)

if (X*T >= D):
  print("YES")
else:
  print("NO")



### FIXED CODE ###

(A, V) = map(lambda a: float(a), input().split())
(B, W) = map(lambda a: float(a), input().split())
T = float(input())

D = abs(A - B)
X = V - W

if (X*T >= D):
  print("YES")
else:
  print("NO")
n=int(input().split())
dic={n:1}
i=1
while True:
  if n%2==0:
    n=n//2
  else:
    n=3*n+1
  i+=1
  if n in dic:
    print(dic[n])
    break
  else:
    dic[n]=i

### FIXED CODE ###

s = int(input())

used = set()
used |= {s}
count = 1

while True:
    if s % 2 == 0: s//=2
    else:s=3*s+1
    if s in used:
        print(count+1)
        break
    else:
        used |= {s}
        count += 1
a, b = map(int,input().split())
def gcd(a,b):
    x = max(a,b)
    y = min(a,b)
    while x // y != 0:
        z = x // y
        y = z
        return z
print(int(a * b / gcd(a,b)))

### FIXED CODE ###

a = int(input())
b = int(input())
if a == 1 and b == 2 or a == 2 and b == 1:
  print("3")
elif a == 1 and b == 3 or a == 3 and b ==1:
  print("2")
else:
  print("1")
import sys
sys.setrecursionlimit(10000000)

n, x = map(int, input().split())

num = [0] * (n + 1)
num_p = [0] * (n + 1)
num_h = [0] * (n + 1)
num[0] = 1
num_p[0] = 1

for i in range(1, n + 1):
    num[i] = num[i - 1] * 2 + 3
    num_p[i] = num_p[i - 1] * 2 + 1

for i in range(n + 1):
    num_h[i] = num[i] // 2 + 1

# idx 番目までに含むPの数を返す
def func(idx, n):
    if idx <= n:
        ret = 0

    if idx == num_h[n]:
        ret = num_p[n - 1] + 1

    if idx > num_h[n]:
        ret = num_p[n] - func(num[n] - idx, n)

    if idx < num_h[n - 1]:
        ret = func(x, n)

    return ret

print(func(x, n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

n, x = map(int, input().split())

num = [0] * (n + 1)
num_p = [0] * (n + 1)
num_h = [0] * (n + 1)
num[0] = 1
num_p[0] = 1

for i in range(1, n + 1):
    num[i] = num[i - 1] * 2 + 3
    num_p[i] = num_p[i - 1] * 2 + 1

for i in range(n + 1):
    num_h[i] = num[i] // 2 + 1

# idx 番目までに含むPの数を返す
def func(idx, n):
    if idx == 1 and n == 0:
        return 1
    if idx == 1 and n == 1:
        return 0
    if idx <= n or n < 0:
        return 0

    if idx == num_h[n]:
        ret = num_p[n - 1] + 1

    elif idx > num_h[n]:
        ret = num_p[n] - func(num[n] - idx - 1, n - 1)

    elif idx < num_h[n]:
        ret = func(idx - 1, n - 1)

    return ret

print(func(x, n))
from collections import defaultdict

N, Q = map(int, input().split())
e = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    e[a].append(b)
    e[b].append(a)

q = []
for i in range(Q):
    p, x = map(int, input().split())
    q.append((p, x))

seen = [False] * (N + 1)

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


def dfs(e, v):
    seen[v] = True
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v)
            subtree[v].extend(subtree[next_v])

    subtree[v].append(v)


dfs(e, 1)
ans = [0] * (N + 1)
for i in q:
    for j in subtree[i[0]]:
        ans[j] += i[1]

print(*ans[1:])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
e = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    e[a].append(b)

q = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    q[p] += x

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])
N = int(input())

d = {}
x = [0] * N
y = [0] * N
from collections import defaultdict
for i in range(N):
    x[i], y[i] = map(int, input().split())

d = defaultdict(int)
for i in range(N):
    for j in range(N):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if i == j:
            continue
        d[(dx, dy)] += 1

print(N - max(d.values()))

### FIXED CODE ###

N = int(input())

d = {}
x = [0] * N
y = [0] * N
from collections import defaultdict
for i in range(N):
    x[i], y[i] = map(int, input().split())

d = defaultdict(int)
for i in range(N):
    for j in range(N):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if i == j:
            continue
        d[(dx, dy)] += 1
        
if N == 1:
    print(1)
else:
    print(N - max(d.values()))
n, m = [int(i) for i in input().split()]
al = [set() for _ in range(n)]
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    al[x-1].add(y-1)

dp = [-1] * n


def rec(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for nv in al[v]:
        ret = max(ret, rec(nv) + 1)
    dp[v] = ret
    return ret


ans = 0
for v in range(n):
    ans = max(ans, rec(v))

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(2 << 28)

n, m = [int(i) for i in input().split()]
al = [set() for _ in range(n)]
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    al[x-1].add(y-1)

dp = [-1] * n


def rec(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for nv in al[v]:
        ret = max(ret, rec(nv) + 1)
    dp[v] = ret
    return ret


ans = 0
for v in range(n):
    ans = max(ans, rec(v))

print(ans)
n = int(input())
pL = [input() for i in range(n)]
print(int(sum(pL)-(max(pL)/2)))

### FIXED CODE ###

n = int(input())
pL = [int(input()) for i in range(n)]
print(int(sum(pL)-(max(pL)/2)))
s = input()
k = int(input())


count = 0
for i in range(len(s)):
  if s[i] == "1":
    count = i
  else:
    st = s[i]
    break
if count ==0:
  print(st)
elif k <= count+1:
  print(1)
else:
  print(st)

### FIXED CODE ###

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


count = 0
for i in range(len(s)):
  if s[i] == "1":
    count = i+1
  else:
    st = s[i]
    break

if k <= count:
  print(1)
else:
  print(st)
ab=raw_input().split()
a=int(ab[0])
b=int(ab[1])
num=1
if a <=0 and b>=0:
    print 'Zero'
else:
    for val in range(a,b+1,1):
        num*=val
    if num > 0:
        print 'Positive'
    elif num==0:
        print 'Zero'
    else :
        print'Negative'

### FIXED CODE ###

ab=raw_input().split()
a=int(ab[0])
b=int(ab[1])
num=1
if a <=0 and b>=0:
    print 'Zero'
elif a>0:
    print 'Positive'
elif (b-a)%2==0:
    print 'Negative'
else:
    print'Positive'
import numpy as np

N = int(input())
T = list(map(int, input().split()))
M = int(input())
for i in range(len(M)):
    P, X = map(int(input().split()))
    
    T_new = T
    T_new[P[i]] = X
    print(np.array(T_new).sum())

### FIXED CODE ###

import numpy as np

N = int(input())
T = list(map(int, input().split()))
M = int(input())
for i in range(M):
    P, X = map(int, input().split())
    
    T_new = T.copy()
    T_new[P-1] = X
    print(np.array(T_new).sum())
n=input()
a=0
for i in n:
  a+=int(n[i])
print("Yes") if int(n)//a else prit("No")

### FIXED CODE ###

n=input()
a=0
for i in n:
  a+=int(i)
print("Yes") if int(n)%a==0 else print("No")
import sys
sys.setrecursionlimit(10**6)

[h,w] = [int(i) for i in input().split()]
mod = 10**9+7
a = [["#"]*(w+2)]
for i in range(h):
    tmp = ["#"]
    s = input()
    for j in range(w):
        tmp.append(s[j])
    tmp.append("#")
    a.append(tmp)
a.append(["#"]*(w+2))


dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[1][i] == "#":
        addi = 0
    dp[1][i] += addi
addi = 1
for i in range(1,w+1):
    if a[i][1] == "#":
        addi = 0
    dp[i][1] += addi
"""
#print(dp)
def rec(stage,y,x,dp_c):
    #print(y,x)
    if stage[y][x] == "#":
        return 0
    else:
        dp_c[y][x] = max(dp_c[y][x],rec(stage,y-1,x,dp_c) + rec(stage,y,x-1,dp_c))%(10**9+7)
        return dp_c[y][x]
rec(a,h,w,dp)
"""
for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "#":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])
#for i in range(h+2):
#    print(dp[i])


### FIXED CODE ###

[h,w] = [int(i) for i in input().split()]
mod = 10**9+7
a = [["#"]*(w+2)]
for i in range(h):
    tmp = ["#"]
    s = input()
    for j in range(w):
        tmp.append(s[j])
    tmp.append("#")
    a.append(tmp)
a.append(["#"]*(w+2))

dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[i][1] == "#":
        addi = 0
    dp[i][1] += addi
addi = 1
for i in range(2,w+1):
    if a[1][i] == "#":
        addi = 0
    dp[1][i] += addi


for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "#":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])
#for i in range(h+2):
#    print(dp[i])
def main():
    n = int(input())
    ls1 = list(input())
    ls2 = list(input())

    if ls1[0]==ls2[0]:
        ans = 3
        i =1
        flg = "b"
    else:
        ans = 3
        flg = "a"
        i =2

    while 1:


        if ls1[i]==ls2[i]:
            if flg == "a":
                flg = "b"
            else:
                ans = (ans*2)%(10**9+7)

            i += 1

        else:
            if flg == "a":
                ans = (ans*3)%(10**9+7)
            else:
                ans = (ans*2)%(10**9+7)
                flg = "a"

            i += 2
        if i >= n:
            break

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ls1 = list(input())
    ls2 = list(input())

    if ls1[0]==ls2[0]:
        ans = 3
        i =1
        flg = "b"
    else:
        ans = 6
        flg = "a"
        i =2

    while 1:

        if i >= n:
            break

        if ls1[i]==ls2[i]:
            if flg == "a":
                flg = "b"
            else:
                ans = (ans*2)%(10**9+7)

            i += 1

        else:
            if flg == "a":
                ans = (ans*3)%(10**9+7)
            else:
                ans = (ans*2)%(10**9+7)
                flg = "a"

            i += 2
        if i >= n:
            break

    print(ans)

if __name__ == "__main__":
    main()