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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    s=list(map(lambda x:ord(x)-a,list(input())))
    t=list(map(lambda x:ord(x)-a,list(input())))
    l=[[-1]*26 for _ in range(len(s))]
    S=s*2
    ap=[0]*26
    for i,a in enumerate(S):
        for j in range(ap[a],len(s)):
            l[j][a]=i-j
        ap[a]=i
    ans=0
    index=len(s)-1
    for a in t:
        n=l[index][a]
        if n==-1:
            print(-1)
            exit()
        ans+=n
        index+=n
        index%=len(s)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    a=ord('a')
    s=list(map(lambda x:ord(x)-a,input()))
    N=len(s)
    t=list(map(lambda x:ord(x)-a,input()))
    l=[[-1]*26 for _ in range(len(s))]
    for i in range(N-1,-N,-1):
        for j in range(26):
            if s[i]==j:
                l[i-1][j]=i%N
            else:
                l[i-1][j]=l[i][j]
    ans=0
    index=N-1
    for a in t:
        n=l[index][a]
        if n==-1:
            print(-1)
            exit()
        if n>index:
            ans+=n-index
        else:
            ans+=n+N-index
        index=n
    print(ans)

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

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=[]
  d.append((sx,sy))
  s=set()
  for ss in d:
    x,y=ss
    t=x*1000000+y
    if t in s:
      s.discard(t)
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append((x+i,y))
      if b[x+i][y]!=0:
        s.add(t+1000000*i)
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      if b[x-i][y]!=0:
        s.add(t-1000000*i)
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      if b[x][y+j]!=0:
        s.add(t+j)
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      if b[x][y-j]!=0:
        s.add(t-j)
      b[x][y-j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

n = int(input())
xs = []
ls = []
for _ in range(n):
    x, l = map(int, input().split())
    xs.append(x)
    ls.append(l)

ok = [True for _ in range(n)]

def f(i):
    rs = []
    for j in range(n):
        if i == j or not ok[j]:
            continue
        if xs[i] - ls[i] < xs[j] + ls[j] and xs[j] - ls[j] < xs[i] + ls[i]:
            rs.append(j)
    return rs

for i in range(n):
    if not ok[i]:
        continue

    rs = f(i)
    if len(rs) == 1:
        j = rs[0]
        ts = f(j)
        if len(ts) == 0:
            ok[i] = False
        else:
            ok[j] = False
    elif len(rs) > 1:
        ok[i] = False

c = 0
for v in ok:
    if v:
        c += 1
print(c)



### FIXED CODE ###

n = int(input())
robots = []
for _ in range(n):
    x, l = map(int, input().split())
    robots.append((x + l, x - l))
robots.sort()

cur = -float('inf')
ans = 0
for i in range(n):
    t, s = robots[i]
    if cur <= s:
        ans += 1
        cur = t

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

# Binary Index Tree (2-dimension)
class BIT2:
    # H*W, 0-based
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    #O(logH*logW)
    #[0.i)x[0.j)
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    # O(logH*logW)
    def add(self, i, j, x):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + x
                k|=(k+1)
            i|=(i+1)
    # [x0, x1) x [y0, y1)
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
ans=0
bit=BIT2(20,20)
for i in range(int(input())):
    a=input().split('.')
    if len(a)==1:
        cnt2,cnt5=9,9
        a=int(a[0])
        while a%2==0 and cnt2<18:
            cnt2+=1
            a//=2
        while a%5==0 and cnt5<18:
            cnt5+=1
            a//=5
    else:
        a=int(a[0])*10**9+int((a[1][::-1].zfill(9))[::-1])
        cnt2,cnt5=0,0
        for j in range(18):
            if a%2==0:
                a//=2
                cnt2+=1
            if a%5==0:
                a//=5
                cnt5+=1
    ans+=bit.range_sum(18-cnt2,19,18-cnt5,19)
    bit.add(cnt2,cnt5,1)
print(ans)

### FIXED CODE ###

# Binary Index Tree (2-dimension)
class BIT2:
    # H*W, 0-based
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    #O(logH*logW)
    #[0.i)x[0.j)
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    # O(logH*logW)
    def add(self, i, j, x):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + x
                k|=(k+1)
            i|=(i+1)
    # [x0, x1) x [y0, y1)
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
ans=0
bit=BIT2(20,20)
for i in range(int(input())):
    a=input().split('.')
    if len(a)==1:
        cnt2,cnt5=9,9
        a=int(a[0])
        while a%2==0 and cnt2<18:
            cnt2+=1
            a//=2
        while a%5==0 and cnt5<18:
            cnt5+=1
            a//=5
    else:
        a=int(a[0])*10**9+int((a[1][::-1].zfill(9))[::-1])
        cnt2,cnt5=0,0
        for j in range(18):
            if a%2==0:
                a//=2
                cnt2+=1
            if a%5==0:
                a//=5
                cnt5+=1
    ans+=bit.range_sum(18-cnt2,19,18-cnt5,19)
    bit.add(cnt2,cnt5,1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
I=lambda:int(input())
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))

