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

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache
from math import hypot

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


@lru_cache(maxsize=None)
def subsum(i, a, b):
    if i == n:
        return hypot(a, b)
    res1 = subsum(i + 1, a + s[i][0], b + s[i][1])
    res2 = subsum(i + 1, a, b)
    return max(res1, res2)


print(subsum(0, 0, 0))


### FIXED CODE ###

def solve():
    from math import atan2, pi, hypot
    n = int(input())
    txy = []
    sx, sy = 0, 0
    for i in range(n):
        a, b = map(int, input().split())
        theta_0 = atan2(b, a)
        sx += a
        sy += b
        txy.append((theta_0, a, b))
    txy.sort()
    ans = hypot(sx, sy)
    for i in range(n):
        for j in range(i + 1, n):
            tx, ty = 0, 0
            for k in range(i, j):
                theta, x, y = txy[k]
                tx += x
                ty += y
                ans = max(ans, hypot(tx, ty))
                ans = max(ans, hypot(sx - tx, sy - ty))
    print(ans)

solve()
### BUGGY CODE ###

# 連結成分に分解、異なる連結成分から一人ずつ集めたグループが１セット。
# これを全ての連結成分が空になるまで繰り返す。
# 全ての連結成分が空になる <===> 連結成分の最大の要素数回この操作を繰り返せば良い。
# Union FInd が一番適してそう。
class UnionFind():
    
    def __init__(self,N):
        self.N = N
        self.par = [-1]*N
    
    def find(self,x):
        if self.par[x]<0:return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 
        
        if self.par[x]>self.par[y]:
            x,y = y,x
        
        self.par[x] += self.par[y]
        self.par[y] = x
    
    def members(self,x):
        root = self.find(x)
        return len([i for i in range(self.N) if self.find(i)==root])

    def roots(self):
        return [i for i,x in enumerate(self.par) if x < 0]
    
    def calc_max_mem(self):
        root = self.roots()
        nums = [self.members(r) for r in root]
        return max(nums)


N,M=map(int,input().split())
uf = UnionFind(N)
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1;b -= 1
    uf.union(a,b)
print(uf.calc_max_mem())

### FIXED CODE ###

# 連結成分に分解、異なる連結成分から一人ずつ集めたグループが１セット。
# これを全ての連結成分が空になるまで繰り返す。
# 全ての連結成分が空になる <===> 連結成分の最大の要素数回この操作を繰り返せば良い。
# Union FInd が一番適してそう。
class UnionFind():
    
    def __init__(self,N):
        self.N = N
        self.par = [-1]*N
    
    def find(self,x):
        if self.par[x]<0:return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 
        
        if self.par[x]>self.par[y]:
            x,y = y,x
        
        self.par[x] += self.par[y]
        self.par[y] = x
    

N,M=map(int,input().split())
uf = UnionFind(N)
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1;b -= 1
    uf.union(a,b)
print(-min(uf.par))
### BUGGY CODE ###

A,B,K = map(int,input().split())
li = []
for i in range(A,B+1):
    if abs(A-i)<K:
        li.append(i)
    elif abs(B-i)<K:
        li.append(i)
li.sort()
for j in range(len(li)):
    print(li[j])


### FIXED CODE ###

