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

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        B, C = map(int,input().split())
        for j in range(B):
            tmp = heapq.heappop(q)
            if tmp < C:
                heapq.heappush(q, C)
                total += (C - tmp)
            else:
                heapq.heappush(q, tmp)
                break

    print(total)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

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

n = int(input())
count = 0
if 1 <= n <= 10 ** 9:
    for i in range(n - 1):
        count += i + 1
    print(count)
else:
    print('hoge!')

### FIXED CODE ###

n = int(input())
if n == 0:
    print(0)
else:
    ans = n*(n-1)//2
    print(ans)
### BUGGY CODE ###

def main():
    s = input()
    a = "".join(["".join(["1"for j in range(i-4) if int(s[j:i])%2019==0]) for i in range(len(s)+1)])
    print(len(a))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

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

class Counter:
  def __init__(self):
    self.v = 0

  def increment(self):
    self.v += 1


H, W = map(int, input().strip().split())

M = [None] * H
MX = [None] * H
MY = [None] * H

for i in range(H):
  M[i] = [c == '.' for c in input().strip()]
  MX[i] = [None] * W
  MY[i] = [None] * W

max_size = 0

for i in range(H):
  for j in range(W):
    if not M[i][j]: continue

    if MX[i][j] is None:
      tmp = Counter()
      for x in range(j, W):
        if not M[i][x]: break
        MX[i][x] = tmp
        tmp.increment()

    if MY[i][j] is None:
      tmp = Counter()
      for y in range(i, H):
        if not M[y][j]: break
        MY[y][j] = tmp
        tmp.increment()

    size = MX[i][j].v + MY[i][j].v - 1
    max_size = max(max_size, size)

print(max_size)

### FIXED CODE ###

class Counter:
  def __init__(self):
    self.v = 0

  def increment(self):
    self.v += 1


H, W = map(int, input().strip().split())

M = [None] * H
MX = [None] * H
MY = [None] * H

for i in range(H):
  M[i] = [c == '.' for c in input().strip()]
  MX[i] = [None] * W
  MY[i] = [None] * W

max_size = 0

for i in range(H):
  for j in range(W):
    if not M[i][j]: continue

    if MX[i][j] is None:
      tmp = Counter()
      for x in range(j, W):
        if not M[i][x]: break
        MX[i][x] = tmp
        tmp.increment()

    if MY[i][j] is None:
      tmp = Counter()
      for y in range(i, H):
        if not M[y][j]: break
        MY[y][j] = tmp
        tmp.increment()

    size = MX[i][j].v + MY[i][j].v - 1
    max_size = max(max_size, size)

print(max_size)
### BUGGY CODE ###

import itertools,math
n=input().split()
n=[int(i) for i in n]
h=[]
for i in range(n[0]):
    h.append(int(input()))
q=[]

for j in itertools.combinations(h,n[1]):
    q.append(max(j)-min(j))

print(min(q))

### FIXED CODE ###

n=input().split()
n=[int(i) for i in n]
h=[0]*n[0]
for i in range(n[0]):
    h[i]=int(input())
h.sort()
q=-1
for i in range(0,len(h)-n[1]+1):
    a=h[i+n[1]-1]-h[i]
    if q==-1 or q>a:
        q=a
print(q)
### BUGGY CODE ###

N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()
i = 0
ans = 0

while i < N:
    t = T[i]
    x = T.count(T[i])
    ans = ans + (x-1+C)//C
    for j in range(i,N):
        if T[j]>t+K:
            y = j-i
            break
        y = N-i
            
    y=min(C,y)
    i = i + y 

print(ans)

### FIXED CODE ###

N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()
i = 0
ans = 0
time =0
p = 0

for i in range(N):
 
    if  p==0 or p ==C:
        ans = ans+1
        p =1
        time =T[i]+K
    elif p<C :
        if T[i]<=time:
            p +=1
        elif T[i]>time:
            ans =ans+1
            time=T[i]+K
            p =1

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

def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = [int(input().rstrip('\n')) for _ in range(m)]
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in a else 0
    dp[1] = 1 if 1 not in a else 0
    for i in range(2, n + 1):
        if i not in a:
            dp[i] = (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)
        else:
            dp[i] = 0
    print(dp[-1])


if __name__ == '__main__':
    slove()


### FIXED CODE ###

n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in [int(input()) for _ in range(m)]:
    dp[i] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
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
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l)
sys.stdout.flush()
ltmp = STR() #初期状態 偶数席
if ltmp == 'Vacant':
    exit()
print(r)
sys.stdout.flush()
rtmp = STR() #最終状態 奇数
if rtmp == 'Vacant':
    exit()
cnt = 2
while l < r:
    cnt += 1
    c = (l + r) // 2
    print(c)
    sys.stdout.flush()
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c + 1
        else:
            r = c - 1
    else:
        if tmp == ltmp:
            r = c - 1
        else:
            l = c + 1