H,W=MI()
A=[LI() for _ in [0]*H]
B=[LI() for _ in [0]*H]

M=80*(H+W)
dp=[[[False]*(2*M+1) for _ in [0]*W] for _ in [0]*H]
dp[0][0][M]=True

m=2*M+1
for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        for a in range(2*M+1):
            if dp[h][w][a]:
                #配る
                if h!=H-1:
                    if 0<=a+d<=2*M:
                        dp[h+1][w][a+d]=True
                        if (h+1)*w==(H-1)*(W-1):
                            m=min(abs(a+d-M),m)
                    if 0<=a-d<=2*M:
                        dp[h+1][w][a-d]=True
                        if (h+1)*w==(H-1)*(W-1):
                            m=min(abs(a-d-M),m)
                if w!=W-1:
                    if 0<=a+d<=2*M:
                        dp[h][w+1][a+d]=True
                        if h*(w+1)==(H-1)*(W-1):
                            m=min(abs(a+d-M),m)
                    if 0<=a-d<=2*M:
                        dp[h][w+1][a-d]=True
                        if h*(w+1)==(H-1)*(W-1):
                            m=min(abs(a-d-M),m)
                            
res=dp[H-1][W-1][:]
for a in range(2*M+1):
    if dp[H-1][W-1][a]:
        d=A[H-1][W-1]-B[H-1][W-1]
        if 0<=a+d<=2*M:
            res[a+d]=True
            m=min(abs(a+d-M),m)
        if 0<=a-d<=2*M:
            res[a-d]=True
            m=min(abs(a+d-M),m)
            
print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))

H,W=MI()
A=[LI() for _ in [0]*H]
B=[LI() for _ in [0]*H]

G=[[set() for i in range(W)] for j in range(H)]
G[0][0].add(0)

for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        for a in G[h][w]:
            if h!=H-1:
                G[h+1][w].add(abs(a+d))
                G[h+1][w].add(abs(a-d))
            if w!=W-1:
                G[h][w+1].add(abs(a+d))
                G[h][w+1].add(abs(a-d))

res=set()
d=A[H-1][W-1]-B[H-1][W-1]
for a in G[H-1][W-1]:
    res.add(abs(a+d))
    res.add(abs(a-d))

res=sorted(list(res))
print(min(res))
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

