Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]


def segfunc(x, y):
    return max(x,y)

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = 0

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

lst=init([0]*300010)    #aはリスト


for i in a:
    l=max(0,i-k)
    r=min(300000,i+k)
    pin=query(l,r+1)+1
    update(i,pin)


print(max(seg))


### FIXED CODE ###

import sys
input=sys.stdin.readline

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        # built
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
 
    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])
 
    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res
 
def func(x, y):
    return max(x,y)

seg=SegTree([0]*300001,0,func)

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]

for i in a:
    l=max(0,i-k)
    r=min(300000,i+k)

    pin=seg.query(l,r+1)+1
    seg.update(i,pin)


print(seg.query(0,300001))
a, b = input().split()
a= int(a)
b = int(b)
if a in range(1,9);
 if b in range(1,9);
  print(a*b)
else:
  print("-1")


### FIXED CODE ###

import sys
a, b = map(int, input().split())
k = range(1,10)
if a in k:
 if b in k:
  print(a*b)
  sys.exit()
 else:
  pass
print("-1")
def main():
    n =int( input())
    sn=[]
    
    for i in range(n):
        inWord = str(input())
        addFlag = True
        for s in sn:
            if s["word"] == inWord and len(sn) !=0:
                s["count"]+=1
                addFlag = False
                break
        if addFlag ==True:
            sn.append( {"word":inWord,"count":1})
    
    a= sorted(sn, reverse=True,key=lambda x:x['count'])

    most = a[0]["count"]
    mostWords=[]
    for elm in a:
        if elm["count"] == most:
            mostWords.append(elm["word"])
    mostWords.sort()
    for elm in mostWords:
        print(elm)
    return
main()



### FIXED CODE ###

A, B, C = map(int, input().split())

if A == B or B == C or C == A:
    if A == B and B == C:
        print("No")
    else:
        print("Yes")

else:
    print("No")
A=list(map(int,input().split()))
t=True
C=2019
if t:
    for i in range(A[1]):
        for t in range(A[1]+1):
            if t>i and i>=A[0]:
                if i-t>2019:
                  	C=0
                    t=False
                    break
                else:
                    if t*i%2019<C:
                        C=t*i%2019
print(C)

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
N=int(input())
if N < 105:
  print(0)
elif N < 135:
  print(1)
elif N < 165
  print(2)
elif N < 189:
  print(3)
elif N < 195:
  print(4)
else:
  ptint(5)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N + 1,2):
    cnt=0
    for j in range(1,i+1):
        if not i%j:
          cnt+=1
    if cnt==8:
      ans += 1
print(ans)
# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a_r2  Time Limit Exceeded
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m_array = list(map(int, input().split()))
m_max = max(m_array)
can_c_array = [[None for _ in range(m_max+1)] for _ in range(n+1)]

def can_comp(i, m): #i番目以降の数列をつかってmを作れるか？
    #print(i,m)
    global n
    global a
    global can_c_array
    if m == 0:
        can_c_array[i][m] = True
        return True
    if i >= n:
        can_c_array[i][m] = False
        return False
    if can_c_array[i][m] != None:
        return can_c_array[i][m]
    elif can_comp(i+1,m):
        can_c_array[i][m] = True
    elif m-a[i] >= 0:
        if can_comp(i+1,m-a[i]):
            can_c_array[i][m] = True
    else:
        can_c_array[i][m] = False
    return can_c_array[i][m]

