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

def main():
    from itertools import accumulate as ac
    n, m, q = map(int, input().split())
    ten = [list(map(lambda x:x == "1", list(input()))) for _ in [0]*n]
    hen1 = [[0]*m]+[[0]+list(ac([ten[i][j] & ten[i][j+1] for j in range(m-1)]))
                    for i in range(n)]
    hen2 = [[0]*(m+1)]+[[0]+list(ac([ten[i][j] & ten[i+1][j] for j in range(m)]))
                        for i in range(n-1)]

    ten = [[0]*(m+1)]+[[0]+list(ac(j)) for j in ten]
    for i in range(n):
        for j in range(1, m+1):
            ten[i+1][j] += ten[i][j]
    for i in range(n):
        for j in range(1, m):
            hen1[i+1][j] += hen1[i][j]
    for i in range(n-1):
        for j in range(1, m+1):
            hen2[i+1][j] += hen2[i][j]

    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        ans = ten[x2][y2]+ten[x1-1][y1-1]-ten[x2][y1-1]-ten[x1-1][y2]
        ans -= hen1[x2][y2-1]+hen1[x1-1][y1-1]-hen1[x2][y1-1]-hen1[x1-1][y2-1]
        ans -= hen2[x2-1][y2]+hen2[x1-1][y1-1]-hen2[x2-1][y1-1]-hen2[x1-1][y2]
        print(ans)


main()


### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n, m, q = map(int, input().split())
    ten = [list(map(lambda x:x == "1", list(input()))) for _ in [0]*n]
    xy = [list(map(int, input().split())) for _ in [0]*q]
    ans = [0]*q

    hen = [[0]*m]+[None]*n
    for i in range(n):
        temp = [0]
        for j in range(m-1):
            temp.append(ten[i][j] & ten[i][j+1])
        hen[i+1] = list(ac(temp))
    for i in range(n):
        for j in range(1, m):
            hen[i+1][j] += hen[i][j]

    for i, (x1, y1, x2, y2) in enumerate(xy):
        ans[i] = -hen[x2][y2-1]-hen[x1-1][y1-1] + \
            hen[x2][y1-1]+hen[x1-1][y2-1]

    hen = [[0]*(m+1)]+[None]*(n-1)
    for i in range(n-1):
        temp = [0]
        for j in range(m):
            temp.append(ten[i][j] & ten[i+1][j])
        hen[i+1] = list(ac(temp))
    for i in range(n-1):
        for j in range(1, m+1):
            hen[i+1][j] += hen[i][j]

    for i, (x1, y1, x2, y2) in enumerate(xy):
        ans[i] -= hen[x2-1][y2]+hen[x1-1][y1-1] - \
            hen[x2-1][y1-1]-hen[x1-1][y2]

    del hen

    ten = [[0]*(m+1)]+ten
    for i in range(1, n+1):
        ten[i] = [0]+list(ac(ten[i]))
    for i in range(n):
        for j in range(1, m+1):
            ten[i+1][j] += ten[i][j]

    for i, (x1, y1, x2, y2) in enumerate(xy):
        print(ans[i]+ten[x2][y2]+ten[x1-1][y1-1]-ten[x2][y1-1]-ten[x1-1][y2])


main()
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

n,q = map(int,input().split())
G = [[] for i in range(n)]
for i in range(n-1):  
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

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

def dfs(v,p):
  ans[v] = p + P[v]
  visited[v] = 1
  
  for nv in G[v]:
    if visited[nv] == 0:
      dfs(nv,ans[v])
        
dfs(0,0)
print(*ans)

### FIXED CODE ###

from collections import deque

n,q = map(int,input().split())
cnt = [0]*(n+1)
g=[[] for _ in range(n+1)]

for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  
for _ in range(q): 
  v,val=map(int,input().split())
  cnt[v]+=val    
  
q = deque()
q.append(1)
checked = [0]*(n+1) 
while q:
  v = q.pop()
  checked[v] = 1
  for vc in g[v]:
    if checked[vc] == 1:
      continue
    else:
      cnt[vc] += cnt[v]
      q.append(vc)
    
print(*cnt[1:])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

modulus = 10 ** 9 + 7
s = input()
n = len(s)