X = sorted(list(map(int,input().split())))
Y = sorted(list(map(int,input().split())))
ans = 0
for i in range(n - 1):
    for j in range(m - 1):
        S = (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
        num = (i + 1) * (n - (i + 1)) * (j + 1) * (m - (j + 1))
        S *= num
        S %= 10 ** 9 + 7
        ans += S
        ans %= 10 ** 9 + 7
print(ans)




### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

X = [0] + sorted(list(map(int,input().split())))
Y = [0] + sorted(list(map(int,input().split())))
sum1 = 0
sum2 = 0
MOD = 10 ** 9 + 7
for i in range(1, n + 1):
    sum1 += ((i - 1)*X[i] - (n - i)*X[i]) % MOD
for i in range(1, m + 1):
    sum2 += ((i - 1)*Y[i] - (m - i)*Y[i])%MOD
print(sum1 * sum2 % MOD)
### BUGGY CODE ###

def dfs():
  while len(q) > 0:
    p = q.pop()
    for e in g[p]:
      if d[e] < 0 or d[e] > d[p] + 1:
        d[e] = d[p] + 1
        q.append(e)
  
  
n, m = map(int, input().split())
g = [[] for i in range(3 * (n+1))]
for i in range(m):
  u, v = map(int, input().split())
  g[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

s, t = map(int, input().split())

d = [-3] * (3 * (n+1))
d[3*s] = 0

q = [3*s]
dfs()
print(d[3*t] // 3) 


### FIXED CODE ###

from collections import deque
def bfs():
  while len(q) > 0:
    p = q.popleft()
    for e in g[p]:
      if d[e] < 0:
        q.append(e)
        d[e] = d[p] + 1
        f[e] = p
      elif d[e] > d[p] + 1:
        d[e] = d[p] + 1
        f[e] = p       

  
  
n, m = map(int, input().split())
g = [[] for i in range(3 * (n+1))]
for i in range(m):
  u, v = map(int, input().split())
  g[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

s, t = map(int, input().split())

d = [-1] * (3 * (n+1))
f = [-1] * (3 * (n+1))
d[3*s] = 0
f[3*s] = 0
q = deque([3*s])
bfs()
c = 0
if f[3*t] == -1:
  print(-1)
  exit()

t = 3 * t
while f[t] > 0:
  c += 1
  t = f[t]
  
print(c // 3)
### BUGGY CODE ###

s = str(input())

ans = 0
for i in range(len(s)-1):
  if s[i:i+2] == 'BC':
    tmp = i
    cnt = 0
    while (0<tmp) and (s[tmp-1]=='A'):
      cnt += 1
      tmp -= 1
    else:
      ans += cnt
      s = s[:tmp] + 'BC' + 'A'*cnt + s[i+2:]
print(ans)

### FIXED CODE ###

s = str(input())

ans, cnt, i = 0, 0, 0
while i < len(s)-1:
  if s[i] == 'A':
    cnt += 1
    i += 1
  else:
    if s[i:i+2] == 'BC':
      ans += cnt
      i += 2
    else:
      cnt = 0
      i += 1
print(ans)
### BUGGY CODE ###

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

list.sort(A, reverse=True)
#print(A)
for m in range(M):
    tmp = A[0] / 2
    del A[0]
    insindex = N
    for i in range(len(A)):
        if A[i] < tmp:
            insindex = i
            break
    A.insert(insindex, tmp)
for i in range(len(A)):
    A[i] = int(A[i])
    
print(sum(A))

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
q = []
for x in A:
    heapq.heappush(q, -x)
for m in range(M):
    x = heapq.heappop(q)
    x /= 2
    heapq.heappush(q, x)
ans = 0
for x in q:
    ans += int(-x)
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
for i in range(N):
    if S[::-1][i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)


### FIXED CODE ###

S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
S=S[::-1]
for i in range(N):
    if S[i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)
### BUGGY CODE ###

from collections import Counter

def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x % d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)

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

divisors = getDivisor(As[0]) + getDivisor(As[1])
cnt = Counter(divisors)

for i, A in enumerate(As[2:], 2):
    for d, num in list(cnt.items()):
        if A%d == 0:
            cnt[d] += 1

    for d, num in list(cnt.items()):
        if num < i:
            del cnt[d]

print(max(cnt.keys()))


### FIXED CODE ###

from collections import Counter

def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x % d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)

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

divisors = getDivisor(As[0]) + getDivisor(As[1])
cnt = Counter(divisors)

for i, A in enumerate(As[2:], 2):
    for d, num in list(cnt.items()):
        if A%d == 0:
            cnt[d] += 1

    for d, num in list(cnt.items()):
        if num < i:
            del cnt[d]

print(max(cnt.keys()))
### BUGGY CODE ###

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

### FIXED CODE ###

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

from bisect import bisect

n, m = map(int, input().split())
*a, = map(int, input().split())
a.sort()
BC = []
num = 0
for _ in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
ans = 0
for b, c in BC:
    idx = bisect(a, c)
    p = min(idx, b)
    a = a[p:]
    ans += c * p
print(sum(a)+ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(i)) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.append((b, c))
a = sorted(a, key=lambda x: x[1])
ans = 0
t = 0
while t < n:
    b, c = a.pop()
    p = min(b, n-t)
    ans += p * c
    t += p
print(ans)
### BUGGY CODE ###

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

ans = 0
place = 0
for i in range(N-K+1):
  temp = sum(list(p[i:i+K]))
  if temp > ans:
    ans = temp
    place = i
    
print((ans+K)/2)

### FIXED CODE ###

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

rp = sum(list(p[0:K]))
rm = 0
ans = rp
for i in range(N-K):
  rp += p[i+K]
  rm += p[i]
  if rp - rm > ans:
    ans = rp - rm

print((ans+K)/2)
### BUGGY CODE ###

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
#                print(i,pxi,xi,popcount(xi),xi%popcount(xi))
                xi=xi%popcount(xi)
            print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if primes[i] * 2 - 1 in primes:
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])


### FIXED CODE ###

q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like_2017.append(2 * primes[i] - 1)

count = [0 for _ in range(10 ** 5)]
for like in like_2017:
    count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0]-1])
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