for m in m_array:
    if can_comp(0, m):
        print('yes')
    else:
        print('no')



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a_r1  
@author: maezawa
"""
import itertools as itr

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

sum_array = []
for r in range(1,n+1):
    for comb in itr.combinations(a, r):
        sum_array.append(sum(comb))
sum_array.sort()

for i in m:
    left = 0
    right = len(sum_array)
    yesorno = 'no'
    while(left < right):
        #print(left, right)
        mid = (left+right)//2
        if sum_array[mid] == i:
            yesorno = 'yes'
            break
        elif sum_array[mid] > i:
            right = mid
        else:
            left = mid+1
            
    print(yesorno)
N = int(input())
x = list(map(int, input().split()))
y = [0] * N

odd = sum([n for i, n in enumerate(shifted_x) if i % 2 == 1])
even = sum([n for i, n in enumerate(shifted_x) if i % 2 == 0])
y[0] = even - odd

for i in range(N-1):
  y[i+1] = 2 * x[1] - y[i]


str_y = map(str, y)
output = " ".join(str_y)
print(output)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
y = [0] * N

odd = sum([n for i, n in enumerate(x) if i % 2 == 1])
even = sum([n for i, n in enumerate(x) if i % 2 == 0])
y[0] = even - odd

for i in range(N-1):
  y[i+1] = 2 * x[i] - y[i]


str_y = map(str, y)
output = " ".join(str_y)
print(output)
a = int(input())
b = int(input())
c = int(input())
d = int(a+b+c)
if d<22:
    print("win")
else:
    print("bust")


### FIXED CODE ###

x = input().split()
a, b, c =x
d = int(a)+int(b)+int(c)
if d<22:
    print("win")
else:
    print("bust")
N, M = map(int, input().split())
S = input()
T = input()

import sys

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

g = gcd(N, M)
sn = N/g
sm = M/g

ok = True
for k in range(0, g):
    a = k * sn
    b = k * sm
    if S[a] != T[b]:
        ok = False
        break

if ok:
    print(N*M/g)
else:
    print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()

import sys

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


g = gcd(N, M)
sn = N//g
sm = M//g

ok = True
for k in range(0, g):
    a = k * sn
    b = k * sm
    if S[a] != T[b]:
        ok = False
        break

if ok:
    print(N*M//g)
else:
    print(-1)
N, T = map(int, input().split())

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


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if j < 0 or dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[N][-1] + last)

#print(dp)



### FIXED CODE ###


N, T = map(int, input().split())

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


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


ans = 0
for i, d in enumerate(dp):
    # dp[i][:]にはi-1番目までで最大の満足度が入れられてるから、ABのi以降（使ってないから）で一番大きいのを足す
    mb = 0
    for a,b in AB[i:]:
        mb = max(mb, b)
    ans = max(ans, d[-1] + mb)

print(ans)
N,M,V,P = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A = np.array(sorted(A,reverse=True))
ans = P
x = A[P-1]
y = N-1
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break

if y==N-1:
  print(N)
z = sum(A[P-1:y])
for i in range(y,N):
  a = A[i]
  d = a+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    e = z+c
    f = d*(i-P+1)
    if f>=e:
      ans+=1
      
  z+=a
print(ans)


### FIXED CODE ###

N,A,B = map(int,input().split())
x = B-A
if x%2==0:
  print(x//2)
  
else:
  x = min(max(A-1,B-1),max(N-A,N-B))
  y = N-B+1+(B-A-1)//2
  z = A+(B-A-1)//2
  print(min(x,y,z))
N, Q = map(int, input().split())

w = [[] for _ in range(N+1)]
for _ in range(N-1):
    A, B = map(int, input().split())
    w[A].append(B)
    w[B].append(A)

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

flag = [False]*(N+1)
cnt_sum = [0]*(N+1)

def f(i, n):
    if flag[i]:
        return
    flag[i] = True
    cnt_sum[i] = n+cnt[i]
    for t in w[i]:
        f(t, cnt_sum[i])

f(1, 0)

print(" ".join([str(c) for c in cnt_sum[1:]]))

### FIXED CODE ###

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

w = [[] for _ in range(N+1)]
for _ in range(N-1):
    A, B = map(int, input().split())
    w[A].append(B)
    w[B].append(A)

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

flag = [False]*(N+1)

q = [1]
while q:
    n = q.pop()
    flag[n] = True
    for i in w[n]:
        if flag[i]:
            continue
        flag[i] = True
        cnt[i] += cnt[n]
        q.append(i)

print(" ".join([str(c) for c in cnt[1:]]))
import numpy as np

n,m = map(int,input().split())
h=list(map(int,input().split()))

mat=np.zeros((n,n),np.uint8)
for i in range(m):
    x,y= map(int,input().split())
    mat[x-1,y-1]+=1
    mat[y-1,x-1]+=1

count=0
for i in range(n):
    for j in range(n):
        if mat[i,j]!=0 and h[i]<=h[j] and i!=j:
            break
        elif j==n-1:
            count+=1

print(count)

### FIXED CODE ###

import numpy as np

n,m = map(int,input().split())
h=list(map(int,input().split()))

l=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    if h[x-1]<=h[y-1]:
        l[x-1]=1
    if h[x-1]>=h[y-1]:
        l[y-1]=1

count=0
for i in range(n):
    if l[i]==0:
        count+=1

print(count)
A = []

for i in range(3):
    a = list(map(int, input().split()))
    A.append(a)

N = int(input())

check = [0]*3*3
for n in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if A[i][j] == b:
                 check[i][j] = 1

ans = 'No'

for i in range(3):
    if check[i][0]+check[i][1]+check[i][2]==3:
        ans = 'Yes'

for i in range(3):
    if check[0][i]+check[1][i]+check[2][i]==3:
        ans = 'Yes'

if check[0][0]+check[1][1]+check[2][2] == 3:
    ans = 'Yes'

if check[0][2]+check[1][1]+check[2][0] == 3:
    ans = 'Yes'

print(ans)


### FIXED CODE ###

A = []
B = []
for i in range(3):
    a = list(map(int, input().split()))
    A.append(a)

N = int(input())

test = [[0]*3 for _ in range(3)]

for i in range(N):
    B.append(int(input()))

for b in B:
    for m in range(3):
        for n in range(3):
            if b == A[m][n]:
                test[m][n] =1

ans = 'No'

for i in range(3):
    if sum(test[i]) == 3:
        ans = 'Yes'
    if test[0][i]+test[1][i]+test[2][i] == 3:
        ans = 'Yes'

if test[0][0]+test[1][1]+test[2][2] == 3:
    ans = 'Yes'

if test[2][0]+test[1][1]+test[0][2] == 3:
    ans = 'Yes'

print(ans)
X = map(int, input().split())
for i in range(len(X)):
  if X[i] == 0:
    print(i+1)
    break

### FIXED CODE ###

X = list(map(int, input().split()))
for i in range(len(X)):
  if X[i] == 0:
    print(i+1)
    break
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=1
j=0
if b[0]==1:
  a[1]=0
  j=1
else:
  a[1]=1
for i in range(2,n+1):
  if i==b[j]:
    if j<m-1:
      j+=1
  else:
    a[i]=a[i-1]+a[i-2]
print(a[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])
# -*- coding: utf-8 -*-
"""
Created on Sat Mar  9 21:40:34 2019

