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

n,m=map(int,input().split())
first=[]
second=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        first.append(bi)
    elif bi==n:
        second.append(ai)
    fset,sset=set(first),set(second)
if len(list(fset&sset))>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
check=[0]*n
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if check[bi-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[bi-1]+=1
    elif bi==n:
        if check[ai-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[ai-1]+=1
print(ans)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s) - 4):
    for j in range(i + 5, len(s) + 1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

s = input()[::-1]
p = 0
dp = [0] * 2019
dp[0] = 1
d = 1
for i in s:    
    p = (int(i) * d + (p)) % 2019
    dp[p] += 1
    d *= 10
    d = d % 2019
ans = 0
for i in dp:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

#2問目
# resultにそれぞれの深さの数を入れていく
N, M = map(int, input().split())
link = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)
visited = [-1 for i in range(N)]
Q = [0]
visited[0] = 0

#Qに要素がなくなるまで
while Q:
    #一番上の要素をpop
    v = Q.pop(0)
    for i in link[v]:
        if visited[i] == -1:
            visited[i] = visited[v] + 1
            Q.append(i)

if 0 <= visited[N-1] <= 2: print("POSSIBLE")
else: print("IMPOSSIBLE")

### FIXED CODE ###

#2問目
N, M = map(int, input().split())
link1 = [False for i in range(N+1)]
link2 = [False for i in range(N+1)]
flag = False
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        link1[B] = True
    elif B == N:
        link2[A] = True
for i in range(2, N):
    if link1[i] and link2[i]:
        print("POSSIBLE")
        flag = True
        break
if flag == False:
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

ans = []
for i in range(1, n+1):
    ans.append(ai.index(i)+1)
ans = map(str, ans)
print(" ".join(ans))    


### FIXED CODE ###

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

ans = [None]*n

for i in range(n):
    ans[ai[i]-1] = i+1

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

N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    dic[u-1][v-1]=w
    dic[v-1][u-1]=w
    M[u-1].append(v-1)
    M[v-1].append(u-1)


from collections import deque 
q = deque()
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i in M[e]:
        if used[i]==-1:
            C = (c+dic[i][e])%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)



### FIXED CODE ###

n = int(input())
from collections import deque
#隣接リストedge
edge = [[] for i in range(n)]
d = [-1] * n
#入力
for i in range(n-1):
    x,y,cost = map(int,input().split())
    #edge[x].append([cost,y])
    #edge[y].append([cost,x])
    x -=1
    y -=1
    cost %=2
    edge[x].append((cost,y))
    edge[y].append((cost,x))
q = deque()
q.append(0)
d[0] =0
while q:
    t = q.popleft()
    for s in edge[t]:
        if d[s[1]] == -1:
            d[s[1]] = d[t] + s[0]
            q.append(s[1])
for i in d:
    print(i%2)
### BUGGY CODE ###

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

count = 0

while count < K:
    if A > 0:
        A -= 1
        count += 1
        continue
        
    elif B > 0:
        B -= 1
        count += 1
        continue
        
    else:
        count += 1
        continue
print(A, B)

### FIXED CODE ###

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

if A > K:
    print(A-K, B)
if A <= K < A + B:
    print(0, A+B-K)
if A + B <= K:
    print(0, 0)
### BUGGY CODE ###

import sys

L,R = map(int, input().split())

if L - R >= 3000:
  print(0)
  sys.exit()

m = 10**9

for i in range(L, R+1):
  for n in range(i+1, R+1):
    s = i * n % 2019

    if m > s:
      m = s

print(m)

### FIXED CODE ###

import sys

L,R = map(int, input().split())

if R - L >= 2020:
  print(0)
  sys.exit()

m = 10**9

for i in range(L, R+1):
  for n in range(i+1, R+1):
    s = i * n % 2019

    if m > s:
      m = s

print(m)
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = [(A[0], 0), (A[k], k)]

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k
        dp[next_k] = list(sorted(set(dp[next_k] + dp[k])))[-2:]
    # for d in digits:
    #     if k & d == 0:
    #         dp[k | d] = list(sorted(set(dp[k | d] + dp[k])))[-2:]

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

def solve(n, xs):

    ans = 0
    for i in range(n):
        for j in range(i,n):
            if abs(i-j) == xs[i] + xs[j]:
                ans +=1

    return ans
if __name__ == "__main__":
    n = int(input())
    xs = [int(i) for i in input().split()]
    print(solve(n, xs))


### FIXED CODE ###

def solve(n, xs):

    ans = 0
    tmp = {}
    for i in range(n-1, -1, -1):
        l = i+1 + xs[i]
        r = i+1 - xs[i]

        if l in tmp:
            ans += tmp[l]

        if r in tmp:
            tmp[r] += 1
        else:
            tmp[r] = 1

    return ans