print(r)
sys.stdout.flush()
tmp = STR()

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
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
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

import copy

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    #print(a)

    sum = 0
    for i in range(n):
        root = list([0])
        for j in range(n):
            if j!=i:
                root.append(a[j])
        root.append(0)
        #print(root)
        for j in range(1, n+1):
            sum += abs(root[j]-root[j-1])
        print(sum)
        sum = 0


### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    A = list([0])
    A.extend(a)
    A.append(0)

    sum = 0
    for i in range(1, n+2):
        sum += abs(A[i]-A[i-1])
    for i in range(1, n+1):
        print(sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))[::-1]
b = []
for _ in range(n):
    b.append(a.pop())
    b = b[::-1]
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if len(a)%2 == 1:
    print(*a[0::2][::-1] + a[1::2])
else:
    print(*a[1::2][::-1] + a[0::2])
### BUGGY CODE ###

p=1
n=10**9+7
for i in range(1, int(input())+1):
    p=p*i
print(p%n)

### FIXED CODE ###

p=1
n=10**9+7
for i in range(1, int(input())+1):
    p=p*i
    p=p%n
print(p)
### BUGGY CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]

for i in range(len(t)):
    for j in range(len(s)):
        if t[i] == s[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
cnt = dp[m][n]
ans = ''
while n > 0 and m > 0:
    if dp[m][n] == dp[m][n - 1]:
        n -= 1
    elif dp[m][n] == dp[m - 1][n]:
        m -= 1
    else:
        ans = s[n - 1] + ans
        n -= 1
        m -= 1

print(ans)

### FIXED CODE ###

def solve(n, m, s, t):
    dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    ans = ''
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            ans = s[n - 1] + ans
            n -= 1
            m -= 1
    print(ans)
    return

s = input()
t = input()

solve(len(s), len(t), s, t)
### BUGGY CODE ###

from collections import deque
n, q = map(int, input().split())
node = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  node[a-1].append([a-1, b-1])
  node[b-1].append([b-1, a-1])

ans = [0]*n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x

already = [[False]*n for i in range(n)]
not_yet = deque(node[0])
for k in not_yet:
  a, b = k[0], k[1]
  already[a][b] = True
  already[b][a] = True
while not_yet:
  key = not_yet.popleft()
  a, b = key[0], key[1]
  ans[b] += ans[a]
  for i in range(len(node[b])):
    p, q = node[b][i][0], node[b][i][1]
    if already[p][q] or already[p][q]:
      continue
    not_yet.append(node[b][i])
    already[p][q] = True
    already[q][p] = True
  
print(*ans)

### FIXED CODE ###

from collections import deque

def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    ans = [0]*n
    for _ in range(q):
        p, x = map(int, input().split())
        ans[p-1] += x
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    
    while not_yet:
        key = not_yet.popleft()
        for value in tree[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            ans[value] += ans[key]
    
    print(*ans)

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

from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.pop()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

for i in range(t):
    n, a, b, c, d = map(int, input().split())
    print(bfs(n, 0, a, b, c, d, n))
    
    


### FIXED CODE ###

from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.popleft()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

for i in range(t):
    n, a, b, c, d = map(int, input().split())
    print(bfs(n, 0, a, b, c, d, n))
### BUGGY CODE ###

# 累積和

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

# ナイーブな実装
def calc(l, r):
    ans = 0
    # 処理系
    for i in range(l, r+1):
        if is_prime(i) and is_prime((i+1)//2):
            ans += 1
    return ans

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(calc(l, r))


### FIXED CODE ###

# 累積和

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

# 2017数 かどうかのマップ
data = [0] * 10**5
# 処理系
for i in range(1, 10**5 + 1):
    if is_prime(i) and is_prime((i+1)//2):
        data[i-1] = 1

cumulative_sum = [0] * 10**5
cumulative_sum[0] = data[0]
for i in range(10**5 - 1):
    cumulative_sum[i+1] += cumulative_sum[i] + data[i+1]

# s_0 = 0 となるように
cumulative_sum = [0] + cumulative_sum

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(cumulative_sum[r] - cumulative_sum[l-1])
    # print(sum(data[l:r+1]))
### BUGGY CODE ###

N = int(input())
T = sorted(list(set([int(input()) for _ in range(N)])), reverse=True)
ret = 1
while len(T) > 1:
  C = int(max(T) ** 0.5)
  f = False
  for c in range(2, C + 1):
    T_ = []
    for i, t in enumerate(T):
      if t % c == 0:
        T_.append(t // c)
        f = True
      elif t < c:
        ret *= t
      else:
        T_.append(t)
    T = sorted(list(set([t for t in T_ if t >= c])), reverse=True)
    if f:
      ret *= c
      break
  else:
    break
for t in T:
  ret *= t
print(ret)

### FIXED CODE ###

from collections import deque
N = int(input())
T = list(set([int(input()) for _ in range(N)]))
ret = T[0]

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

for t in T[1:]:
  ret = ret * t // gcd(ret, t)
  
print(ret)
### BUGGY CODE ###

n = int(raw_input())
G = [[-1] * n] * n
d = [0] * n
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+2*j]] = int(v[3+2*j])
 
flag = [0] * n
tn = [0]
r = 0
while True:
    for i in range(n):
        if flag[i] == 0 and i in tn:
            flag[i] = 1
            d[i] = r
            for j in range(n):
                if G[i][j] != -1 and flag[j] == 0:
                    tn.append(j)
    if len(tn) == n:
        break
    r += 1
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]))