@author: iwata
"""

N,M = map(int, input().split())
numlist =[]
money = 0
count = 0
count1 = 0
count2 = 0

for i in range(N):
    AB = list(map(int, input().split()))
    numlist.append(AB)

numlist.sort()

while count <= M:
    while numlist[count1][1] >= count2:
        money = money + numlist[count1][0]
        count = count + 1
        count2 = count2 + 1
        if count == M:
            break
    count1 = count1 + 1
    count2 = 0
    
print(money)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Mar  9 21:07:57 2019

@author: iwata
"""

H,W = map(int, input().split())
h,w = map(int, input().split())

num = H*W - (h*W+(H-h)*w)
print(num)
x = input()
 
while x != "0":    
    a=x.sort()
    for i in range(2):
        print(a[0],a[1])
    x = input()

### FIXED CODE ###

import sys
   
ff = sys.stdin
   
while True :
    a, b = map(int, ff.readline().split())
    if (a == 0) & (b == 0) :
        break
   
    if a < b : print(a, b)
    else : print(b, a)
N,M=map(int,input().split())
d={}
for i in range(M):
  s,t=map(int,input().split())
  if s in d:
    if d[s]!=t:
      print('-1')
      exit()
  if s==1:
    if t==0:
      if N==1:
        print('0')
        exit()     
      else:
        print('-1')
        exit()  
  d[s]=t
if N==1:
    if s==1:
      if t==0:
        print('0')
        exit()
if 1 not in d:
  d[1]=1
for i in range(2,N):
  if i not in d:
    d[i]=0
L=[]
for i in d.values():
  L.append(str(i))
print(''.join(L))

### FIXED CODE ###

N,M=map(int,input().split())
SC=[list(map(int,input().split())) for i in range(M)]

def check(x):
  x=str(x)#文字に変換
  if len(x)!=N:
    return False
  for s,c in SC:
    if x[s-1]!=str(c):
      return False
  return True

for i in range(1000):
  if check(i):
    print(i)
    exit()
print(-1)
a,b = map(int,input().split())

s = a + b
if s % 2 = 1:
  s =s+ 1
  
