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

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

def light(a_list):
    outcome= [0]*n
    for i in range(n):
        for j in range(max(0,i-a_list[i]),min(n,i+a_list[i]+1)):
            outcome[j] += 1
    return outcome

for _ in range(k):
    a = light(a)

[print(aa,end=' ') for aa in a]

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]
### BUGGY CODE ###

import itertools
import numpy as np

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

l = []
for i in range(N):
    num = int(input())
    l.append(num)
l = np.array(l)

min_loss = 9999999999999999
for pat in itertools.product(["A", "B", "C", "D"], repeat=N):
    if pat.count("A") > 0 and pat.count("B") > 0 and pat.count("C") > 0:
        pat = np.array(pat)
        pat_A = l[pat == "A"]
        pat_B = l[pat == "B"]
        pat_C = l[pat == "C"]

        loss_A = abs(A-pat_A.sum())+10*(len(pat_A)-1)
        loss_B = abs(B-pat_B.sum())+10*(len(pat_B)-1)
        loss_C = abs(C-pat_C.sum())+10*(len(pat_C)-1)

        loss = loss_A+loss_B+loss_C
        min_loss = min(min_loss, loss)

print(min_loss)


### FIXED CODE ###

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

l_in = []
for i in range(N):
    num = int(input())
    l_in.append(num)


def dfs(cur, a_sum, b_sum, c_sum):
    if cur == N:
        return abs(A-a_sum)+abs(B-b_sum)+abs(C-c_sum)-30 if a_sum*b_sum*c_sum > 0 else 100000000

    pat0 = dfs(cur+1, a_sum, b_sum, c_sum)
    pat1 = dfs(cur+1, a_sum+l_in[cur], b_sum, c_sum)+10
    pat2 = dfs(cur+1, a_sum, b_sum+l_in[cur], c_sum)+10
    pat3 = dfs(cur+1, a_sum, b_sum, c_sum+l_in[cur])+10

    return min(pat0, pat1, pat2, pat3)


print(dfs(0, 0, 0, 0))
### BUGGY CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
a_list = input().split()
a_queue = []
for a in a_list:
    heappush(a_queue, int(a))

for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        m = heappop(a_queue)
        heappush(a_queue, max(m, c))

print(sum(a_queue))

### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
a_list = input().split()
priority_queue = []
for a in a_list:
    heappush(priority_queue, (-int(a), 1))

for i in range(m):
    b, c = map(int, input().split())
    heappush(priority_queue, (-c, b))

res = 0
for i in range(n):
    c_, b = heappop(priority_queue)
    res += -c_
    b -= 1
    if b > 0:
        heappush(priority_queue, (c_, b))

print(res)
### BUGGY CODE ###

N = int(input())
res = 1
temp = 1

for i in range(1, N + 1):
    res = res * i

for i in range(9):
    temp = temp * 10
temp = temp + 7


print(res % temp)


### FIXED CODE ###

N = int(input())
ans = 1

for i in range(1, N + 1):
    ans = (ans * i) % (10 ** 9 + 7)

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

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
sums = []
total = 0
for i in a:
    total += i
    sums.append(total)
sums.pop()
# print(sums)
ans = 2 * 10 ** 9 + 1
# print(sums)
for i in sums:
    ans = min(ans, abs(i - (sum(a) - i)))
print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
sums = [0] * (n - 1)
total = 0
for i in range(n - 1):
    total += a[i]
    sums[i] = total
ans = 2 * 10 ** 9 + 1
a_sum = sum(a)
for i in sums:
    ans = min(ans, abs(i - (a_sum - i)))
print(ans)
### BUGGY CODE ###

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1
amari = []

for j in range(10):
  for i in range(13):
    amari.append(((i*10+j)%13,i))

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for i in amari:
      a[i[0]] += p[i[1]]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])

### FIXED CODE ###

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])
### BUGGY CODE ###

import bisect
import sys
N,Q = map(int,raw_input().split())
if N == 1:
  for i in range(Q):
    a,b = map(int,raw_input().split())
    print(min(a,b))
  sys.exit()

MAXN = 10**9
borders = [1]
while borders[-1] < MAXN:
  borders.append(borders[-1] + N**(len(borders) - 1))

