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

n, m = map(int, input().split())
query = []
result =  [[] for i in range(n)]
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)
    result[qList[0]-1].append(qList[1])
 
for i in result:
    i.sort()
 
for city in query:
    rank = result[city[0]-1].index(city[1])+1
    resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

k = int(input())
ans = 0

for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      gcd = 0
      for m in range(1,max(i,j,l)+1):
      	if i % m == 0 and j % m == 0 and l % m == 0:
        	gcd = max(gcd,m)
      ans += gcd
      #print(i,j,l,gcd)

print(ans)

### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0

for i in range(1,k+1):
  for j in range(1,k+1):
    ij_gcd = gcd(i,j)
    for l in range(1,k+1):
      ans += gcd(ij_gcd,l)

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

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
for i in range(m):
    b, c = map(int, input().split())
    count = 0
    while count < b:
        x = heapq.heappop(a)
        if x < c:
            heapq.heappush(a, c)
            count += 1
        elif x >= c:
            heapq.heappush(a, x)
            break
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(m):
    b, c = map(int, input().split())
    l.append((b, c))
for i in a:
    l.append((1, i))
l.sort(key=lambda x: x[1], reverse=True)
#print(l)
count = n
ans = 0
for item in l:
    b, c = item
    ans += c*min(b, count)
    count -= b
    if count <= 0:
        break
print(ans)
### BUGGY CODE ###

N=int(input())
word=[]
for i in range(N):
  word.append(input())
  
alphalist=[]
alpha=[[] for i in range(N)]
for i in range(N):
  word0=word[i]
  for v in range(10):
    alpha[i].append(word0[v])
  alpha[i].sort()
  alphalist.append(alpha[i])


number=0
for i in range(N):
  freq=alphalist.count(alphalist[i])
  if freq!=1:
    number0=(freq*(freq-1))/2
    number0=number0/freq
    number+=number0
  
print(int(number))

### FIXED CODE ###

n = int(input())
s = [input()for _ in range(n)]

for i in range(n):
    s[i] = ''.join(sorted(s[i]))

s.sort()

ans = 0
count = 0

for i in range(1, n):
    if count == 0:
        if s[i] == s[i-1]:
            count = 2
    else:
        if s[i] == s[i-1]:
            count += 1
        else:
            ans += count * (count - 1) // 2
            count = 0

ans += count * (count - 1) // 2

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

H, W = map(int, input().split())
# initialize maze
maze = []

for r in range(H):
  maze.append(list(input()))
maxVisit = 0
for row in maze:
  for road in row:
    if (road == "."):
      maxVisit += 1
# do bfs for each point and record maximum steps...
def findMaxBFS(start):
  # initialize BFS
  visitedCount = 1
  visitedPoints = []
  for r in range(H):
    visitedPoints.append([])
    for c in range(W):
      if (r == start[0]) and (c == start[1]):
        visitedPoints[r].append("Y")
      else:
        visitedPoints[r].append("N")
  points = [start]
  directions = [[0,1], [0,-1], [1,0], [-1,0]]
  steps = 0
  # BFS starts
  while (visitedCount < maxVisit):
    steps += 1
    nextPoints = []
    for p in points:
      for d in directions:
        nextP = [p[0]+d[0], p[1]+d[1]]
        #check nextP is inside the maze
        if (0<=nextP[0] and nextP[0]<H) and (0<=nextP[1] and nextP[1]<W):
          road = maze[nextP[0]][nextP[1]]
          #check nextP is walkable = stone
          if (road == "."):
            # check if nextP is already visisted
            if (visitedPoints[nextP[0]][nextP[1]] == "N"):
              nextPoints.append(nextP)
              visitedCount += 1
              visitedPoints[nextP[0]][nextP[1]] = "Y" 
    points = nextPoints
  # BFS ended
  # return max step
  return steps

max_steps = []
for r in range(H):
  for c in range(W):
    max_steps.append(findMaxBFS([r,c]))
print(max(max_steps))
    

### FIXED CODE ###

H, W = map(int, input().split())
# initialize maze
maze = []

for r in range(H):
  maze.append(list(input()))
maxVisit = 0
for row in maze:
  for road in row:
    if (road == "."):
      maxVisit += 1