print(s // 2)

### FIXED CODE ###

l = list(map(int,input().split()))
 
s = l[0] + l[1]
if s % 2 == 1:
    s = s+ 1
else:
    None
print(s // 2)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*n
    self.rank = [0]*n
    
  def find_root(self, e):
    if self.root[e] < 0:
      return e
    else:
      r = self.find_root(self.root[e])
      self.root[e] = r
      return r
    
  def combine(self, e1, e2):
    root1 = self.find_root(e1)
    root2 = self.find_root(e2)
    if root1 == root2:
      pass
    elif self.rank[root1] < self.rank[root2]:
      self.root[root1] += self.root[root2]
      self.root[root2] = root1
      self.rank[root1] = self.rank[root2] + 1
    elif self.rank[root2] < self.rank[root1]:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] = self.rank[root1] + 1
    else:
      self.root[root2] += self.root[root1]
      self.root[root1] = root2
      self.rank[root2] += 1
      
  def in_the_same_group(self, e1, e2):
      r1 = self.find_root(e1)
      r2 = self.find_root(e2)
      if r1 == r2:
        return True
      return False
  

NMK = input().split()
N = int(NMK[0])
M = int(NMK[1])
K = int(NMK[2])
uf = UnionFind(N)
from collections import defaultdict
friend_list = [0]*N
for _ in range(M):
  AB = input().split()
  A = int(AB[0])-1
  B = int(AB[1])-1
  uf.combine(A,B)
  friend_list[A] += 1
  friend_list[B] += 1

block_list = [0]*N
for _ in range(K):
  CD = input().split()
  C = int(CD[0])-1
  D = int(CD[1])-1
  if uf.in_the_same_group(C, D):
    block_list[C] += 1
    block_list[D] += 1

block_list*n
cnt = defaultdict(int)
ans = []
for i in range(N):
  cnt[i] = -uf.root[uf.find_root(i)] - 1 - friend_list[i] - block_list[i]
  ans.append(str(cnt[i]))

print(" ".join(ans))

### FIXED CODE ###

class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])
S, T = list(map(str,input().split()))
A, B = list(map(int,input().split()))
U = str(input())

def main():
    if S is U:
        A -= 1
    elif T is U:
        B -= 1
    else:
        pass

    print(A,B)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

S,T = list(map(str,input().split()))
A,B = list(map(int,input().split()))
U = str(input())

if S == U:
    A -=1
elif T == U:
    B -=1
else:
    pass

print(A,B)
n = int(input())
import fractions
print(fractions.floor(n**0.5)**2)

### FIXED CODE ###

n = int(input())
a = 1
while a**2 <= n:
    a += 1
print((a-1)**2)
import heapq
import math
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
if b>=sum(c):
  print(0)
else:
  c.sort()
  d.sort(reverse=True)
  e=[c[i]*d[i] for i in range(a)]
  f=[]
  for i in range(a):
    heapq.heappush(f,-e[i])
  k=0
  while k<b or f[0]==0:
    x=-heapq.heappop(f)
    y=e.index(x)
    z=min(b-k,(x+f[0])//d[y]+1)
    k+=z
    c[y]=c[y]-z
    e[y]=c[y]*d[y]
    heapq.heappush(f,-e[y])
    print(f)
  print(-f[0])

### FIXED CODE ###

import math
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
c.sort()
d.sort(reverse=True)
e=[0 for i in range(a)]
for i in range(a):
  e[i]=c[i]*d[i]
def s(e,x):
  k=0
  for i in range(a):
    if e[i]<x:
      continue
    else:
      k+=math.ceil((e[i]-x)/d[i])
  if k>b:
    return False
  else:
    return True
    
left=0
right=max(e)
while left!=right:
  mid=(left+right)//2
  if s(e,mid):
    right=mid
  else:
    left=mid+1
print(left)
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(m + 2) for a in range(n + 2)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = (c[i - 1][j - 1]) + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))

n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    # s1 = strs[i*2].rstrip()
    # s2 = strs[i*2+1].rstrip()
    ret.append(lcs(strs[i*2].rstrip(), strs[i*2+1].rstrip()))
print(*ret, sep="\n")

### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
N,X = (int(i) for i in input().split()) 
L = [int(i) for i in input().split()] 
D=0
i=0
while(D<=X and i<=N+1):
  D=D+L[i]
  i=i+1
print(i)

### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
count = 1
line = 0
for i in range(N):
    line += L[i]
    if line <= X:
        count += 1
print(count)