def pos(a):
  rank = bisect.bisect_right(borders, a) - 1
  idx = a - borders[rank]
  return (rank,idx)

def parent(p):
  rank,idx = p
  return (rank-1, idx//N)

for i in range(Q):
  a,b = map(int,raw_input().split())
  p1,p2 = pos(a),pos(b)
  while p1 != p2:
    if p1 > p2:
      p1 = parent(p1)
    else:
      p2 = parent(p2)
  rank,idx = p1
  print(borders[rank] + idx) 

### FIXED CODE ###

N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))
### BUGGY CODE ###

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

for j in range(m):
    new_a = sorted(a)
    for b in range(bc[j][0]):
        if new_a[b] < bc[j][1]:
            new_a[b] = bc[j][1]
    a = new_a
print(sum(a))

### FIXED CODE ###

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

bc = sorted(bc, key=lambda x: (x[1]), reverse=True)
count = 0
for b, c in bc:
    count += b
    a.extend([c]*b)
    if count >= n:
        break
print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

# coding: utf-8

import re

def _main():
    text = input()
    count = 0

    while True:
        new_text = re.sub(r'01|10', '', text, 1)

        if text == new_text:
            break
        else:
            count += 2
            text = new_text

    print(count)



if __name__ == '__main__':
    _main()

### FIXED CODE ###

# coding: utf-8

def _main():
    text = input()

    zero_count = text.count('0')
    one_count = len(text) - zero_count

    ans = min(zero_count, one_count) * 2

    print(ans)



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

def inputs():
    return [int(x) for x in input().split()]
N,M = inputs()
E={i:[] for i in range(1,N+1)}
for i in range(M):
    L,R,D = inputs()
    E[L].append((R,D))
    E[R].append((L,-D))
visited = {i: False for i in range(1, N+1)}
counter = 0
dis = [0]*(N+1)
while False in visited.values():
    stk = [(list(visited.values()).index(False) + 1, -1, 0)]
    flag = True
    while stk:
        v, p, d = stk.pop()
        #print(v,p)
        if visited[v]:
            if dis[v]!=dis[p]+d:
                print("No")
                exit()
            continue
        visited[v] = True
        dis[v]=dis[p]+d
        for u,d in E[v]:
            if u != p:
                stk.append((u,v,d))
print("Yes")

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    for i in range(1,N+1):
        if not visited[i]:
            stk = [( i, -1, 0)]
            while stk:
                v, p, d = stk.pop()
                #print(v,p)
                if visited[v]:
                    if dis[v]!=dis[p]+d:
                        print("No")
                        exit()
                    continue
                visited[v] = True
                dis[v]=dis[p]+d
                for u,d in E[v]:
                    if u != p:
                        stk.append((u,v,d))
    print("Yes")
main()
### BUGGY CODE ###

import numpy as np

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


for i in range(n):
    y = x.pop(i)
    print(int(np.median(x)))
    x.insert(i, y)

### FIXED CODE ###

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