# do bfs for each point and record maximum steps...
def findMaxBFS(start):
  #check start point is valid
  if (maze[start[0]][start[1]] == "#"):
    return 0
  # initialize BFS
  visitedCount = 1
  visitedPoints = []
  for r in range(H):
    visitedPoints.append([])
    for c in range(W):
      if (r == start[0]) and (c == start[1]):
        visitedPoints[r].append("Y")
      else:
        visitedPoints[r].append("N")
  points = [start]
  directions = [[0,1], [0,-1], [1,0], [-1,0]]
  steps = 0
  # BFS starts
  while (visitedCount < maxVisit):
    steps += 1
    nextPoints = []
    for p in points:
      for d in directions:
        nextP = [p[0]+d[0], p[1]+d[1]]
        #check nextP is inside the maze
        if (0<=nextP[0] and nextP[0]<H) and (0<=nextP[1] and nextP[1]<W):
          road = maze[nextP[0]][nextP[1]]
          #check nextP is walkable = stone
          if (road == "."):
            # check if nextP is already visisted
            if (visitedPoints[nextP[0]][nextP[1]] == "N"):
              nextPoints.append(nextP)
              visitedCount += 1
              visitedPoints[nextP[0]][nextP[1]] = "Y" 
    points = nextPoints
  # BFS ended
  # return max step
  return steps

max_steps = []
for r in range(H):
  for c in range(W):
    max_steps.append(findMaxBFS([r,c]))
print(max(max_steps))
### BUGGY CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

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

def solve():
    N = inp()
    AA = inlt()
    
    mult = AA[0]
    gcd_cum = AA[0]
    pairwise = True

    for i in range(1, N):
        g = gcd(mult, AA[i])
        if g != 1:
            pairwise = False
        mult = mult * (AA[i] // g)
        gcd_cum = gcd(gcd_cum, AA[i])
    
    if pairwise:
        return "pairwise coprime"

    if gcd_cum == 1:
        return "setwise coprime"
    
    return "not coprime"

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))


### FIXED CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############


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

def solve():
    N = inp()
    AA = inlt()

    MAX = 10 ** 6 + 5
    freq = [0 for i in range(MAX)]
    cnt = [0 for i in range(MAX)]
    
    gcd_cum = AA[0]

    for i in range(N):
        freq[AA[i]] += 1
        gcd_cum = gcd(gcd_cum, AA[i])

    for i in range(2, MAX):
        for j in range(i, MAX, i):
            cnt[i] += freq[j]

    pairwise = True
    for i in range(2, MAX):
        if cnt[i] > 1:
            pairwise = False
            break
    
    if gcd_cum == 1 and pairwise:
        return "pairwise coprime"

    if gcd_cum == 1:
        return "setwise coprime"
    
    return "not coprime"
    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))
### BUGGY CODE ###

import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

X,Y,Z,K = IL()
a = IL()
b = IL()
c = IL()

ab = []
for i in itertools.product(a,b):
  ab.append(sum(i))
ab.sort(reverse=True)

ans = []
for i in itertools.product(ab[:3000],c):
  ans.append(sum(i))
ans.sort(reverse=True)

for i in range(K):
  print(ans[i])

### FIXED CODE ###

import itertools
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

X,Y,Z,K = IL()
a = IL()
b = IL()
c = IL()

ab = []
for i in itertools.product(a,b):
  ab.append(sum(i))
ab.sort(reverse=True)

ans = []
for i in itertools.product(ab[:3000],c):
  ans.append(sum(i))
ans.sort(reverse=True)

for i in range(K):
  print(ans[i])
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []

x = 0
if n % 2 != 0:
    b.insert(0,a[x])
    x += 1

for i in range(x,n):
    if(i % 2 == 0):
        b.append(a[i])
    else:
        b.insert(0,a[i])
if n % 2 != 0:
    b.reverse()
    
print(' '.join(b))



### FIXED CODE ###

from collections import deque
n = int(input())
a = input().split()
b = deque()