A,B,K=map(int,input().split())
li=range(A,B+1)
ans=sorted(set(li[:K])|set(li[-K:]))
for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
A = input().split()
if len(set(A)) == 1:
    for _ in range(n):
        print(((n - 1) * (n - 2)) // 2)
    exit()
elif len(set(A)) == len(A):
    for _ in range(n):
        print(0)
    exit()

dA = {}
for a in A:
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

kA = {}
for a in dA:
    kA[a] = (dA[a] - 1) * (dA[a] - 2) // 2
    dA[a] = dA[a] * (dA[a] - 1) // 2

for a in A:
    print(sum(dA.values()) - A.count(a) + 1)


### FIXED CODE ###

n = int(input())
dA = {}
A = []
for a in input().split():
    A.append(a)
    if a in dA:
        dA[a] += 1
    else:
        dA[a] = 1

cA = {}
for a in dA:
    cA[a] = dA[a] * (dA[a] - 1) // 2

s = sum(cA.values())
for a in A:
    print(s - dA[a] + 1)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
check = [True for _ in range(n)]
edges = [[] for _ in range(n)]

for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    check[b - 1] = False
    edges[a - 1].append(b - 1)

rood = check.index(True)
queue = deque()
ans = [0 for _ in range(n)]
queue.append(rood)
queue.append(0)
while queue:
    pos = queue.popleft()
    b_pos = queue.popleft()
    for n_pos in edges[pos]:
        ans[n_pos] = pos + 1
        queue.append(n_pos)
        queue.append(pos)
        
for pos in ans:
    print(pos)

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
check = [0 for _ in range(n)]
edges = [[] for _ in range(n)]

for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    check[b - 1] += 1
    edges[a - 1].append(b - 1)

rood = check.index(0)
queue = deque()
ans = [0 for _ in range(n)]
queue.append(rood)
while queue:
    pos = queue.popleft()
    for n_pos in edges[pos]:
        check[n_pos] -= 1
        if check[n_pos] == 0:
            queue.append(n_pos)
            ans[n_pos] = pos + 1
        
for pos in ans:
    print(pos)
### BUGGY CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
dp=[0]*2**n
dp[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]&~I
 for j in range(n):
  x=1<<j;
  if a&x:dp[I|x]+=dp[I];dp[I|x]%=10**9+7
print(dp[-1])

### FIXED CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
dp=[0]*2**n
dp[0]=1
for I in range(2**n-1):
    a=A[bin(I).count('1')]&~I
    for j in range(n):
        if a&1<<j:dp[I|1<<j]=(dp[I|1<<j]+dp[I])%(10**9+7)
print(dp[-1])
### BUGGY CODE ###

s = str(input())
words = ["dreamer","eraser","dream","erase"]
i = 0
while i<len(s):
    if i<=len(s)-7 and s[i:i+7] == words[0]:
        i += 7
    elif i<=len(s)-6 and s[i:i+6] == words[1]:
        i += 6
    elif i<=len(s)-5 and s[i:i+5] in words:
        i += 5
    elif i>1 and s[i-2:i]=="er":
        if s[i:4]=="aser":
            i += 4
        elif s[i:3]=="ase":
            i += 3
    else:
        break
if i==len(s):
  print("YES")
else:
  print("NO")


### FIXED CODE ###

s = str(input())
words = ["dream","erase","eraser","dreamer"]
i = len(s)
while i>0:
    if s[-5:] in words:
        s = s[:-5]
        i -= 5
    elif s[-6:] in words:
        s = s[:-6]
        i -= 6
    elif s[-7:] in words:
        s = s[:-7]
        i -= 7
    else:
        break
if i==0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  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
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+1):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    for c in range(c1,c2+1):
      ans+=cmb(r+c,r,mod)
      ans%=mod
  print(ans)

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  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
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

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

import collections
N = int(input())
s_list = [collections.Counter(input()) for _ in range(N)]
cnt = 0
for i, s in enumerate(s_list):
    for t in s_list[i+1:]:
        if (s==t): cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
s_list = [input() for _ in range(N)]
dic = {ord("a")+i: i for i in range(26)}
counter = {}
for s in s_list:
    str_cnt = [0]*26
    for char in s:
        str_cnt[dic[ord(char)]] += 1
    str_cnt = ''.join([str(i) for i in str_cnt])
    if (str_cnt in counter):
        counter[str_cnt] += 1
    else:
        counter[str_cnt] = 1
cnt = 0
for k, v in counter.items():
    if (v >= 2):
        cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

S = (input())
ans = 0
while True:
    if "01" in S:
        S = S.replace("01","",1)
        ans+=2
    elif "10" in S:
        S = S.replace("10","",1)
        ans+=2
    else:
        break
print(ans)

### FIXED CODE ###

S = [i for i in input()]
zero = S.count("0")
iti = S.count("1")
print(min(zero,iti)*2)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
for i in range(n):
	l[i]=[l[i],i+1]