def dp(i, j):
    """
    dynamic programming for abc 104
    :param i: index of the given string
    :param j: count of letters of composed string (like 'ABC')
    :return: the number of cases
    """
    if i == n:
        if j == 3:
            return 1
        else:
            return 0

    else:
        wildcard = s[i] == '?'
        if j == 3:
            m = 3 if wildcard else 1
            return m * dp(i + 1, 3) % modulus

        else:
            m1 = 3 if wildcard else 1
            m2 = 1 if wildcard or s[i] == 'ABC'[j] else 0
    
            return (m1 * dp(i + 1, j) + m2 * dp(i + 1, j + 1)) % modulus


print(dp(0, 0))


### FIXED CODE ###

if __name__ == "__main__":
    modulus = 10 ** 9 + 7
    s = input()
    n = len(s)
    dp = [[0] * 4 for _ in range(n + 1)]

    for i in range(n + 1)[::-1]:
        for j in range(4)[::-1]:
            if i == n:
                if j == 3:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                is_wildcard = s[i] == '?'
                if j == 3:
                    m = 3 if is_wildcard else 1
                    dp[i][j] = m * dp[i + 1][3] % modulus

                else:
                    m1 = 3 if is_wildcard else 1
                    m2 = 1 if is_wildcard or s[i] == 'ABC'[j] else 0

                    dp[i][j] = (m1 * dp[i + 1][j] + m2 * dp[i + 1][j + 1]) % modulus
            # print(i, j, dp[i][j])
    print(dp[0][0])
### BUGGY CODE ###

N,M=map(int,input().split())
numbers=[]
for _ in range(M):
    a,b=input().split()
    numbers.append([int(b),int(a)])
new_numbers=sorted(numbers)
answers=[]


while new_numbers:
    large = new_numbers[0][0]
    if  not new_numbers[0] in answers:
        answers.append(new_numbers[0])
    new_numbers=[a for a in new_numbers if a[1]>=large]
print(len(answers))


### FIXED CODE ###

N,M=map(int,input().split())
numbers=[]
for _ in range(M):
    a,b=input().split()
    numbers.append([int(b),int(a)])
new_numbers=sorted(numbers)
answers=[]
while new_numbers:
    large = new_numbers[0][0]
    if  not new_numbers[0] in answers:
        answers.append(new_numbers[0])
    new_numbers=[a for a in new_numbers if a[1]>=large]
print(len(answers))
### BUGGY CODE ###

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()


### FIXED CODE ###

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()
### BUGGY CODE ###

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

ans = 0

for i in range(N-1):
  ans += A[i]*sum(A[i+1:N])
  
mod = 10**9 + 7
print(ans%mod)

### FIXED CODE ###

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

ans = 0
res = [0] * N
res[0] = A[0]
for i in range(len(A)-1):
    res[i+1] = res[i] + A[i+1]

sum_A = sum(A)

for i in range(N-1):
  ans += A[i]*(sum_A-res[i])
  
mod = 10**9 + 7
print(ans%mod)
### BUGGY CODE ###

N, M = map(int, input().split())
a = M//N
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

ma = gcd(a, M)
for i in range(a, 0, -1):
    ma = max(ma, gcd(i, M))
    
print(ma)


### FIXED CODE ###

