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

from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,(0,source))
    heapq.heapify(queue)
    went = {n:0 for n in range(vertice)}

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break
        elif went[here]:
            continue
        can_go = link[here]

        #print(v,here,now_cost,not_went,queue)
        for nw in can_go:
            if went[nw]:
                continue
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went[here] = 1
    else:
        print("INF")

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

import sys
import itertools

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = []
for i in range(2, len(A)-1):
  B0 = B[0:i]
  B1 = [x - B[i-1] for x in B[i:len(A)]]
  s = B0[-1] // 2
  for j in range(1, len(B0)):
    if (B0[j] > s):
      c0 = abs(2 * B0[j-1] - B0[-1])
      c1 = abs(2 * B0[j] - B0[-1])
      j0 = j-1 if c0 < c1 else j
      break

  s = B1[-1] // 2
  for j in range(1, len(B1)):
    if (B1[j] > s):
      c0 = abs(2 * B1[j-1] - B1[-1])
      c1 = abs(2 * B1[j] - B1[-1])
      j1 = j-1 if c0 < c1 else j
      break

  c = [B0[j0], B0[-1] - B0[j0], B1[j1], B1[-1] - B1[j1]]
  cand.append(max(c) - min(c))

ans = min(cand)
print(ans)

### FIXED CODE ###

import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  if (j == 0):
    j0 = j
  else:
    c0 = abs(2 * B[j-1] - z)
    c1 = abs(2 * B[j] - z)
    j0 = j-1 if c0 < c1 else j

  z = B[-1]
  s = B[i-1] + (B[-1] - B[i-1]) // 2
  j = bisect.bisect_right(B, s)
  if (j == i):
    j1 = j
  else:
    c0 = abs(B[j-1] - B[i-1] - (B[-1] - B[j-1]))
    c1 = abs(B[j]   - B[i-1] - (B[-1] - B[j]  ))
    j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
n = 1
while n <= N:
    n *= 2

data = [0] * (2 * n - 1)

def update(k, a):
    k = k + n - 1
    # data[k] = a
    while k >= 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0

dp = [A[0]] + [0] * (N - 1)
update(H[0] - 1, A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(0, H[i] - 1) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i] - 1, dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (max(dp))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():  
    N=int(input())
    S=input()
    r,g,b=[],[],[]
    for i,s in enumerate(S):
        if s=="R":r.append(i)
        elif s=="B":b.append(i)
        else: g.append(i)
    #print(r,g,b)
    #RGBのリストが作れたので、このうち１個ずつとっていけば
    #<1>の条件を満たすことができる（ijkの順序が決まっていることから、
    #最後にこれらが<2>を満たすことを確認する？または、満たさないものを除く
    #<2> i<=j<=k　に対して　j-i = k-j でない
    #"この式を整理すると"k-j*2+i=0ではない:i+j+k=j*3ではない
    #逆にこの式を満たす（平均の関係になっているなら、jは必ず真ん中になる
    
    cnt=0
    for R in r:
        for G in g:
            for B in b:
                temp= R+G+B
                if temp==R*3 or temp==G*3 or temp == B*3:
                    cnt+=1
    print(len(r)*len(g)*len(b)-cnt)
        
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#%%code
def resolve():
    N=int(input())
    S=input()
    RGB=[0,0,0]
    subcnt=0
    for i,c in enumerate(S):
        if c=="R":RGB[0]+=1
        if c=="G":RGB[1]+=1
        if c=="B":RGB[2]+=1
            
        for j in range(i+1,N):
            s=S[j]
            k=j*2-i
            if k<N :
                x=S[k]
                if   x!=s and s!=c and x!=c :
                    #print(i,j,k)
                    
                    subcnt+=1
            else:break

    #print(RGB,subcnt)
    A=RGB[0]*RGB[1]*RGB[2]
    print(A-subcnt)
            
#%%submit!
resolve()
### BUGGY CODE ###

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
s=[[10**12]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if j==0:s[i][j]=a[i]
        else:s[i][j]=min(s[i][j-1],a[(i-j)%n])
ans=10**12
for j in xrange(n):
    tmp=x*j
    for i in xrange(n):
        tmp+=s[i][j]
    ans=min(ans,tmp)
print ans


### FIXED CODE ###

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
s=[[10**12]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if j==0:s[i][j]=a[i]
        else:s[i][j]=min(s[i][j-1],a[(i-j)%n])
ans=float("inf")
for j in xrange(n):
    tmp=x*j
    for i in xrange(n):
        tmp+=s[i][j]
    ans=min(ans,tmp)
print ans
### BUGGY CODE ###

from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

for _ in range(Q):
    p,x = map(int,input().split())
    c[p] += x

ans = defaultdict(int)
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

for i in range(1,N+1):
    if i<N:
        print(str(ans[i])+' ',end="")
    else:
        print(str(ans[i]))


### FIXED CODE ###

from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

for _ in range(Q):
    p,x = map(int,input().split())
    c[p] += x

ans = [0 for i in range(N)]
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v-1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

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

#!/usr/bin/env python3

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(K):
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(' '.join(map(str,A)))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M, L = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

graph = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == float('inf'):
            continue
        for j in range(N):
            if graph[k][j] == float('inf'):
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

cnt = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    cnt[i][i] = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if graph[i][j] <= L:
            cnt[i][j] = 1
            cnt[j][i] = 1

for k in range(N):
    for i in range(N):
        if cnt[i][k] == float('inf'):
            continue
        for j in range(N):
            if cnt[k][j] == float('inf'):
                continue
            cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j])