y = sorted(x, reverse=True)
me1 = y[(n+1) // 2 - 1]
me2 = y[(n+1) // 2]
for i in range(n):
    if x[i] <= me2:
        print(me1)
    else:
        print(me2)
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0

  for i in range(h):
    for j in range(w):
      for k in range(h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          visited=[[-1]*w for _ in range(h)]
          for _ in range(inf):
            if len(q)<=0:
              break
            y,x,c=q.popleft()
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
              ny=y+dy
              nx=x+dx
              if 0<=ny<h and 0<=nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

N=int(input())
S=[]
L=[]
C=[]

for i in range(N):
    S.append(str(input()))

S.sort()
L.append(S[0])
C.append(S.count(S[0]))

for i in range(1,N):
    if S[i]!=S[i-1]:
        L.append(S[i])
        C.append(S.count(S[i]))
count_max=max(C)
for i in range(len(L)):
    if C[i]==count_max:
        print(L[i])

### FIXED CODE ###

N=int(input())
S=[]
L=[]
C=[]

for i in range(N):
    S.append(str(input()))

S.sort()
L.append(S[0])
C.append(1)
cur=0

for i in range(1,N):
    if S[i]!=S[i-1]:
        L.append(S[i])
        C.append(1)
        cur+=1
    else:
        C[cur]+=1
count_max=max(C)
for i in range(len(L)):
    if C[i]==count_max:
        print(L[i])
### BUGGY CODE ###

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

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(n-i,n+1):
        count += info[j]
    if count != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
if ans != []:
    print(" ".join(map(str,ans)))

### FIXED CODE ###

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

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(" ".join(map(str,ans)))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [int(input()) for i in range(Q)]
keys = [i for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1]*Q
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    count = 0
    it = bisect.bisect_left(D, m)
    while it != len(D):
        if D[it] >= n:
            break
        ans[keys[it]] = xi
        D[it] = 0
        keys[it] = 0
        it += 1
        count += 1
    D.sort()
    D = D[count:]
    keys.sort()
    keys = keys[count:]
[print(i) for i in ans]

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q
check = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    while l < r:
        if check[l] == -1:  
            ans[l] = e[2]
            check[l] = r
            l += 1
        else:
            l = check[l]
        
[print(i) for i in ans]
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = 0
S = []
for j in range(N-1):
    S.append(sum(A[:N-j-1]))

for i in range(N-1):
    Ans += A[N-i-1]*S[i]

print(Ans%((10**9)+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = 0
S = sum(A)

for i in range(N-1):
    S -= A[N-i-1]
    Ans += A[N-i-1]*S

print(Ans%((10**9)+7))
### BUGGY CODE ###

X = int(input())
queue = [(0,0)]
while queue:
  time, location = queue.pop(0)
  if location == X:
    print(time)
    break
  time+=1
  queue.append((time,location+time))
  queue.append((time,location))
  queue.append((time,location-time))

### FIXED CODE ###

X = int(input())
t = 1
for t in range(1,X+1):
  total = t*(t+1)/2
  if total>=X:
    break
print(t)
### BUGGY CODE ###

import numpy as np


def solve(string):
    n, *a = map(int, string.split())
    t = np.zeros(n)
    ans = []
    for i, _a in zip(range(n, 0, -1), a[::-1]):
        s = t[i - 1::i].sum() % 2
        if s == _a:
            continue
        ans.append(str(i))
        t[i - 1] += 1
    return "0" if len(ans) == 0 else "{}\n{}".format(len(ans), " ".join(ans[::-1]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

from math import ceil


def solve(string):
    n, *a = map(int, string.split())
    t = [0] * n
    ans = []
    for i, _a in zip(range(n, 0, -1), a[::-1]):
        if t[i - 1] % 2 == _a:
            continue
        ans.append(str(i))
        for j in range(1, ceil((i + 1)**0.5)):
            if i % j == 0:
                t[j - 1] += 1
                if j != i // j:
                    t[i // j - 1] += 1
    return "0" if len(ans) == 0 else "{}\n{}".format(len(ans), " ".join(ans[::-1]))

  
if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
### BUGGY CODE ###

a,b = map(int, input().split())
l = list(map(int, input().split()))
max = 0
e = 0
temp = 0
pr = []

for i in range(a-b+1):
  temp = sum(l[i:i+b])
  if temp >= max:
    max = temp
    pr = l[i:i+b]

for j in pr:
  for k in range(1,j+1):
    e += k*(1/j)
  
print(e)


### FIXED CODE ###

a,b = map(int, input().split())
l = [(int(i)+1)/2 for i in input().split()]

temp = sum(l[:b])
max = temp
for i in range(b,a):
  temp = temp + l[i] - l[i-b]
  if max < temp:
    max = temp
    
print(max)
### BUGGY CODE ###

import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0:
        OK = False

h = 0
for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")




### FIXED CODE ###

import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(readline())

ls = []
rs = []

total = 0
S = list(map(lambda x: x.strip().decode(), readlines()))

for i in range(n):
    s = S[i]

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0:
        OK = False

h = 0
for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

a,b,n=map(int,input().split())
'''
lst=[]
for i in range(n+1):
    now=int(a*i/b)-a*int(i/b)
    lst.append(now)
print(max(lst))
'''
now=0
if n>=b:
    if n//b>=500000:
        ans=int(a*(n-1)/b)-a*int((n-1)/b)
        ans2=int(a*n/b)-a*int(n/b)
        for i in range(0,n//b+1,10000):
            ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
            now=max(now,ans3)
        print(max(ans,ans2,now))
        exit()
    ans=int(a*(n-1)/b)-a*int((n-1)/b)
    ans2=int(a*n/b)-a*int(n/b)
    for i in range(n//b+1):
        ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
        now=max(now,ans3)
    print(max(ans,ans2,now))

else:
    ans=int(a*(n)/b)-a*int((n)/b)
    print(max(ans,0))

### FIXED CODE ###

a,b,n=map(int,input().split())
def ans(x):
    return int(a*x/b)
print(ans(min(n,b-1)))
### BUGGY CODE ###

import collections
N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
for i in set(A):
  if A.count(i) % 2 != 0:
    ans += 1

print(ans)


### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for _ in range(N)]
count = collections.Counter(A)

l = []
for i in list(count):
  if count[i] % 2 != 0:
    l.append(count[i])

print(len(l))
### BUGGY CODE ###

import fractions

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = 1
for i in a:
    LCM = lcm(LCM, i)

ans = 0
for i in a:
    ans += LCM // i
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 1000000007

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)
### BUGGY CODE ###

from bisect import bisect_left as bl
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[1]+[0]*(n-1)
q=[[0,[a[0]],1]]
while q:
    c,d,e=q.pop(0)
    for i in t[c]:
        s=d[::]
        g=e
        if b[i]==0:
            h=bl(d,a[i])
            if e>h:
                s[h]=a[i]
            else:
                s.append(a[i])
                g+=1
            b[i]=g
            q.append([i,s,g])
for i in range(n):
    print(b[i])


### FIXED CODE ###

from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
set0=set(range(1,n+1))
for i in range(m):
  l,r=map(int,input().split())
  id_set=set(range(l,r+1))
  set0=set0&id_set
print(len(set0))

### FIXED CODE ###

n,m=map(int,input().split())
l0,r0=1,n
for i in range(m):
  l,r=map(int,input().split())
  if l>r0 or r<l0:
    print(0)
    exit()
  else:
    l0=max(l0,l)
    r0=min(r0,r)
print(r0-l0+1)
### BUGGY CODE ###

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

targets = [N - R * i for i in range(int(N / R) + 1)]
score = 0
for g in range(3001):
    for b in range(3001):
        if g + b > 3000:
            break
        if (g * G + b * B) in targets:
            score += 1

print(score)

### FIXED CODE ###

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

score = 0

for g in range(3001):
    for b in range(3001):
        if g + b > 3000:
            break
        if (N - (g * G + b * B)) >= 0 and (N - (g * G + b * B)) % R == 0:
            score += 1

print(score)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * N
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, K+1) if i-j >= 0)
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * N
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(i, K) + 1))
print(dp[-1])
### BUGGY CODE ###

K = int(input())
count = 0
an = 0

if K%2 == 0 or K%2 ==0:
    print("-1")
    exit(0)
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
     break
print(count)

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

N=int(input())
s=list(map(int, input().split()))
a=1
for i in range(N):
  a*=s[i]
print(-1 if a>1000000000000000000 else a)

### FIXED CODE ###

N=int(input())
s=sorted(list(map(int, input().split()))[::-1])
a=1
for i in range(N):
  if a>10**18:
    break
  a*=s[i]
print(-1 if a>10**18 else a)
### BUGGY CODE ###

N,Q=map(int,input().split())
y=input()
arr=[]
for i in range(len(y)-1):
    if y[i:i+2]=='AC':
        arr.append(1)
    else:
        arr.append(0)
        
for q in range(Q):
    l,r=map(int,input().split())
    print(sum(arr[l-1:r-1]))

### FIXED CODE ###

import numpy as np

N,Q=map(int,input().split())
y=input()
arr=np.zeros(len(y))
for i in range(len(y)-1):
    if y[i:i+2]=='AC':
        arr[i+1]=arr[i]+1
    else:
        arr[i+1]=arr[i]
              
for q in range(Q):
    l,r=map(int,input().split())
    print(int(arr[r-1]-arr[l-1]))