l.sort()
count=0
for i in range(n):
	a=l[i]
	for j in range(i+1,n):
		if abs(a[1]-l[j][1])==a[0]+l[j][0]:
			count+=1
		elif abs(a[1]-l[j][1])>n:
			break
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
a={}
b={}
count=0
for i in range(n):
	t=l[i]-(i+1)
	if t in a:
		a[t]+=1
	else:
		a[t]=1
	t=-l[i]-(i+1)
	if t in b:
		b[t]+=1
	else:
		b[t]=1
		# b[t].add(i+1)
for i in a:
	if i in b:
		count+=a[i]*b[i]
print(count)
### BUGGY CODE ###

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, input().split()))

X,Y,Z,K = ints_raw()

A = ints_raw()
B= ints_raw()
C= ints_raw()
#A.sort(reverse=True)
#B.sort(reverse=True)
#C.sort(reverse=True)
def main():
    D = [a+b for a in A for b in B]
    D.sort(reverse=True)
    D = D[:K+1]
    E =[d+c for d in D for c in C]
    E.sort(reverse=True)
    for e in E[:K]:
        print (e)

main()


### FIXED CODE ###

from heapq import *

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int,ss_raw()))

X,Y,Z,K = ints_raw()

A = ints_raw()
B= ints_raw()
C= ints_raw()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

arg_hash = {}

def main():
    Q = []
    heappush(Q,(-A[0]-B[0]-C[0],0,0,0))
    arg_hash[(0,0,0)]=1
    for k in range(K):
        ans = heappop(Q)
        print(-ans[0])
        a,b,c = ans[1:]

        argA = (a+1,b,c)
        if a < X-1 and (not argA in arg_hash):
            arg_hash[argA]=1
            heappush(Q,(-A[a+1]-B[b]-C[c],)+argA)
        argB = (a,b+1,c)
        if b < Y-1 and (not argB in arg_hash):
            arg_hash[argB]=1
            heappush(Q, (-A[a]-B[b+1]-C[c],)+argB)
        argC = (a,b,c+1)
        if c < Z-1 and (not argC in arg_hash):
            arg_hash[argC]=1
            heappush(Q,(-A[a]-B[b]-C[c+1],)+argC)
        
main()
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#[w,v]
#重さに対応するインデックスに価値を保存する
dp=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #i番目の品を入れる場合
    
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])
        #i番目の品を入れない場合
print(dp[-1][-1])

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#[w,v]
#重さに対応するインデックスに価値を保存する
dp=[[0]*(w+1) for i in range(n+1)]
 
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #i番目の品を入れる場合
    
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])
        #i番目の品を入れない場合
print(dp[-1][-1])
### BUGGY CODE ###

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

xy = list()
d2 = d ** 2

for i in range(n):
    xy += map(int,input().split())

#xy_2 = int(len(xy) / 2)
#for i in range(xy_2):
#    x.append(xy.pop(0))
#    y.append(xy.pop(0))
xy2 = list()
for i in range(n):
    xy2.append(xy.pop(0)**2 + xy.pop(0)**2)
    
#xy2_2 = list(set(xy2))

xy2.sort()

ans = 0
#ans += len(xy2) - len(xy2_2)
for i in xy2:
    if d2 >= i:
        ans += 1
#    else:
#        break

print(ans)




### FIXED CODE ###

n,d = map(int,input().split())
d2 = d ** 2

xy2 = list()
for i in range(n):
    x,y = map(int,input().split())
    xy2.append(x**2+y**2)

    ans = 0
for i in xy2:
    if d2 >= i:
        ans += 1
print(ans)
### BUGGY CODE ###

from math import factorial as fac
def cc(n,r):
  def fac2(n,r):
    m = 1
    for i in range(n-r+1,n+1):
      m*=i
    return m
  r = min(r,n-r)
  return fac2(n,r)//fac(r)