for i in range(0,n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if n % 2 != 0:
    b.reverse()

print(*b)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
lr=[[int(i) for i in input().split()] for _ in range(q)]
for i in range(q):
    t=s[lr[i][0]-1:lr[i][1]]
    print(t.count('AC'))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
qs = [tuple(map(int,input().split())) for i in range(Q)]

cums = [0,0]
for i in range(1,N):
    if S[i-1:i+1] == 'AC':
        cums.append(cums[-1] + 1)
    else:
        cums.append(cums[-1])

for l,r in qs:
    print(cums[r] - cums[l])
### BUGGY CODE ###

n,m = map(int,input().split())
l = [0]*m
r = [0]*m
ans = 0
for i in range(m):
    l[i],r[i] = map(int,input().split())

for i in range(n):

    for j in range(m):
        
        if  not l[j]<=i+1<=r[j]:
            break
        if j==m-1:
            ans += 1
            
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
l = [0]*m
r = [0]*m
ans = 0
for i in range(m):
    l[i],r[i] = map(int,input().split())

Min = max(l)
Max = min(r)
for i in range(n):
    if Min<=i+1<=Max:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    t = list(r)
    t.sort()
    s[i] = ''.join(t)
total = 0
while len(s):
    a = s.pop(-1)
    count = 0
    for i in reversed(range(0, len(s))):
        if s[i] == a:
            count += 1
            s.pop(i)
    total += int((count + 1) * count / 2)
print(total)

### FIXED CODE ###

import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    t = list(r)
    t.sort()
    s[i] = ''.join(t)
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 0
count = 0
for k, v in d.items():
    count += int((v + 1) * v / 2)
print(count)
### BUGGY CODE ###

def sol():
    n=int(input())
    a=tuple(int(i) for i in input().split())
    ans=chk=0
    for i in range(min(a[0],a[-1])*2,-1,-2):
        ans=[0]*n
        ans[0]=i
        f=1
        for j in range(1,n):
            t=(a[j-1]-ans[j-1]//2)*2
            if t>=0 and (t+ans[j-1])//2==a[j-1]:
                ans[j]=t
            else:
                f=0
                break
        if f and ans[-1]//2+ans[-2]//2==a[-2] and ans[-1]//2+ans[0]//2==a[-1]:
            print(*ans)

if __name__=="__main__":
    sol()

### FIXED CODE ###

# from https://atcoder.jp/contests/abc133/submissions/6272850
n=int(input())
a=[int(i) for i in input().split()]
c=[0]
s=sum(a)

for i in range(2*n):
    c.append(c[-1]+a[(i*2+1)%n])
ans=[0]*n
for i in range(n):
    ans[i*2%n]=s-2*(c[i+n//2]-c[i])
print(*ans)
### BUGGY CODE ###

import numpy as np
N, Q = list(map(int, input().split()))
S = input()
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

s = list(S)

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"

d = np.array(s)
tf = np.where(d=="AC", True, False)


for i in range(Q):
    print(np.sum(tf[l[i]-1:r[i]-1]))

### FIXED CODE ###

import sys  
from itertools import accumulate
input = sys.stdin.readline  

N, Q = list(map(int, input().split()))
S = input()

l = [None]*Q
r = [None]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

s = list(S)
ac = [0] * N

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"
            ac[i] += 1

ans = list(accumulate(ac))
ans = [0] + ans


for i in range(Q):
    print(ans[r[i]-1]- ans[l[i]-1])
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]
    
    
 
    
 
    bh_destroy = bomb_most_h[1]
    
 
    bw_destroy = bomb_most_w[1]
    
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]
 
    
    ans = 0
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if [bh,bw] in BOMB_HW:
                ans = max(bh_destroy+bw_destroy-1,ans)
            else:
                ans = max(bh_destroy+bw_destroy,ans)
    print(ans)
    
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    dd = defaultdict(bool)
    for m in range(M):
        dd[str(bomb_h[m]) + "-" + str(bomb_w[m])] = True
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]

    bh_destroy = bomb_most_h[1]
    bw_destroy = bomb_most_w[1]
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    ans = bh_destroy+bw_destroy
    

    for bh in candidate_h:
        for bw in candidate_w:   
            if not(dd[str(bh) + "-" + str(bw)]):
                print(ans)
                sys.exit()
    print(ans-1)
    


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

s = input()
q = int(input())

query = [input().split() for i in range(q)]

a = s
for i in range(len(query)):
    if query[i][0] == "1":
        a = a[::-1]
    else:
        if query[i][1] == "1":
            a = query[i][2] + a
        else:
            a = a + query[i][2]

print(a)

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())

query = [input().split() for i in range(q)]

a = deque([s])

flag = True

for i in range(q):
    if query[i][0] == "1":
        flag = not(flag)
    else:
        if (query[i][1] == "1" and flag) or (query[i][1] != "1" and not(flag)):
            a.appendleft(query[i][2])
        else:
            a.append(query[i][2])

b = "".join(a)
if not(flag):
    b = b[::-1]

print(b)
### BUGGY CODE ###

N=int(input())
numbers=[]
for n in range(0,N):
    number=int(input())
    if number in numbers:
        numbers.remove(number)
    else:
        numbers.append(number)
print(len(numbers))


### FIXED CODE ###

N=int(input())
numbers={}
for n in range(0,N):
    number=int(input())
    if number in numbers:
        numbers[number]+=1
    else:
        numbers[number]=1
ans=0
for n in list(numbers.values()):
    ans+=n%2
print(ans)
### BUGGY CODE ###