if __name__ == "__main__":
    n = int(input())
    xs = [int(i) for i in input().split()]
    print(solve(n, xs))
### BUGGY CODE ###

nn, kk = list(map(int,input().split()))
pp = list(map(int,input().split()))

expectation = [0]*(nn-kk+1)

for i in range(nn-kk+1):
    for j in range(kk):
        expectation[i] += pp[i+j]

print((max(expectation)+kk)/2)


### FIXED CODE ###

nn, kk = list(map(int,input().split()))
pp = list(map(int,input().split()))

expectation = [0]*(nn-kk+1)
expectation[0] = sum(pp[0:kk])

for i in range(1,nn-kk+1):
    expectation[i] = expectation[i-1] - pp[i-1] + pp[i+kk-1]

print((max(expectation)+kk)/2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect

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

B = [0 for _ in range(N)]
for i in A:
    B[i-1] += 1

F = []
for i in range(1,N+1):
    f = 0
    for j in range(N):
        f += min(B[j],i)
    f = f / i
    F.append(f)
F.sort()

for k in range(N):
    x = bisect.bisect_left(F,k+1)
    print(N-x)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from itertools import accumulate

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

B = list(Counter(A).values())

C = [0] * N 
for i in B:
    C[i-1] += 1

F = list(accumulate(C))

S = [0] * N
f = [0] * N
S[0] = f[0] = sum(C) 
for i in range(2, N+1):
    S[i-1] = (S[i-2] + C[i-1] + S[0] - F[i-1] ) 
    f[i-1] = S[i-1] / i

f.sort()
n = 0     
K = 1
    
while K != N+1:
    if K <= f[n]:
        print(N-n)
        K += 1
    else:
        n += 1
    if n == N:
        for i in range(N-K+1):
            print(0)
        K = N+1
### BUGGY CODE ###

N = int(input())
a = []

# 二つの掛け算の組み合わせを列挙
for n in range(1, int(N/2) + 1):
  if N % n == 0:
    a.append( int(n + N/n) )

# その中で一番足した数が少ないものを選択する
print(min(a) - 2)


### FIXED CODE ###

import math

N = int(input())

# 証明できないけど、真ん中の方の数字の方が数を足すと小さい値になると思う。
for n in reversed(range(1, int(math.sqrt(N)) + 1)):
  if N % n == 0:
    a = int(n + N/n)
    break


print(a - 2)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ls = set(l)

for i in range(1,n+1):
  if i in ls:
    print(l.count(i))
  else:
    print(0)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans =[0]*n
for i in l:
  ans[i-1] +=1
for i in ans:
  print(i)
### BUGGY CODE ###

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

bc2 = sum([[c]*b for b,c in bc],[])
a.extend(sorted(bc2)[-n:])
print(sum(sorted(a,reverse=True)[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ 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 ###

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

num_counts = {}
if len(set(num_lists)) <= k:
  ans = 0
else:
  for i in set(num_lists):
    num_counts[i] = num_lists.count(i)
  numbers = list(num_counts.values())
  numbers.sort()
  ans = 0
  for i in range(len(set(num_lists)) - k):
    ans += numbers[i]

print(ans)

### FIXED CODE ###

from collections import Counter

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

num_counts = dict()
length = len(set(num_lists))
ans = 0

if length > k:
  d = Counter()
  d.update(num_lists)
  count_sorted = list(d.values())
  count_sorted.sort()
  for i in range(length - k):
    ans += count_sorted[i]

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

s = input()
l = len(s)
MOD = 10**9+7
dp = [[0]*13 for _ in range(100005)]
dp[0][0] = 1
for i in range(l):

    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for r in range(13):
            dp[i+1][(10*r+j)%13] += dp[i][r]
    for k in range(13):
        dp[i+1][k] %= MOD
print(dp[l][5])

### FIXED CODE ###

s = input()
l = len(s)
MOD = 10**9+7
dp = [[0]*13 for _ in range(100005)]
dp[0][0] = 1
for i in range(l):

    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for r in range(13):
            dp[i+1][(10*r+j)%13] += dp[i][r]
    for k in range(13):
        dp[i+1][k] %= MOD
print(dp[l][5])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
is_root = [False] + [True] * N
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        parent[v] = u
        queue.append(v)
for i in range(1, N+1):
    print(parent[i])


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
is_root = [False] + [True] * N
par_count = [0] * (N+1)
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    par_count[B] += 1
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        if par_count[v] > 1:
            par_count[v] -= 1
        else:
            parent[v] = u
            queue.append(v)
for i in range(1, N+1):
    print(parent[i])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
m=10**9+7
s=0
for i in range(n-1):
    s+=l[i]*sum(l[i+1:])
print(s%m)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
a=sum(l[1:])
m=10**9+7
s=0
for v,u in zip(l[:-1],l[1:]):
    s+=v*a
    a-=u
print(s%m)
### BUGGY CODE ###

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

check = dict()
def get_pattern2(i, j):
    a = s[i]
    b = s[j]
    total = 0
    check_str = ""
    if a == "R" or b == "R":
        check_str += "R"
    if a == "G" or b == "G":
        check_str += "G"
    if a == "B" or b == "B":
        check_str += "B"

    for k in range(j+1, n):
        if check_str+str(k) in check:
            total += check[check_str+str(k)]
            break
        if a != s[k] and b != s[k]:
            total += 1
    check[check_str+str(j+1)] = total
    return total

def get_pattern(i):
    a = s[i]
    total = 0
    for j in range(i+1, n):
        if a+str(j) in check:
            total += check[a+str(j)]
            break
        if a != s[j]:
            total += get_pattern2(i, j)
    check[a+str(i+1)] = total

    # k-j = i-jなものをぬく
    for j in range(i+1, n):
        k = j + j - i
        if k >= n:
            break
        if a != s[k] and s[j] != s[k] and a != s[j]:
            total -= 1

    return total

total = 0
for i in range(n-1, -1, -1):
    total += get_pattern(i)
print(total)


### FIXED CODE ###

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

check = dict()
def get_pattern2(i, j):
    a = s[i]
    b = s[j]
    total = 0
    check_str = ""
    if a == "R" or b == "R":
        check_str += "R"
    if a == "G" or b == "G":
        check_str += "G"
    if a == "B" or b == "B":
        check_str += "B"

    for k in range(j+1, n):
        if check_str+str(k) in check:
            total += check[check_str+str(k)]
            break
        if a != s[k] and b != s[k]:
            total += 1
    check[check_str+str(j+1)] = total
    return total

def get_pattern(i):
    a = s[i]
    total = 0
    for j in range(i+1, n):
        if a+str(j) in check:
            total += check[a+str(j)]
            break
        if a != s[j]:
            total += get_pattern2(i, j)
    check[a+str(i+1)] = total

    # k-j = i-jなものをぬく
    for j in range(i+1, n):
        k = j + j - i
        if k >= n:
            break
        if a != s[k] and s[j] != s[k] and a != s[j]:
            total -= 1
    return total

total = 0
for i in range(n-1, -1, -1):
    total += get_pattern(i)
print(total)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import sys
limit = 10 ** 18
if 0 in a:
    print(0)
    sys.exit()
else:
    ans = 1
    for i in range(n):
        ans *= a[i]
        if ans > limit:
            print(-1)
            sys.exit()
    print(ans)
### BUGGY CODE ###

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

sums = [[None for j in range(N-i)] for i in range(N)]

for i in range(N):
    for j in range(N-i):
        if j == 0:
            sums[i][j] = A[i]
        else:
            sums[i][j] = sums[i][j-1] + A[j+i]

count = 0
for line in sums:
    count += line.count(0)
    
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
sums_dic = {}
a = sum(A)
sums_dic[a] = 1

for n in range(1,N):
    a -= A[n-1]
    sums_dic[a] = sums_dic.setdefault(a, 0) + 1 

count = 0
for key, value in sums_dic.items():
    if key == 0:
        count += value
    
    if value >= 2:
        count += value * (value - 1) // 2
    
print(count)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        bb=n-(i*r+j*g)
        s=bb+i*r+j*g
        if bb<0:
            continue
        if s==n and bb%b==0:
            cnt+=1
        if j*g>n or i*r>n:break
    if i*r>n:break
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        bb=n-(i*r+j*g)
        s=bb+i*r+j*g
        if bb<0:
            continue
        if s==n and bb%b==0:
            cnt+=1
        if j*g>n or i*r>n or s-bb>n:break
    if i*r>n:break
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 1000000007

C = [[0 for _ in range(4005)] for _ in range(4005)]
C[0][0] = 1
for i in range(4000):
  for j in range(4000):
    C[i + 1][j] += C[i][j]
    C[i + 1][j + 1] += C[i][j]

def comb(n, k):
  return C[n][k]

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 1000000007

fact = [1]
for i in range(1, N):
  fact.append(fact[-1] * i)

def comb(n, k):
  return (fact[n] // (fact[n - k] * fact[k])) % MOD

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return 0
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = 0
for i in range(n):
    for j in range(1,n - i):
        b += a[i]*a[i + j]
       

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


### FIXED CODE ###

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

mod = 10 ** 9 + 7
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

lcm_A = A[0]
for i in range(1, N):
    lcm_A = lcm_A * A[i] // gcd(lcm_A, A[i])

ans = 0
for i in range(N):
    ans += lcm_A // A[i]

print(ans % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

lcm_A = A[0]
for i in range(1, N):
    lcm_A = lcm_A * A[i] // gcd(lcm_A, A[i])

ans = 0
for i in range(N):
    ans += lcm_A // A[i]

print(ans % mod)
### BUGGY CODE ###

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

def main():
    def checkABC(x):
        if s[x]=='A' and s[x+1]=='B' and s[x+2]=='C':
            s[x],s[x+1],s[x+2]='B','C','A'
            return True
        else:
            return False
    
    s=list(input())
    N=len(s)
    i=0
    ans=0
    if N>=3:
        while True:
            if checkABC(i) == True:
                if i!=0 and s[i-1]=='A':
                    i-=2
                else:
                    i+=1
                ans+=1
            while True:
                i+=1
                if i >= N-2:
                    print(ans)
                    exit()
                if s[i] == 'A':
                    break
    else:
        print(ans)
        
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    ans=0
    c=0
    for i in range(N):
        if s2[i]=='A':
            c+=1
        elif c!=0 and s2[i]=='D':
            ans+=c
        else:
            c=0
    print(ans)

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

import itertools

n=int(input())

p=list(i+1 for i in range(n))
max=0
now=0
p1=list(itertools.permutations(p))

for p2 in p1:
  c=0
  now=0
  for l in p2:
    c+=1
    now += c % l
  if max<now:
    max=now
print(max)

### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

n = inp()
print(int((n-1)*n//2))

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)
### BUGGY CODE ###

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

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

before = 1

for _ in range(K):
    target_index = portals[before]
    before = target_index

print(before)


### FIXED CODE ###

N, K = map(int, input().split())
portals = [0] + list(map(int, input().split()))

visitTowns = list()
visitTimes = [0 for _ in range(N + 1)]

curTown = 1
timeBackTo = 0

curTime = 0
while True:
    if visitTimes[curTown] > 0:
        timeBackTo = visitTimes[curTown]
        break

    visitTowns.append(curTown)
    visitTimes[curTown] = curTime

    # teleport
    curTown = portals[curTown]

    curTime += 1

nonLoopCount = timeBackTo
loopSpan = len(visitTowns) - nonLoopCount

if K <= nonLoopCount:
    print(visitTowns[K])
    exit()

rem = (K - nonLoopCount) % loopSpan
print(visitTowns[nonLoopCount + rem])
### BUGGY CODE ###

from heapq import heapify,heappop,heappush
N,M,s,t=map(int,input().split())
Graph1=[set() for i in range(N)]
Graph2=[set() for i in range(N)]
inf=float("inf")
for i in range(M):
  u,v,a,b=map(int,input().split())
  Graph1[u-1].add((a,v-1))
  Graph1[v-1].add((a,u-1))
  Graph2[u-1].add((b,v-1))
  Graph2[v-1].add((b,u-1))
  
def dijkstra(s,n,links):
  cost=[inf]*n
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    for c,p in links[hp]:
      if c+hc<=cost[p]:
        cost[p]=c+hc
        heappush(heap,(cost[p],p))
  return cost
  

money=[0]*N
cost1=dijkstra(s-1,N,Graph1)
cost2=dijkstra(t-1,N,Graph2)

ans=[0]*N
a=inf
for i in range(N)[::-1]:
  a=min(a,cost1[i]+cost2[i])
  ans[i]=10**15-a
for i in ans:
  print(i)

### FIXED CODE ###

from heapq import heapify,heappop,heappush
N,M,s,t=map(int,input().split())
Graph1=[set() for i in range(N)]
Graph2=[set() for i in range(N)]
inf=float("inf")
for i in range(M):
  u,v,a,b=map(int,input().split())
  Graph1[u-1].add((a,v-1))
  Graph1[v-1].add((a,u-1))
  Graph2[u-1].add((b,v-1))
  Graph2[v-1].add((b,u-1))
  
def dijkstra(s,n,links):
  cost=[inf]*n
  visited=[False]*n
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if not visited[hp]:
      visited[hp]=True
      for c,p in links[hp]:
        if not visited[p]:
          if c+hc<=cost[p]:
            cost[p]=c+hc
            heappush(heap,(cost[p],p))
  return cost
 
cost1=dijkstra(s-1,N,Graph1)
cost2=dijkstra(t-1,N,Graph2)

ans=[0]*N
a=inf
for i in range(N)[::-1]:
  a=min(a,cost1[i]+cost2[i])
  ans[i]=10**15-a
for i in ans:
  print(i)