for s, t in X:
    if cnt[s - 1][t - 1] == float('inf'):
        print(-1)
    else:
        print(cnt[s - 1][t - 1] - 1)



### FIXED CODE ###

N, M, L = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

INF = 10 ** 9 + 6
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == INF:
            continue
        for j in range(N):
            if graph[k][j] == INF:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

cnt = [[INF] * N for _ in range(N)]

for i in range(N):
    cnt[i][i] = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if graph[i][j] <= L:
            cnt[i][j] = 1
            cnt[j][i] = 1

for k in range(N):
    for i in range(N):
        if cnt[i][k] == INF:
            continue
        for j in range(N):
            if cnt[k][j] == INF:
                continue
            cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j])

for s, t in X:
    if cnt[s - 1][t - 1] == INF:
        print(-1)
    else:
        print(cnt[s - 1][t - 1] - 1)
### BUGGY CODE ###

from collections import deque
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)

### FIXED CODE ###

from collections import deque
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)
### BUGGY CODE ###

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * 10**order)%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * 10**order)%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * 10**order)%13 ] %= MOD
 
print(dp[-1][5]%MOD)

### FIXED CODE ###

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)
### BUGGY CODE ###

MOD = 10**9+7

L=input()
N = len(L)
ans = 0
num = 0 # Lの先頭iケタにおける1の個数
cum_one_cnt = [0]*(N+1)
for i in range(N):
    length = N-i-1
    if L[i] == "1":
        ans += pow(3, length) * pow(2, num)
        num += 1 # 1を発見したので1つ加算

# 最後のパターンのみ特殊(フリーなケタがない)
ans += pow(2, num)
print(ans%MOD)

### FIXED CODE ###

MOD = 10**9+7

L=input()
N = len(L)
ans = 0
num = 0 # Lの先頭iケタにおける1の個数
cum_one_cnt = [0]*(N+1)
for i in range(N):
    length = N-i-1
    if L[i] == "1":
        ans += pow(3, length, MOD) * pow(2, num, MOD) % MOD
        ans %= MOD
        num += 1 # 1を発見したので1つ加算

# 最後のパターンのみ特殊(フリーなケタがない)
ans += pow(2, num, MOD)
print(ans%MOD)
### BUGGY CODE ###

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

points = []

p = 1
for i in range(k):
    p *= a[i]

points.append(p)
for i in range(n-k):
    p = p * a[i+k] // a[i]
    points.append(p)

for p,n in zip(points, points[1:]):
    if p < n:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for p,n in zip(a, a[k:]):
    if p < n:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
S = input()

cand = []

for i in range(N+1):
    st = '.'*i + '#'*(N-i)
    temp = 0
    for s, t in zip(S, st):
        if s != t:
            temp += 1
    cand.append(temp)
    
print(min(cand))

### FIXED CODE ###

N = int(input())
S = input()

cand = []
black = 0
white = 0

for s in S:
    if s == '.':
        white +=1
cand.append(white)
        
for s in S:
    if s == '#':
        black += 1
    else:
        white -= 1
    cand.append(black+white)

print(min(cand))
### BUGGY CODE ###

from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for k in range(w)] for l in range(h)]
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                visited[now[0]][now[1]] = True
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)):
                    if (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                        queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                if (now[1] <= (w - 2)):
                    if (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                        queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                if (1 <= now[0]):
                    if (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                        queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                if (1 <= now[1]):
                    if (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                        queue.put((now[0], (now[1] - 1), (now[2] + 1)))

print(ans)


### FIXED CODE ###

from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                    visited[now[0] + 1][now[1]] = True
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                    visited[now[0]][now[1] + 1] = True
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                    visited[now[0] - 1][now[1]] = True
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))
                    visited[now[0]][now[1] - 1] = True

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

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

max = 0

for i in range(100000 + 1):
  X = i

  new = [l for l in li if l == X or l == (X + 1) or l == (X - 1)]

  if max < len(new):
    max = len(new)

print(max)

### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v-1] += 1
    cnt[v+1] += 1
    
print(max(cnt))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
    num=sum(p[i:i+k])
    if ans<num:
        ans=num
print((ans+k)/2)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
num=[sum(p[0:k])]
def ap(num1):
    num.append(num1)
for i in range(n-k):
    ap(num[i]-p[i]+p[k+i])
print((max(num)+k)/2)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
s = 0
for i in range(N):
    for j in range(i+1,N):
        s += a[i]*a[j]
print(s%(pow(10,9)+7))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a_s = sum(a)
mod = 10**9+7
s = 0
for i in range(N-1):
    b = a[i]
    a_s -= b
    s += b*(a_s)
    s %= mod
print(s)
### BUGGY CODE ###

MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
ngs = [i in a_list for i in range(n)]
ngs.append(False)
for i in range(n):
    if ngs[i] and ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for ng in ngs:
    if ng:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(ngs)
# print(cnts)
print(ans % MOD)


### FIXED CODE ###

MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
is_ngs = [0] * (n + 2)
for a in a_list:
    is_ngs[a] = 1
for i in range(n):
    if is_ngs[i] and is_ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for i in range(n + 1):
    if is_ngs[i]:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(is_ngs)
# print(cnts)
print(ans % MOD)