N, M = map(int, input().split(" "))
flg = 0
for i in range(N, M+1):
    if M % i == 0:
        print (M//i)
        flg = 1
        break
    if i**2 > M:
        break

if flg == 0:
    for i in range(M//N, 0, -1):
        if M % i == 0:
            print (i)
            break
### BUGGY CODE ###

N, K = map(int, input().split())
listp = list(map(int, input().split()))
#print(listp)
listans = []
for n in range(N):
    a = (listp[n]+1)/2
    listans.append(a)
#print(listans)   
listans1 = []
for n in range(N-K+1):
    b = sum(listans[n:n+K])
    listans1.append(b)
#print(listans1) 
print(max(listans1)) 

### FIXED CODE ###

N, K = map(int, input().split())
listp = tuple(map(int, input().split()))
bc =sum(listp[0:K])
b = sum(listp[0:K])
for n in range(1,N-K+1):
    b = b - listp[n-1]+listp[n+K-1]
    
    if b > bc:
        bc = b
    else:
        pass    
    #print(b)    
print((bc+K)/2)
### BUGGY CODE ###

n = int(input())
a_l = list(map(int, input().split()))
ans = ''

for i in range(1,n+1):
    ans += str(a_l.index(i)+1)+' '

print(ans)


### FIXED CODE ###

n = int(input())
ans = [0]*n

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

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

st = ''
for a in ans:
    st += str(a)+' '

print(st)
### BUGGY CODE ###

from functools import reduce

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

for i in range(n):
    tmp = a[:i] + a[i + 1:]
    print(reduce(lambda i, j: int(i) ^ int(j), tmp))


### FIXED CODE ###

from functools import reduce

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

all = reduce(lambda i, j: int(i) ^ int(j), a)

for i in range(n):
    print(all ^ a[i])
### BUGGY CODE ###

from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)
### BUGGY CODE ###

i = input()
N = int(i)
A = []
for x in range(N):
    j = input()
    A.append(int(j))

for x in range(N):
    #print(x)
    t = []
    for y in A:
        t.append(y)
    # print(t)
    t.remove(A[x])
    print(max(t))


### FIXED CODE ###

import numpy as np

i = input()
N = int(i)
A = np.array([0]*N)
i = input()
a = int(i)
A[0] = a
i = input()
b = int(i)
A[1] = b
snd = min(a, b)
fst = max(a, b)
for x in range(N - 2):
    j = input()
    y = int(j)
    A[x+2] = y
    if y <= fst:
        snd = max(snd, y)
    fst = max(fst, y)

for x in range(N):
    if A[x] < fst:
        print(fst)
    else:
        print(snd)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = []
cnt = 0

for i in range(n-1):
    A.append(a[i])
    if sum(A) > 0 and sum(A) + a[i+1] > 0:
        cnt += abs(sum(A) + a[i+1])+1
        a[i+1] -= abs(sum(A) + a[i+1])+1


    elif sum(A) < 0 and sum(A) + a[i+1] < 0:
        cnt += abs(sum(A) - a[i+1])-1
        a[i+1] += abs(sum(A) - a[i+1])-1


if sum(a) == 0:
    cnt += 1

print(cnt)

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

import bisect
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())

listofmax = [A[0]]

for j in range(1, N):
    if listofmax[0] >= A[j]:
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]

print(len(listofmax))


### FIXED CODE ###

import bisect
from collections import deque
de1 = deque()
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
de1.appendleft(A[0])
for j in range(1, N):
    if de1[0] >= A[j]:
        de1.appendleft(A[j])
    else:
        de1[bisect.bisect_left(de1, A[j]) - 1] = A[j]
print(len(de1))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l = []
r = []
ans = []
for _ in range(q):
    lq, rq = map(int, input().split())
    ans.append(s[lq-1:rq].count('AC'))
     
for i in range(q):
    print(ans[i])

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

cnt = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        res = N - (r*R+g*G)
        if res == 0 or res > 0 and res % B == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