n, a, b, k = map(int, input().split())
mod = 998244353
ans = 0
for i in range(min(k//a+1,n+1)):
  jof = k-a*i
  if jof%b==0 and jof<=n*b:
    j = jof//b
    ans += cc(n,i)*cc(n,j)
    ans %= mod
print(ans)

### FIXED CODE ###

n,a,b,k = map(int,input().split())
mod = 998244353
fun = [1]*(n+1)
for i in range(1,n+1):
  fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
  rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
  if r > n:
    return 0
  return fun[n]*rev[r]%mod*rev[n-r]%mod
ans = 0
for i in range(min(n,k//a)+1):
  j = (k-a*i)//b
  if i*a+j*b == k and 0<=j<=n:
    ans += nCr(n,i)*nCr(n,j)
    ans %= mod
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
SUM = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            SUM += gcd(i,j,k)
print(SUM)

### FIXED CODE ###

import math

K = int(input())
SUM = 0
gcdlist = []
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            gcd1 = math.gcd(i,j)
            gcd2 = math.gcd(gcd1,k)
            if i == j and j== k:
                SUM += gcd2
            elif i == j or j == k or k == i:
                SUM += gcd2*3
            else:
                SUM += gcd2*6

print(SUM)
### BUGGY CODE ###

S = list(str(input()))
T = list(str(input()))
check = 1
while len(S) > 0:
  idxS = [j for j, x in enumerate(S) if x == S[0]]
  idxT = [j for j, x in enumerate(T) if x == T[0]]
  if idxS == idxT:
    for i in idxS[::-1]:
      S.pop(i)
      T.pop(i)
  else:
    check = 0
    break
if check:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

S = list(str(input()))
T = list(str(input()))
check = 1
bij1 = {}
bij2 = {}
for i in range(len(S)):
  if S[i] in bij1 and bij1[S[i]] != T[i]:
    check = 0
    break
  elif T[i] in bij2 and bij2[T[i]] != S[i]:
    check = 0
    break
  elif S[i] not in bij1 and T[i] not in bij2:
    bij1[S[i]] = T[i]
    bij2[T[i]] = S[i]
    
if check:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

#!/usr/bin/env python3


def argmax(scores):
    index = 0
    mx = 0
    for i, s in enumerate(scores):
        if mx < s[0]:
            mx = s[0]
            index = i
    return index


def main():
    N, K = input_line(int, int)
    A = input_line(*[int for i in range(N)])
    F = input_line(*[int for i in range(N)])
    A.sort()
    F.sort(reverse=True)
    scores = [[a*f, a, f] for a, f in zip(A, F)]
    scores.sort(key=lambda x: x[0], reverse=True)
    index = argmax(scores)
    while K > 0 and scores[index][1] > 0:
        scores[index][1] -= 1
        scores[index][0] = scores[index][1] * scores[index][2]
        K -= 1
        index = argmax(scores)
    print(scores[index][0])


def input_line(*types):
    if len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np


def is_ok(mid, K, A, F):
    return np.maximum(A - mid // F, 0).sum() <= K


def main():
    N, K = input_line(int, int)
    A = input_line([int])
    F = input_line([int])
    A = np.array(sorted(A))
    F = np.array(sorted(F, reverse=True))

    ng = -1
    ok = int(1e12)
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if is_ok(mid, K, A, F):
            ok = mid
        else:
            ng = mid
    print(ok)


def input_line(*types):
    if isinstance(types[0], list):
        return [types[0][0](x) for x in input().split()]
    elif len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


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

from itertools import combinations
n,k = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(n)]
p,ans = sorted(p),float("inf")
for q in combinations(p,min(4,k)):
	r = sorted(j for i,j in q)
	xa,xb,ya,yb = q[0][0],q[-1][0],r[0],r[-1]
	num = sum(1 for i,j in p if xa<=i<=xb and ya<=j<=yb)
	if num>=k: ans = min(ans,(xb-xa)*(yb-ya))
print(ans)

### FIXED CODE ###

n,k = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(n)]
p,ans = sorted(p),float("inf")
q = list(enumerate(p))
for i,(a,b) in q[:n-k+1]:
	for j,(c,d) in q[i+k-1:]:
		r = sorted(y for x,y in p[i:j+1])
		r2 = r[k-1:]
		for i2,j2 in zip(r,r2):
			if i2<=b and d<=j2: ans = min(ans,(c-a)*(j2-i2))
print(ans)
### BUGGY CODE ###

def pow(a, n, mod):
    if n == 0:
        return 1
    elif n == 1:
        return a % mod
    ret = 1
    if n % 2 == 1:
        v = pow(a, n // 2, mod)
        w = pow(a, n // 2 + 1, mod)
        ret *= v * w
    else:
        v = pow(a, n // 2, mod)
        ret *= v ** 2
    return ret % mod


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def pow(a, n, mod):
    ret = 1
    pw = a
    while n > 0:
        if n & 1 == 1:
            ret *= pw
            ret %= mod
        n >>= 1
        pw *= pw
        pw %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


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

N = int(input())
str_list = []
for i in range(N):
  str_dict = {}
  for j in input():
    if j in str_dict:
      str_dict[j] += 1
    else:
      str_dict[j] = 1
  str_list.append(str_dict)
  
count = 0
for i in range(N):
  for j in range(i+1, N):
    if str_list[i] == str_list[j]:
      count += 1
print(count)


### FIXED CODE ###

N = int(input())
str_list = {}
for i in range(N):
  str_dict = {}
  for j in input():
    if j in str_dict:
      str_dict[j] += 1
    else:
      str_dict[j] = 1
  key = "".join([str(k)+str(v) for k, v in sorted(str_dict.items(), key=lambda x:x[0])])
  if key in str_list:
    str_list[key] += 1
  else:
    str_list[key] = 1
  
result = sum([i*(i-1)//2 for i in str_list.values()])
print(result)
### BUGGY CODE ###

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

m = p[0:K]
for i in range(1,N-K+1):
    if sum(m) < sum(p[i:K+i]):
        m = p[i:K+i]

for l in range(0,K):
     m[l] = (1+m[l])/2
n = sum(m)
print(n)

### FIXED CODE ###

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

s = 0
for i in range(0,K):
    s = s + p[i]
t = s
for j in range(0,N-K):
    u = s + p[j+K] - p[j]
    if u > t:
        t = u
    s = u
print((t+K)/2)
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**12
def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    a=s
    used=np.append(used,a)
    for i in range(N):
        if i!=a and not(i in used):
            cost=d[a,i] if a<=i else d[i,a]
            if cost!=INF:
                table[i]=min(table[i],table[a]+cost)
                heapq.heappush(heap,(table[i],i))
    while heap:
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if i!=a and not(i in used):
                cost=d[a,i] if a<=i else d[i,a]
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]


N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])]

d=np.array([[INF for j in range(N)] for i in range(N)])
for i in range(N):
    d[i,i]=0
l=np.array([i+1 for i in range(N)])
l[-1]=N
for m in range(M):
    L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
    for i in range(L,R+1):
        if l[i]<N:
            d[i,l[i]:R+1]=C
            l[i]=R+1

ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,y=map(int,input().split())
i,j,f=0,0,0
for i in range(y//10000+1):
    a=y-10000*i
    for j in range(a//5000+1):
        p=a-5000*j
        for f in range(p//1000+1):
            o=p-1000*f
            if o>(n-(i+j))*1000:
                break
            elif o==0 and i+j+f==n:
                print(i,j,f)
                exit()
print(-1,-1,-1)

### FIXED CODE ###

n,y=map(int,input().split())
i,j,f=0,0,0
for i in range(y//10000+1):
    a=y-10000*i
    for j in range(a//5000+1):
        p=a-5000*j
        if i+j+p//1000==n:
            print(i,j,p//1000)
            exit()
print(-1,-1,-1)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            ans += gcd(x,y,z)
            
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            ans += gcd(x,y,z)
            
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
slis=list(input())
ta_slis=[]
for i in range(q):
	l,r=map(int,input().split())
	t_slis=slis[l-1:r]
	counter=0
	for j in range(len(t_slis)-1):
		if t_slis[j]=='A':
			if t_slis[j+1]=='C':
				counter+=1
	print(counter)

### FIXED CODE ###

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