d=deque([[1,[float('inf')]]])
itta=[0]*(n+1)
# lislist=[0]*(n+1)
while d:
    now,lis=d.pop()
    # print(now,lis)
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
    else:
        lis[bisect.bisect_left(lis, a[now-1])]=a[now-1]
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            d.append([i,lis[:]])
# print(itta)
for i in range(n):
    print(itta[i+1])

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(1000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

itta=[0]*(n+1)
# lislist=[0]*(n+1)

def dfs(now,lis):
    stk=0
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
        stk="pop"
    else:
        tmp=bisect.bisect_left(lis, a[now-1])
        stk=[tmp,lis[tmp]]
        lis[tmp]=a[now-1]
    
    # print(now,lis)
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            dfs(i,lis)
    
    if stk=="pop":
        lis.pop()
    else:
        lis[stk[0]]=stk[1]

dfs(1,[float('inf')])

# print(itta)
for i in range(n):
    print(itta[i+1])
### BUGGY CODE ###

def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
N=input()
A=list(map(int,input().split(' ')))
ans = 0
l = 1
mod = 10**9+7
for i in A:
    g = gcd(l,i)
    l = l*i//g
print(sum([l//i%mod for i in A])%mod)

### FIXED CODE ###

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l_1 = 1
l_2 = 1
mod = 10**9+7
def lcm(x,y):
    return x*y//gcd(x,y)
for i in A[:N//2]:
    l_1 = lcm(l_1,i)
for j in A[N//2:]:
    l_2 = lcm(l_2,j)
l = lcm(l_1,l_2)
out1 = sum([l_1//i for i in A[:N//2]])
out2 = sum([l_2//i for i in A[N//2:]])
out1 *= l//l_1
out2 *= l//l_2
print((out1+out2)%mod)
### BUGGY CODE ###

N,K=map(int,input().split())
import copy
import sys
input=sys.stdin.readline
D=dict()
D[(0,0)]=1

for i in range(N):
    a,b=map(int,input().split())
    d=dict()
    for j in D:
        d[j]=1
        d[(j[0]|a,j[1]+b)]=1
    D=copy.deepcopy(d)
#print(D)
ans=0
for i in D:
    if i[1]>ans and i[0]<=K:
        ans=i[1]
print(ans)

### FIXED CODE ###

import copy
N,K=map(int,input().split())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    if a<=K:
        L.append([a,b])

#print(L)
k=[]
num=copy.deepcopy(K)
for i in range(30):
    if num//(2**(29-i))==1:
        k.append(1)
        num%=(2**(29-i))
    else:
        k.append(0)
        num%=(2**(29-i))
        
ans=0
for a,b in L:
    if K|a==K:
        ans+=b
NUM=0
for i in range(30):
    if k[i]==1:
        cnt=0
        NUM+=2**(29-i)
        for a,b in L:
            if K-2**(29-i)|a<NUM:
                cnt+=b
        if ans<cnt:
            ans=cnt
        #print(cnt,i,K-2**(29-i))
    
print(ans)
#print(k)