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

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

m_count = 0

while True:
    a_l[0] //= 2
    m_count += 1
    max_price = a_l[0]
    for j in range(1,n):
        if a_l[j] >= max_price:
            a_l[j] //2
            m_count += 1
            if m_count == m:
                break
        else:
            break
    a_l.sort(reverse=True)

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

m_count = 0
while True:
    max_price = a_l[0]//2
    for j in range(n):
        if a_l[j] >= max_price:
            a_l[j] //= 2
            m_count += 1
            if m_count == m:
                break
        else:
            break
        if m_count == m:
            break
    a_l.sort(reverse=True)
    if m_count == m:
        break

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class BIT():
    def __init__(self, n):
        """
        1-index
        sum -> i番目までの和
        add -> i番目にxを足す
        :param n:
        """
        self.n = n
        self.data = [0]*(n+1)
        self.each = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.each[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def __str__(self):
        return str(self.each)



def main():
    N, Q = NMI()
    C = [0]+NLI()
    querys = [[i]+NLI() for i in range(Q)]
    querys.sort(key=lambda x: x[2])
    ans = [0] * Q
    last_index = [-1] * (N+1)
    tree = BIT(N)
    idx = 1
    for query in querys:
        qi, ql, qr = query
        while idx <= N and idx <= qr:
            color = C[idx]
            if last_index[color] != -1:
                tree.add(last_index[color], -1)

            tree.add(idx, 1)
            last_index[color] = idx
            idx += 1

        ans[qi] = tree.sum(qr) - tree.sum(ql-1)

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class BIT():
    def __init__(self, n):
        """
        1-index
        sum -> i番目までの和
        add -> i番目にxを足す
        :param n:
        """
        self.n = n
        self.data = [0]*(n+1)
        self.each = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.each[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def __str__(self):
        return str(self.each)



def main():
    N, Q = NMI()
    C = [0]+NLI()
    d_querys = [[i]+NLI() for i in range(Q)]
    querys = defaultdict(list)
    for qi, ql, qr in d_querys:
        querys[qr].append((qi, ql))

    ans = [0] * Q
    last_index = [-1] * (N+1)
    index_dict = defaultdict(list)
    tree = BIT(N)

    for i, color in enumerate(C):
        if color == 0: continue
        idx = last_index[color]
        if idx != -1:
            index_dict[i].append((idx, i))
        last_index[color] = i
        tree.add(i, 1)

    for i in range(1, N+1):
        for idx, _ in index_dict[i]:
            tree.add(idx, -1)
        for qi, ql in querys[i]:
            ans[qi] = tree.sum(i) - tree.sum(ql-1)

    for a in ans:
        print(a)




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

import sys
import numpy as np

def main():
    n, w = map(int, input().split())
    a = np.array([list(map(int, x.split())) for x in sys.stdin.readlines()])
    dp = np.array([[0]*(w+1) for _ in range(n+1)])

    for i in range(n):
        for j in range(w+1):
            if j - a[i][0] >= 0:
                dp[i+1][j] = max(dp[i+1][j] , dp[i][j - a[i][0]] + a[i][1])

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    n, w = map(int, input().split())
    a = [list(map(int, x.split())) for x in sys.stdin.readlines()]
    dp = [[0]*(w+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(w+1):
            if j - a[i][0] >= 0:
                dp[i+1][j] = max(dp[i+1][j] , dp[i][j - a[i][0]] + a[i][1])

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

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

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()[::-1]
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

for i in range(N):
    c = S[i]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*(10**i) + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[N][5])



### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

s = [1]
for i in range(N):
  s.append((s[-1]*10)%13)

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*s[i] + j) % 13
            dp[i+1][amari] = (dp[i][j] + dp[i+1][amari]) % MOD

print(dp[N][5])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    n,x,y = map(int,input().split())
    ans = [0]*(n)
    E = [[] for i in range(n)]
    E[0].append(1)
    E[n-1].append(n-2)
    for i in range(1,n-1):
        E[i].append(i-1)
        E[i].append(i+1)
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    ans = [0]*(n)
    def search(x):
        d = [float("INF")]*n
        d[x] = 0
        q = deque([])
        q.append((x,0))
        while q:
            bef,l = q.pop()

            for nex in E[bef]:
                if d[nex] > l+1:
                    d[nex] = l+1
                    q.append((nex,l+1))
        
        d = d[x:]
        for j in range(n):
            ans[j] += d.count(j)
    for i in range(n-1):
        search(i)

    for i in ans[1:]:
        print(i)
if __name__ == "__main__":
    main()



### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n)

for i in range(1,n):
    for j in range(i+1,n+1):
        d = min(j-i,abs(x-i)+abs(y-j)+1)
        ans[d] += 1
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

N = int(input())
alist = list(map(int, input().split()))
min_x, max_x = min(alist), max(alist)
max_num = 0
for x in range(min_x, max_x + 1):
    if x in alist:
        num = len([xx for xx in alist if x -1 <= xx <= x + 1])
        max_num = max(max_num, num)
print(max_num)

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
### BUGGY CODE ###

n = int(input())
a=list(map(int,input().split()))
 
ans=1
 
for i in a:
    ans=ans*i
 
if ans>1000000000000000000:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

import sys

def main():
    n = int(input())
    a=sys.stdin.readline().rstrip().split()
    if '0' in a:
        print(0)
        return
    ans=1
 
    for i in a:
        ans=ans*int(i)
        if ans>1000000000000000000:
            print("-1")
            return
    else:
        print(ans)
main()
### BUGGY CODE ###

K, S = map(int,input().split())
from itertools import product
ans = 0
for x,y,z in product(range(K+1),repeat=3):
    if x + y + z == S:ans += 1
print(ans)


### FIXED CODE ###

from itertools import  product
K, S = map(int, input().split())
ans = 0
for x,y in product(range(K+1),repeat=2):
    z = S - x - y
    if 0 <= z <= K and x + y + z == S:
        ans += 1
print(ans)
### BUGGY CODE ###

mod = 10**9+7

n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]

dp = [0 for __ in range(1 << n)]
dp[0] = 1

for bit in range(1 << n):
    i = bin(bit).count("1")
    for j in range(n):
        if a[i-1][j] == 1 and (bit & 1 << j):
            dp[bit] += dp[bit ^ (1 << j)]
    dp[bit] %= mod

print(dp[2**n-1])


### FIXED CODE ###

mod = 10**9+7

n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]

