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

n = int(input())
s =input()
s = "0" + s
ans = 0
 
for i in range(1, n - 1):
    for j in range(i + 1 , n):
        if s[i] == s[j]:
            continue
        elif (s[i] == "R" and s[j] == "G") or (s[i] == "G" and s[j] == "R"):
            ans += s.count("B", j , n + 1)
            if 2 * j - i <= n:
                if s[2 *j - i] == "B":
                    ans -=1
        elif (s[i] == "R" and s[j] == "B") or (s[i] == "B" and s[j] == "R"):
            ans += s.count("G", j , n + 1)
            if 2 * j - i <= n:
                if s[2 *j - i] == "G":
                    ans -=1
        elif (s[i] == "B" and s[j] == "G") or (s[i] == "G" and s[j] == "B"):
            ans += s.count("R", j , n + 1)
            if 2 * j - i <= n:
                if s[2 *j - i] == "R":
                    ans -=1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
s = "0" + s
ans = s.count("R") * s.count("G") * s.count("B")

for i in range(1,n):
    for j in range(i + 1, n + 1):
        if 2 * j - i <= n:
            if s[i] != s[j] and s[i] != s[2*j -i] and s[j] != s[2*j -i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
 
a = list(map(int, input().split()))
 
def myindex(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default
 
for i in range(1, n+1):
  b = myindex(a, i, default=-1)
  if b == -1:
    del a[(i-1):]
    break
  else:
    del a[(i-1):b]
 
 
if len(a) == 0:
  print('-1')
 
else:
  print(n - len(a))

### FIXED CODE ###

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

card = 1
cnt = 0

for i in a:
  if i == card:
    card += 1
  else:
    cnt += 1

if cnt == n:
  print('-1')

else:
  print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
x = input()

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count

# int変換
x = int(x,2)

def toggle_nth_bit(num: int, n: int):
    """下から数えてn桁目を反転"""
    return num ^ (1 << n)

ans = []

for i in range(0,n):
    tmp_x = toggle_nth_bit(x,i)
#    tmp_n = countSetBits(tmp_x)
    tmp_n = bin(tmp_x).count('1')
    tmp = 0
    while tmp_x > 0:
        tmp_x %= tmp_n
#        tmp_n = countSetBits(tmp_x)
        tmp_n = bin(tmp_x).count('1')
        tmp += 1
    ans.append(tmp)
    
print(*ans[::-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
s = input()

def pcnt(x):
    return bin(x).count('1')

def f(x):
    if x == 0: return 0
    return f(x%pcnt(x))+1

x = [0]*n

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

# 元のpopcountを求める
pc = sum([x[i] for i in range(n)])

ans = [0]*n

# b: 元のbit
for b in range(2):
    npc = pc
    if b == 0: npc += 1
    else: npc -= 1
        
    if npc <= 0: continue # 0除算が発生するため
    
    # 元の数をpopcountで割ったあまりを求める
    # 例えば2進数1101を10進数に変換するには、1, 1の2倍の2に1を足して3, 3の2倍の6に0を足して6, 6の2倍に1を足して13、と計算できる。今回はこれを%npcする操作が加わる
    r0 = 0
    for i in range(n):
        r0 = (r0*2)%npc
        r0 += x[i]
    
    # 一番下の桁からループを回す
    # i桁目をフリップしたときのあまりを求める
    # 下からi桁目をフリップすると2^i変わる。その値をkとして計算する。同じループの中で2^i(k)のあまりも求める
    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == b:
            r = r0
            if b == 0: r = (r+k)%npc
            else: r = (r-k+npc)%npc # r-kだけだとマイナスになることがある
            ans[i] = f(r)+1
        k = (k*2)%npc

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

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

ans = []

for i in range(1, N+1):
    ans.append(((A*i)//B) - A*(i//B))

print(max(ans))

### FIXED CODE ###

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

if N < B:
    ans = ((A*N)//B) - A*(N//B)
elif B <= N < 2*B:
    ans = max((((A*N)//B) - A*(N//B)), (((A*(B-1))//B) - A*((B-1)//B)))
elif 2*B <= N:
    ans = max((((A*(B-1))//B) - A*((B-1)//B)), (((A*(2*B-1))//B) - A*((2*B-1)//B)), (((A*(3*B-1))//B) - A*((3*B-1)//B)))

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

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

for i in range(n-1):
    for j in range(i+1,n):
        out.append(a[i]*a[j])
out.sort()
print(out[k-1])


### FIXED CODE ###

import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=np.int64)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd

N=int(input())
a_list = list(map(int, input().split()))
MOD = 10**9+7


def cal_lcm(a, b):
  return int(a*b//gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = (ans*(lcm_//lcm) + (lcm_//a_list[i]) )% MOD
  lcm = lcm_

print(ans)

### FIXED CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
hlist = []
for i in range(n):
    hlist.append(int(input()))
hlist.sort()
h = []
for j in range(n-k+1):
    h.append(max(hlist[j:j+k])-min(hlist[j:j+k]))
print(min(h))


### FIXED CODE ###

n, k = map(int, input().split())
hlist = []
for i in range(n):
    hlist.append(int(input()))
hlist.sort()
h = []
for j in range(n-k+1):
    h.append(hlist[j+k-1]-(hlist[j]))
print(min(h))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)
### BUGGY CODE ###

def main():
    n=int(input())
    a=1
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        a=m+1
        print("Yes")
    else:
        print("No")
        exit()
    print(a)
    s=set(range(1,1+n))
    l=[0]*(n+1)
    ans=[set()]

    for i in range(a):
        ll=set()
        for j in ans[:i+1]:
            for p in s&j-ll:
                ll.add(p)
                if l[p]==1:
                    s.remove(p)
                else:
                    l[p]+=1
                break

        for p in s:
            if len(ll)>=n*2//a:
                break
            else:
                if l[p]==0:
                    ll.add(p)
                    l[p]+=1

        ans.append(ll)
    for i in ans[1:]:
        print(n*2//a,*i)


if __name__ == '__main__':
    main()








### FIXED CODE ###

def main():
    n=int(input())
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        print("Yes")
        m+=1
        print(m)
    else:
        print("No")
        exit()
    
    ans=[[m-1] for i in range(m)]
    c=1
    for i in range(m):
        for j in range(i+1,m):
            ans[i].append(c)
            ans[j].append(c)
            c+=1
    for i in ans:
        print(*i)


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

import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
s = [0] * M
t = [0] * M
for i in range(M):
    s[i], t[i] = map(int, input().split())

#output
#（便宜的に地点から-1としておく）
u = [[]] * N
for v in s:
    u[v-1] = [t-1 for i, t in enumerate(t) if s[i] == v]

#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for v in range(N):
    for i in range(v):
        if v in u[i]:
            p[v] += p[i]/len(u[i])

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for v in reversed(range(N)):
    for i in u[v]:
        q[v] += (1 + q[i])/len(u[v])

v = [0] * N
for i in range(N):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))


### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
u = [[] for i in range(N-1)]
#（便宜的に地点から-1としておく）
for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)

#output
#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for x, y in enumerate(u):
    for z in y:
        p[z] += p[x]/len(y)

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for x, y in list(enumerate(u))[::-1]:
    q[x] = sum(q[z] for z in y)/len(y) + 1

v = [0] * N
for i in range(N-1):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))
### BUGGY CODE ###

N = int(input())
s = []
l = 0
for i in range(0,N):
    s.append(str(input()))
for i in range(0,N):
    s[i] = ''.join(sorted(s[i]))
s.sort()
for i in range(0,N-1):
    for n in range(i+1,N):
        if s[i] == s[n]:
            l += 1
print(l)


### FIXED CODE ###

N = int(input())
s = []
l = 1
z = 0
for i in range(0,N):
    s.append(str(input()))
for i in range(0,N):
    s[i] = ''.join(sorted(s[i]))
s.sort()
for i in range(0,N-1):
    if s[i] == s[i+1]:
        l += 1
    else:
        z += l*(l-1)/2
        l = 1
z += l*(l-1)/2
print(int(z))
### BUGGY CODE ###

K,S = map(int,input().split())
cnt = 0
for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                cnt += 1
                
print(cnt)

### FIXED CODE ###

K,S = map(int,input().split())
cnt = 0
for i in range(K + 1):
    for j in range(K + 1):
        k = S - i - j
        if 0<= k <= K:
            cnt += 1
                
print(cnt)
### BUGGY CODE ###

a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
    i = max(s)
    c = min(a,b)
  else:
    i += 1
print(len(s))

### FIXED CODE ###

a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c**0.5+1:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
  else:
    if a%i==0: a//=i
    if b%i==0: b//=i
    i += 1
  c = min(a,b)
if c!=1 and max(a,b)%c==0 and all([i==1 or c%i>0 for i in s]):
  s.append(c)
print(len(s))
### BUGGY CODE ###

diction = []
for i in range(int(input())):
    command = input().split()
    if command[0] == "insert":
        diction.append(command[1])
    else:
        if command[1] in diction:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

import sys
n = int(input())
dictionary = {}

k = sys.stdin.readlines()


for j in k:
    i = j.split()
    if i[0] == "insert":
        dictionary[i[1]] = 0
    else:
        if i[1] in dictionary:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  if len(values) > 500000:
    print('Yes')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


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

#!/usr/bin python3
# -*- coding: utf-8 -*-

import itertools

n, k = map(int, input().split())
a = list(itertools.accumulate(list(map(int, input().split()))))
a = [0] + a
s = []
for i in range(n+1):
    for j in range(i,n+1):
        s.append(list(format(a[j]-a[i], '050b')))

ret = 0
sel = set(range(n*(n+1)//2))
for i in range(50):
    nxt = set([])
    for j in sel:
        if s[j][i] == '1':
            nxt.add(j)
    if len(nxt)>=k:
        sel = nxt
        ret += 2**(49-i)
print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import itertools

n, k = map(int, input().split())
a = list(itertools.accumulate(list(map(int, input().split()))))
a = [0] + a
s = [None] * (n*(n+1)//2)
cnt = 0
for i in range(n+1):
    for j in range(i+1,n+1):
        s[cnt] = format(a[j]-a[i], '050b')
        cnt += 1

ret = 0
sel = set(range(n*(n+1)//2))
for i in range(50):
    nxt = set([])
    for j in sel:
        if s[j][i] == '1':
            nxt.add(j)
    if len(nxt)>=k:
        sel = nxt
        ret += 2**(49-i)
print(ret)
### BUGGY CODE ###

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

count = 0
for i in range(A, B+1):
  if i % C != 0 and i % D != 0:
    count += 1

print(count)

### FIXED CODE ###

import math
 
def lcm(a, b):
    return (a*b)//math.gcd(a, b)
 
a, b, c, d = map(int, input().split())
e = lcm(c, d)
 
total = b - (a - 1)
cc = b//c - (a-1)//c
dd = b//d - (a-1)//d
ee = b//e - (a-1)//e
 
ans = total - cc - dd + ee
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
a = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
	ss = input()
	s.append(ss)
	b = 0
	for j,k in enumerate(ss):
		if k == "#":
			b = 0
			a[i][j] == 0
		else:
			b += 1
			a[i][j] = b
	mx = 0
	for j in range(w-1,-1,-1):
		if a[i][j] == 0:
			mx = 0
			continue
		else:
			mx = max(a[i][j],mx)
			a[i][j] = mx

c = [[0 for i in range(h)] for j in range(w)]
for i in range(w):
	v = ""
	b = 0
	for j in range(h):
		v += s[j][i]
	for j,k in enumerate(v):
		if k == "#":
			b = 0
			c[i][j] == 0
		else:
			b += 1
			c[i][j] = b
	mx = 0
	for j in range(h-1,-1,-1):
		if c[i][j] == 0:
			mx = 0
			continue
		else:
			mx = max(c[i][j],mx)
			c[i][j] = mx

wk = 0
ans = 0
for i in range(h):
	for j in range(w):
		wk = a[i][j] + c[j][i] -1
		ans = max(ans,wk)
print (ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
  t = input()
  s.append(t)
yokol = [[0 for i in range(w)] for j in range(h)]
yokor = [[0 for i in range(w)] for j in range(h)]
tateu = [[0 for i in range(w)] for j in range(h)]
tated = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
  cnt = 0
  for j in range(w):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      yokol[i][j] = cnt
  cnt = 0
  for j in reversed(range(w)):
    if s[i][j] == '#':
      cnt=0
    else:
      cnt += 1
      yokor[i][j] = cnt

for j in range(w):
  cnt = 0
  for i in range(h):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tateu[i][j] = cnt
  cnt = 0
  for i in reversed(range(h)):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tated[i][j] = cnt

ans = 0
for i in range(h):
  for j in range(w):
    x = yokol[i][j] + yokor[i][j] + tateu[i][j] + tated[i][j] - 3
    ans = max(ans,x)
print (ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


cnt = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        t = L[i] + L[j]
        idx = bisect_left(L, t, j + 1)
        cnt += max(0, idx - j - 1)
print(cnt)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
from bisect import bisect_left 
cnt = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    t = L[i]+L[j]
    idx = bisect_left(L,t,j+1)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        p = [sum([pow(x, i, mod) for x in range(a, b+1)]) %
             mod for i in range(c+1)]
        for i in range(c+1):
            dp2[i] = sum([dp[i-j]*p[j] for j in range(i+1)]) % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0

    p = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        q = [0]*(c+1)
        for i in range(c+1):
            q[i] = sum(p[i][a:b+1]) % mod
        for i in range(c+1):
            temp = 0
            for j in range(i+1):
                temp += dp[i-j]*q[j]
            dp2[i] = temp % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()
### BUGGY CODE ###

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

me = []
for p in P:
    me.append((p * (p + 1) / 2) / p)

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(me[i:i+k]))
print(ans)


### FIXED CODE ###

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

ave_pl = []
for i, p in enumerate(pl):
    p_sum = p*(p+1)/2
    if i == 0:
        ave_pl.append(p_sum/p)
    else:
        ave_pl.append(ave_pl[i-1]+(p_sum/p))

ans = 0
if n == k:
    print(ave_pl[-1])
else:
    for i in range(k-1, n):
        if i == 0:
            ans = max(ans, ave_pl[i])
        else:
            ans = max(ans, ave_pl[i]-ave_pl[i-k])
    print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
a = [s[0:i+1].count("AC") for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    print(a[r-1] - a[l-1])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n+1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for j in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)
### BUGGY CODE ###

s=input()
l=len(s)
amari=[0]*(l+1)
for i in range(1,l+1):
    amari[i]=int(s[l-i:])%2019

from collections import Counter
myc = Counter(amari)
val=list(myc.values())

ans=0
for i in range(len(val)):
    ans+=val[i]*(val[i]-1)//2
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
visited = [False] * N
visited[0] = True


def dfs(v):
    if v == N-1:
        return [N-1]
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        ret = dfs(u)
        visited[u] = False
        if ret:
            return [v] + ret
    return None


path = dfs(0)
l = len(path)
u, v = 0, 0
if l % 2 == 0:
    u = path[l//2-1]
    v = path[l//2]
else:
    u = path[l//2]
    v = path[l//2+1]
G[u].remove(v)
G[v].remove(u)


def dfs2(v):
    global fen
    fen += 1
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        dfs2(u)
        visited[u] = False


fen = 0
dfs2(0)
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)


def dfs(v, dist):
    for u in G[v]:
        if dist[u] != -1:
            continue
        dist[u] = dist[v] + 1
        ret = dfs(u, dist)


dist_fen = [-1] * N
dist_fen[0] = 0
dfs(0, dist_fen)

dist_snu = [-1] * N
dist_snu[N-1] = 0
dfs(N-1, dist_snu)

fen = 0
for v in range(N):
    if dist_fen[v] <= dist_snu[v]:
        fen += 1
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')