def main():
    R, G, B, N = map(int, input().split())

    cnt = 0
    for r in range(N//R+1):
        for g in range(N//G+1):
            res = N - (r*R+g*G)
            if res >= 0 and res % B == 0:
                cnt += 1
    print(cnt)

main()
### BUGGY CODE ###

N=int(input())
A = list(map(int,input().split()))
for i in range(N):
  i += 1
  print(A.count(i))

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
import collections
c = collections.Counter(A)
for i in range(N):
  i+=1
  print(c[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[[-1,0,0] for j in range(W)] for i in range(H)]

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u[0]][u[1]][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u[0]][u[1]][0] = findset(p(u))
        return T[u[0]][u[1]][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)[0]][findset(u)[1]][1] += T[findset(v)[0]][findset(v)[1]][1]
    T[findset(u)[0]][findset(u)[1]][2] += T[findset(v)[0]][findset(v)[1]][2]
    T[findset(v)[0]][findset(v)[1]][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite([i1,j1],[i2,j2])
#        print('unite',i1,j1,i2,j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite([i1,j1],[i2,j2])
#        print('unite',i1,j1,i2,j2)
#    else:
#        print('not unite',i1,j1,i2,j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i][j][1] += 1
        else:
            T[i][j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i][j][0] == -1:
            ans += T[i][j][1]*T[i][j][2]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[-1,0,0] for j in range(H*W)] 

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u][0] = findset(p(u))
        return T[u][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)][1] += T[findset(v)][1]
    T[findset(u)][2] += T[findset(v)][2]
    T[findset(v)][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite(i1 * W + j1, i2 * W + j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite(i1 * W + j1, i2 * W + j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i * W + j][1] += 1
        else:
            T[i * W + j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i * W + j][0] == -1:
            ans += T[i * W + j][1] * T[i * W + j][2]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
c = [0]*N
p = 0

for i in range(N):
  c[i] = A.count(i+1)

for i in range(N):
  if c[i] > 1:
    p += (c[i])*(c[i]-1)//2

for i in range(N):
  if c[A[i]-1] > 1:
    print(p-(c[A[i]-1]-1))
  else:
    print(0)


### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
c = [0]*N
p = 0


c = collections.Counter(A)

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

for i in range(N):
  print(p-c[A[i]]+1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
f = sorted(list(map(int, input().split())), reverse=True)


def test(x):
    cost = 0
    for i in range(n):
        cost += max(0, a[i] - x // f[i])
    return cost <= k


left = -1
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = np.array(sorted(list(map(int, input().split()))))
f = np.array(sorted(list(map(int, input().split())), reverse=True))


def test(x):
    cost = np.maximum(0, a-x//f).sum()
    return cost <= k


left = -1
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
arr = []
for i in range(m-1):
    arr.append(abs(x[i] - x[i + 1]))
for _ in range(n - 1):
    if len(arr) <= 0:
        break
    arr.remove(max(arr))

print(sum(arr))

### FIXED CODE ###

n, m = map(int, input().split())
x = sorted(map(int, input().split()))
arr = [x[i + 1] - x[i] for i in range(m - 1)]
arr.sort(reverse=True)
print(sum(arr[n-1:]))
### BUGGY CODE ###

def main():
    N,M = [int(x) for x in input().split()]
    Scc_cnt = 0
    while N >= 0 and M >= 2:
        if N >= 1 and M >= 2:
            N -= 1
            M -= 2
            Scc_cnt += 1
        if N == 0 and M >= 4:
            M -= 4
            Scc_cnt += 1
        if N == 0 and M <= 3:
            break
    print(Scc_cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,M = [int(x) for x in input().split()]
    Scc_cnt = 0
    if N >= 0 and M >= 2:
        if M >= N*2:
            Scc_cnt += N + (M-N*2)//4
        else:
            Scc_cnt += M//2
    print(Scc_cnt)

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

# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
#    print(p)
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_right(c, a[i]-1)
        c[p-1]=a[i]
#        c.sort()

print(len(c))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [-999]*n

for i in range(0,n):
#    if c[0] >= a[i]:
#        c.insert(0,a[i])
#    else:
    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]
#        print(c)
#        print(p)

print(len(c) - bisect.bisect_left(c, -1))
### BUGGY CODE ###

N, M = map(int, input().split())
tmp = []
PY = [[] for _ in range(N + 1)]
# PY_sorted = [[] for _ in range(N + 1)]

for i in range(M):
    p, y = map(int, input().split())
    tmp.append([p, y])
    PY[p].append(y)
    PY[p].sort()

# for i in range(1, N + 1):
#     PY_sorted[i] = sorted(PY[i])

for prefecture, year in tmp:
    text = ""
    text += "%06d" % prefecture
    text += "%06d" % (PY[prefecture].index(year) + 1)
    print(text)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
PY = [[] for _ in range(N + 1)]

for i in range(M):
    p, y = map(int, input().split())
    PY[p].append((y, i))

ans = []

for pre_id, info in enumerate(PY):
    info.sort()
    for i in range(len(info)):
        ans.append((info[i][1], "%06d" % pre_id, "%06d" % (i + 1)))

ans.sort()
for i, x, y in ans:
    print(str(x) + str(y))
### BUGGY CODE ###

"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)



### FIXED CODE ###

"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)