dp = [-1 for __ in range(1 << n)]
dp[0] = 1


def dfs(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]


print(dfs(2**n-1, 0))
### BUGGY CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = 1.0e+9 + 7
for i in range(len(A)):
  A[i]= A[i]%mod_num
rest = 0
for i in range(N-1):
  for j in range(N-i-1):
    rest +=A[i]*A[i+j+1]
    if(rest>=mod_num):
    	rest=rest%mod_num

    
print(int(rest%mod_num))

### FIXED CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = int(1.0e+9 + 7)
rest = 0
temp = 0

for i in range(N-1):
  temp+=A[i]
  rest += temp*A[i+1]
  rest = rest%mod_num

print(int(rest%mod_num))
### BUGGY CODE ###

N,M,K=map(int,input().split())
O,S,T=10**9+7,N+M,6
for i in range(K):S*=N*M-i;T*=i+1
print(S*K*~-K*pow(T,O-2,O)%O)

### FIXED CODE ###

N,M,K=map(int,input().split())
O,S,T=10**9+7,N+M,6
for i in range(K):S=S*(N*M-i)%O;T=T*-~i%O
print(S*K*~-K*pow(T,O-2,O)%O)
### BUGGY CODE ###

# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()

    num = 0

    for i in range(1, N+1):
        y = math.floor(N/i)
        num += int((y*(y+1)*i)/2)

    print(num)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 幅優先探索（行きがけ）
import collections
import sys
import copy


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()

    num = 0

    for i in range(1, N+1):
        y = N//i
        num += int((y*(y+1)*i)/2)

    print(num)


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

n=int(input())
a=list(map(int, input().split()))
ans = 0
for i in a:
    cnt = a.count(i+1) + a.count(i) + a.count(i-1)
    ans = max(ans,cnt)
print(ans)

### FIXED CODE ###

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

import math
K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
           ans += math.gcd(math.gcd(i, j), k)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        a = math.gcd(i,j)
        for k in range(1, K+1):
           ans += math.gcd(a, k)
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import lil_matrix

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]

G = lil_matrix((N, N))