N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = [i for i in range(1,K+1)]
    if(used_color!=0):
        available_color.remove(used_color)
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        col = available_color.pop()
        next_stk.append((next,col))
        i = di[(next,n)]
        colors[i] = col
    stk = next_stk + stk
    seen.add(n)

print(K)
for col in colors:
    print(col)


### FIXED CODE ###

N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
#K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
 
cnt = 0
num = min(P)

for i in range(1,N+1):
  a = P.index(min(P[:i]))
  if i == a+1:
    cnt += 1
  if num == min(P[:i]):
    break
    
cnt_2 = P.count(num)
    
print(cnt+cnt_2-1)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
 
cnt = 0
M = 10**6

for i in range(N):
  if M >= P[i]:
    cnt += 1
    M = P[i]
    
print(cnt)
### BUGGY CODE ###

from fractions import gcd

from functools import reduce


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

n = int(input())
a_list = [int(x) for x in input().split()]

temp = reduce(lcm, a_list)

mod = 10 ** 9 + 7
ans = sum([temp // a for a in a_list]) % mod
print(ans)

### FIXED CODE ###

from fractions import gcd

from functools import reduce


n = int(input())
a_list = [int(x) for x in input().split()]

temp = reduce(lambda x, y: (x * y) // gcd(x, y), a_list)

mod = 10 ** 9 + 7
ans = sum([temp // a for a in a_list]) % mod
print(ans)
### BUGGY CODE ###

# coding: utf-8
# from collections import Counter
N = int(input())
A = list(map(int, input().split()))
# cnts = Counter(A)
cnts = {}
for i in range(N):
    if A[i] not in cnts.keys():
        cnts[A[i]] = 1
    else:
        cnts[A[i]] += 1
d = {}
for k in cnts.keys():
    if cnts[k] >= 2:
        d[k] = cnts[k] // 2
        
ans = 0
for i, k1 in enumerate(list(d.keys())[:-1]):
    for k2 in list(d.keys())[i:]:
        if k1 == k2:
            if d[k1] < 2:
                continue
            else:
                ans = max(ans, k1 * k2)
        else:
            ans = max(ans, k1 * k2)
print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
Aset = list(set(A))
Aset.sort(reverse=True)
a, b = 0, 0
L = []
cnt = 1
for i in range(1, N):
    if A[i] == A[i-1]:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
if A[-1] == A[-2]:
    L.append(cnt)
idx = 0
for i in range(len(L)):
    if L[i] >= 4:
        a, b = Aset[i], Aset[i]
        break
    elif L[i] >= 2:
        a = Aset[i]
        idx = i + 1
        break
if b <= 0:
    for i in range(idx, len(L)):
        if L[i] >= 2:
            b = Aset[i]
            break
print(a * b)
### BUGGY CODE ###

L = input()
mod = 10**9 + 7

x = len(L)
ans = 0
count = 0
for i in range(x):
    if L[i] == '1':
        ans += (3**(x-i-1)) * (2**count)
        ans %= mod
        count += 1
    else:
        continue

ans += 2**count % mod
ans %= mod
print(ans)

### FIXED CODE ###

L = input()
mod = 10**9 + 7

x = len(L)
L = int(L, 2)
DP1 = [0] * (x+1)  # sure under L
DP2 = [0] * (x+1)  # possible under L
DP1[1] = 1
DP2[1] = 2
for i in range(2, x+1):
    if (L >> (x-i)) & 1:
        DP1[i] = (DP1[i-1] * 3 + DP2[i-1]) % mod
        DP2[i] = DP2[i-1] * 2 % mod

    else:
        DP1[i] = DP1[i-1] * 3 % mod
        DP2[i] = DP2[i-1]
ans = (DP1[x] + DP2[x]) % mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase2=[]
for _ in range(N):
    Abase2=Abase2+Abase
A=set(itertools.combinations(Abase2,N))
A=list(A)
A2=set([tuple(sorted(x)) for x in A])
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)
### BUGGY CODE ###

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(len(S)):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == len(S)-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
    mode = 0

if K > int((len(D)-1)/2):
    K = int((len(D)-1)/2)
ans = 0
for i in range(int((len(D)-2*K-1)/2)+1):
    j = 2*i
    k = 2*K + 2*i + 1
    if sum(D[j:k]) > ans:
        ans = sum(D[j:k])

print(ans)


### FIXED CODE ###

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(N):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == N-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = sum(D[:(2*K+1)])
sumd = ans
for i in range(int((len(D)-2*K-1)/2)):
    sumd += D[2*K+2*i+1]+D[2*K+2*i+2]-D[2*i]-D[2*i+1]
    if sumd > ans:
        ans = sumd

print(ans)