### FIXED CODE ###

n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))
### BUGGY CODE ###

s=input()
K=int(input())
mojiretsu=set()
for i in range(0,len(s)):
    for k in range(1,len(s)+1-i):
        mojiretsu.add(s[i:i+k])
ans=sorted(mojiretsu)
print(ans[K-1])

### FIXED CODE ###

s=input()
K=int(input())
mojiretsu=set()
for i in range(0,len(s)):
    for k in range(1,6):
        mojiretsu.add(s[i:i+k])
ans=sorted(mojiretsu)
print(ans[K-1])
### BUGGY CODE ###

l,r = map(int,input().split())

a = []
for i in range(l,r):
    for j in range(i+1,r+1):
        a.append(i*j%2019)

print(min(a))
        


### FIXED CODE ###

l,r = map(int,input().split())

a = []
r = min(r,l+2019)
for i in range(l,r):
    for j in range(i+1,r+1):
        a.append(i*j%2019)

print(min(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

memo = {}
def dfs(rest, i):
    key = (rest, i)
    if key in memo:
        return memo[key]
    if i == M:
        return [] if rest == 0 else None
    v = A[i]; c = CS[v]
    r = None
    k = 0
    while k*c <= rest:
        r0 = dfs(rest-k*c, i+1)
        if r0 is not None:
            r0 = [k] + r0
            if r is None or (sum(r) < sum(r0) or (sum(r) == sum(r0) and r < r0)):
                r = r0
        k += 1
    memo[key] = r
    return r
res = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

N, M = map(int, readline().split())
*A, = map(int, readline().split())

A.sort(reverse=1)
CS = [0,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M+1)]
mM = memo[M]
mM[0] = EMP
for i in range(1, N+1):
    mM[i] = INV
def dfs(rest, i):
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
writelines(ans)
write("\n")
### BUGGY CODE ###

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
a=0
N=int(input())
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      c=euclid(i, j)
      a+=euclid(c, k)
print(a)

### FIXED CODE ###

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
a=0
N=int(input())
for i in range(1,N+1):
  for j in range(i,N+1):
    for k in range(j,N+1):
      if i==j==k:
        a+=i
      elif i==j or j==k or i==k:
        c=euclid(i, j)
        c=euclid(c, k)
        a+=3*c
      else:
        c=euclid(i, j)
        c=euclid(c, k)
        a+=6*c
print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [[0,1], [0,-1], [1,0], [-1,0]]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)
### BUGGY CODE ###

#coding: utf-8
N,W=map(int,input().split())
w_and_v=[list(map(int,input().split())) for i in range(N)]

dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):  #i番目の荷物チェック
    w,v=w_and_v[i]
    for j in range(1,W+1):  #残りjまで荷物を持てる
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
        
print(dp[N][W])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)])

dp = np.zeros(W+1, dtype=np.int64)

for w, v in wv:
    dp[w:] = np.maximum(dp[w:], dp[:W-w+1]+v)

ans = dp[W]
print(ans)
### BUGGY CODE ###

ans = input()
n = int(input())
for i in range(n):
    query = input()
    if query == "1":
        ans = ans[::-1]
    else:
        _,option,str = query.split()
        if option == "1":
            ans = str + ans
        else:
            ans += str
print(ans)

### FIXED CODE ###

from collections import deque

def main():
    ans = deque(input())
    n = int(input())
    vec = 1
    for i in range(n):
        q = input()
        if q == "1":
            vec *= -1
        else:
            _,o,s = q.split()
            if ((o == "1") and (vec == 1)) or ((o == "2") and (vec == -1)):
                ans.appendleft(s)
            else:
                ans.append(s)
    if vec == -1:
        ans.reverse()
    ans = ''.join(ans)
    print(ans)

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

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

pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
num = len(a)
for i in range(num):
  for j in range(num):
    
    if i == j or a[i]*a[j]%4 == 0:
      continue
    else:  
      not_4 += 1
      
      if not_4 >= pair:
        ans = 'No'
        break
    
print(ans)

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')