for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    G[i0, i1] = min(abs(x1 - x0), abs(y1 - y0))

mst = minimum_spanning_tree(G)
print(int(mst.sum()))

### FIXED CODE ###

import heapq

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]
G = [set() for _ in range(N)]

iXY.sort(key=lambda a: a[1])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

iXY.sort(key=lambda a: a[2])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)
### BUGGY CODE ###

N=int(input())
ans=1
for x in range(3,N+1):
    tmp=x-1
    for i in range(1,int(tmp**0.5)+1):
        if tmp%i==0:
            ans+=2
            if tmp//i ==i:
                ans-=1

print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for x in range(1,N):
  ans+=(N-1)//x
print(ans)
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    for j in range(N-i-1):
        ans += As[i]*As[j+i+1]

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


### FIXED CODE ###

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

sum = 0
for i in range(N):
    sum += As[i]
    sum %= 10**9+7

ans = 0
for i in range(N):
    sum -= As[i]
    ans += As[i]*sum
    ans %= 10**9+7

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

import sys
sys.setrecursionlimit(10**6)

# 入力
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

# メモ用のDPテーブル生成
dp = [float("inf") for i in range(N)]

# 初期値をセット
dp[0] = 0

# 足場iへたどり着く最小コストを返す
def rec(i):
    # ベースケース
    if i == 0:
        return 0
    
    # メモをチェック
    if dp[i] < float("inf"):
        return dp[i]
    
    # 足場iの最小コストの更新
    # for j in range(1, K+1):
        # if i - j >= 0:
            # 最小コストをメモ
            # dp[i] = min(dp[i], rec(i-j) + abs(H[i] - H[i-j]))
            
    dp[i] = min([rec(i-j) + abs(H[i] - H[i-j]) for j in range(1, K+1) if i - j >= 0])
    
    return dp[i]

print(rec(N-1))

### FIXED CODE ###

import numpy as np

# 入力
N, K = map(int, input().split())
H = np.array([int(i) for i in input().split()])

# ndarray型のDPテーブルを生成
dp = np.zeros(N, dtype=int)
# 初期値をセット
dp[0] = 0

# 各足場へたどり着く最小コストを調べる
for i in range(1, N):
    s = max(0, i-K)
    dp[i] = min(dp[s:i] + np.abs(H[i] - H[s:i])) # iより前の足場のコストに足す

print(dp[N-1])
### BUGGY CODE ###

from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if len(rest) == 0 or passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], list(rs))
print(smallest)


### FIXED CODE ###

from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)
### BUGGY CODE ###

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

ans = 1
for i in l:
  ans *= i
  
if ans > 1000000000000000000:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys

n = int(input())
l = [int(x) for x in input().split()]

ans = 1

if 0 in l:
    print(0)
    sys.exit()

for i in l:
  ans *= i
  if ans > 1000000000000000000:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

A = sorted(A)[::-1]

ans = 0
for i, a in enumerate(A):
    if i==0:
        first = a
    elif i==1:
        ans += first
        pre = [A[1], A[1]]
    else:
        ans += pre[0]
        pre = pre[1:]
        pre.append(a)
        pre.append(a)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

A = sorted(A)[::-1]

ans = 0
for i, a in enumerate(A):
    if i==0:
        ans += a
        itr = 2
        if itr >= N:
            break
    else:
        ans += a
        itr += 1
        if itr >= N:
            break
        ans += a
        itr += 1
        if itr >= N:
            break

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

import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

cost.sort(key = lambda x: x[0])

nn = -1
for i in range(1, n + 1):
    if nn < i:
        for j in cost:
            if j[1] >= i:
                ss = j[0]
                nn = j[1]
                break
    print(10**15-ss)

### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b=[]
for j in range(len(a)):
  b.append(a.count(a[j]))
c=int(b.count(max(b))/max(b))
d=[]
for k in range(c):
  d.append(a[b.index(max(b))])
  a.remove(d[k])
e=[]
for l in range(len(d)):
  e.append(min(d))
  d.remove(e[l])
for m in e:
  print(m)

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b={}
for j in range(len(a)):
  if a[j] in b:
    b[a[j]]+=1
  else:
    b[a[j]]=1
max_b=max(b.values())
c=[]
for k,l in b.items():
  if l==max_b:
    c.append(k)
c.sort()
for m in c:
  print(m)