CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")

MOD = 1000000007  # type: int


def cmb(n, r):
    r = min(r, n-r)
    if r < 0 or r > n:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])

    return result


def solve(n: int, a: "List[int]"):
    (m, _), = Counter(a).most_common(1)
    left = a.index(m)
    right = a.index(m, left+1)
    for i in range(1, n+2):
        print(((cmb(n+1, i)-cmb(n-right+left, i-1)) % MOD))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n+1)]  # type: "List[int]"
    solve(n, a)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):
    def __init__(self, N, mod):
        self.N = N
        self.MOD = mod
        self.fac = [0] * (N+1)
        self.finv = [0] * (N+1)
        self.inv = [0] * (N+1)
        self.cmb_init()

    def cmb_init(self):
        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, self.N+1):
            self.fac[i] = self.fac[i-1]*i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i]*(self.MOD//i) % self.MOD
            self.finv[i] = self.finv[i-1]*self.inv[i] % self.MOD

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k]*self.finv[n-k] % self.MOD) % self.MOD


def solve(n: int, a: "List[int]"):
    (m, _), = Counter(a).most_common(1)
    left = a.index(m)
    right = a.index(m, left+1)
    cmb = Combination(n+1, MOD)
    for i in range(1, n+2):
        print(((cmb(n+1, i)-cmb(n-right+left, i-1)) % MOD))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n+1)]  # type: "List[int]"
    solve(n, a)


if __name__ == '__main__':
    main()
# Original solution
def d_11(N, A):  # N:整数の種類, A:数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    # 重複した数のインデックスを求める
    from collections import Counter
    c = Counter(A).most_common(n=1)[0][0]  # 重複した整数の値を取得
    index = [i for i, x in enumerate(A) if x == c]  # 重複した整数のインデックス
    l = index[0] + 1
    r = index[1] + 1

    # フェルマーの小定理を用いてコンビネーションを効率よく計算
    factrial = [1] * (N + 2)  # 0~N+1までの階乗のテーブルを作る
    for k in range(1, N + 2):
        factrial[k] = (factrial[k - 1] * k) % M

    fact_inv = [1] * (N + 2)
    fact_inv[N + 1] = pow(factrial[N + 1], M - 2, M)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = ''
    for k in range(1, N + 2):
        ans += '{}\n'.format((nCr(N + 1, k, M) -
                              nCr((l - 1) + (N + 1 - r), k - 1, M)) % M)
    return ans[:-1]

N = int(eval(input()))
A = [int(i) for i in input().split()]
print((d_11(N, A)))

# Optimized solution
def d_11(MOD=10**9 + 7):
    from collections import Counter

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    # 重複した数のインデックスを求める
    c = Counter(A).most_common(n=1)[0][0]  # 重複した整数の値を取得
    index = [i for i, x in enumerate(A) if x == c]  # 重複した整数のインデックス
    left = index[0] + 1
    right = index[1] + 1

    comb = Combination(N + 1).combination
    ans = [(comb(N + 1, k) - comb(N - (right - left), k - 1)) % MOD for k in range(1, N + 2)]
    return '\n'.join(map(str, ans))

print((d_11()))
# Original solution
def d_11(MOD=10**9 + 7):
    from collections import Counter

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    # 重複した数のインデックスを求める
    c = Counter(A).most_common(n=1)[0][0]  # 重複した整数の値を取得
    index = [i for i, x in enumerate(A) if x == c]  # 重複した整数のインデックス
    left = index[0] + 1
    right = index[1] + 1

    comb = Combination(N + 1).combination
    ans = [(comb(N + 1, k) - comb(N - (right - left), k - 1)) % MOD for k in range(1, N + 2)]
    return '\n'.join(map(str, ans))

print((d_11()))

# Optimized solution
def d_11(MOD=10**9 + 7):
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    # 重複した数のインデックスを求める
    appeared = set()
    for k, a in enumerate(A):
        if a in appeared:
            left, right = A.index(a), k
            break
        appeared.add(a)

    c = Combination(N + 1).combination
    ans = [(c(N + 1, k) - c(N - (right - left), k - 1)) % MOD for k in range(1, N + 2)]
    return '\n'.join(map(str, ans))

print((d_11()))
# Original solution
# ABC143C - Slimes
from itertools import groupby


def main():
    N = int(eval(input()))
    S = input().rstrip()
    ans = len(tuple(groupby(S)))
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
def main():
    N = int(eval(input()))
    S = input().rstrip()
    S += "."
    ans, cur = 0, S[0]
    for s in S[1:]:
        if s != cur:
          ans += 1
          cur = s
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
f=input;f()
import itertools as it
print((len(list(it.groupby(f())))))

# Optimized solution
f=input;n=int(f());s=f()
print((1+sum(s[i]!=s[i-1] for i in range(1,n))))
# Original solution
# 2019-11-19 10:28:31(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    count = 1
    for i in range(n-1):
        if s[i+1] != s[i]:
            count += 1
    print(count)

if __name__ == "__main__":
    main()


# Optimized solution
import sys

n, s = sys.stdin.read().split()

def main():
    cnt = 0
    prev = '$'
    for c in s:
        if c == prev: continue
        cnt += 1
        prev = c
    print(cnt)

if __name__ ==  '__main__':
    main()
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    cnt = 0
    for i in range(1, n):
        if s[i] != s[i-1]:
            cnt += 1
    print((cnt+1))


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    cnt = 0
    for i in range(1, n):
        if s[i] != s[i-1]:
            cnt += 1
    print((cnt + 1))


if __name__ == '__main__':
    solve()
# Original solution
from itertools import groupby


def main():
    S = open(0).read().split()[1]
    print((len(list(groupby(S)))))


main()


# Optimized solution
from itertools import groupby


def main():
    S = open(0).read().split()[1]
    print((sum(1 for x in groupby(S))))


main()
# Original solution
n = int(eval(input()))
s = input().rstrip()


def rle(s):
    import itertools
    return list([(x[0], len(list(x[1]))) for x in itertools.groupby(s)])


print((len(rle(s))))

# Optimized solution
import itertools
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
s = rs()
print((len(list(itertools.groupby(s)))))
# Original solution
N = int(eval(input()))
S = input().strip()

after = S[0]
for i in range(1, N):
    if S[i] != S[i-1]:
        after += S[i]

print((len(after)))


# Optimized solution
N = int(eval(input()))
S = input().strip()

after = [S[0]]
for i in range(1, N):
    if S[i] != S[i-1]:
        after.append(S[i])

print((len(after)))
# Original solution
def gcd(a, b):
        while a != b:
                if a > b :
                        a -= b
                else:
                        b -= a
        return a

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

print((3*(N - gcd(N, X))))


# Optimized solution
def gcd(a, b):
        while a != b:
                if a == 0:
                        return b
                elif b == 0:
                        return a
                if a > b :
                        a %= b
                else:
                        b %= a
        return a

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

print((3*(N - gcd(N, X))))
# Original solution
N,X = list(map(int,input().split()))
x = X
y = N-X
res = N
while 1:
    if x==y:
        res += x
        break
    if x > y:
        x,y = y,x
    res += x*2
    y -= x
print(res)

# Optimized solution
N,X = list(map(int,input().split()))
x = X
y = N-X
if x<y:
    x,y = y,x
res = N
while y>0:
    x,y = y,x
    m = x*(y//x)
    res += m*2
    y -= m
res -= x
print(res)
# Original solution
n,x = list(map(int,input().split()))

ans = n
e = n-x
count = 0
while True:
    
    if x%e == 0:    
        ans += x//e*(e*2)-e
        break
    else:
        ans += (x//e)*e*2
    x,e = e,x%e
    count += 1
    
print(ans)

# Optimized solution
n,x = list(map(int,input().split()))
ans = n
e = n-x
while e > 0:
    if x%e == 0:    
        ans += x//e*(e*2)-e
    else:
        ans += (x//e)*e*2
    x,e = e,x%e    
print(ans)
# Original solution
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

N, K = list(map(int, sys.stdin.buffer.readline().split()))
a = K
b = N - K
c = 0
d = min(a, b)
while not a == b == c:
    a, b, c = sorted([a, b, c])
    if b == c and (b - a) % d == 0:
        a = b
    elif a == b:
        a += d
    else:
        d = b - a
        a += d * 2
print((a + b + c))


# Optimized solution
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

N, K = list(map(int, sys.stdin.buffer.readline().split()))

a = K
b = N - K
c = 0
d = min(a, b)
while not a == b == c:
    a, b, c = sorted([a, b, c])
    if a != b:
        d = b - a
    cnt = (c - b) // d
    b += d * cnt
    a += d * cnt + d
print((a + b + c))
# Original solution
n, x = list(map(int, input().split(' ')))

ans = n
c = [x, n-x]
while (c[0] != c[1]):
    ans += 2 * min(c)
    c = [min(c), max(c)-min(c)]
print((ans+c[0]))


# Optimized solution
def sub(a, b):
    if (a%b == 0):
        return a//b-1
    return a//b

def mod(a, b):
    if a%b==0:
        return b
    return a%b

n, x = list(map(int, input().split(' ')))
ans = n
c = [x, n-x]
while (c[0] != c[1]):
    c = [min(c), max(c)]
    ans += 2*sub(c[1], c[0])*c[0]
    c[1] = mod(c[1], c[0])
print((ans+c[0]))
# Original solution
N, X = list(map(int, input().split(" ")))

e_long = max(X, N-X)
e_short = N - e_long

total = N

while e_long != e_short and e_long > 0 and e_short > 0:
    total += e_short * 2
    e_long -= e_short
    if e_short > e_long:
        tmp = e_long
        e_long = e_short
        e_short = tmp

total += e_short

print(total)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N, X = list(map(int, input().split()))
    ans = N
    min_ = min(X, N-X)
    max_ = max(X, N-X)
    while min_ != 0:
        # print(max_, min_)
        ans += (max_ // min_) * 2 * min_
        tmp = max_ % min_
        max_ = min_
        min_ = tmp
    ans -= max_
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
N,X=list(map(int,input().split()))
A=N

X,N = sorted((X,N-X))
while N != X:
    A += 2*X
    X,N=sorted((X,N-X))
print((A+X))

# Optimized solution
N,X=list(map(int,input().split()))
A=N

X,N = sorted((X,N-X))
while N != X and X != 0:
    if N%X == 0:
        A += 2*(N//X-1)*X
        X,N=X,X
    else:
        A += 2*(N//X)*X
        X,N=sorted((X,N%X))
print((A+X))
# Original solution
# -*- coding: utf-8 -*-

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, X = MAP()

print(((N-gcd(N, X))*3))


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, X = MAP()

# 最初のN以外は、平行四辺形を小さくしていくと考える
def rec(a, b):
    a, b = min(a, b), max(a, b)
    if a == 0:
        # 最後に割り切れた時は半分でいいので減らす
        return -b
    # 同じだけ小さくする所はまとめてやる
    return a*2*(b//a) + rec(a, b%a)

print((N+rec(X, N-X)))
# Original solution
n, x = list(map(int, input().split()))

def func(a, b):
    res = 0
    while b > 0:
        c, d = divmod(a, b)
        res += 2 * b * c
        a = b
        b = d
    
    return res - a

print((n + func(x, n-x)))

# Optimized solution
n, x = list(map(int, input().split()))

def func(a, b):
    if a < b:
        a, b = b, a

    res = 0
    while b > 0:
        c, d = divmod(a, b)
        res += 2 * b * c
        a = b
        b = d
    
    return res - a

print((n + func(x, n-x)))
# Original solution
n, x = list(map(int,input().split()))

if n % 2 == 0 and n//2 == x:
    print((3 * x))
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x

ans = n
i = 0
f = False

while True:
    if yy >= xx:
        ans += 2 * xx
        yy -= xx

        if yy == 0:
            ans -= xx
            f = True
            break

    if xx > yy:
        ans += yy * 2
        xx -= yy

        if xx == 0:
            ans -= yy
            f = True
            break

print(ans)


# Optimized solution
n, x = list(map(int,input().split()))

if n % 2 == 0 and n//2 == x:
    print((3 * x))
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x


ans = n
i = 0

while True:
    
    if yy >= xx:
        ans += 2 * (yy // xx) * xx
        yy %= xx

        if yy == 0:
            ans -= xx
            break

        if yy < xx:
            tmp = xx
            xx = yy
            yy = tmp

print(ans)
# Original solution
n, x = list(map(int, input().split()))

def func(a, b):
    if a < b:
        if b%a == 0:
            return (b//a*2 - 1)*a
        else:
            q, mod = divmod(b,a)
            return 2*q*a + func(a, mod)
    elif a > b:
        if a%b == 0:
            return (a//b*2 - 1)*b
        else:
            q, mod = divmod(a,b)
            return 2*q*b + func(mod, b)
    else:
        return a

if x == n/2:
    print((3*x))
else:
    print((x+(n-x)+func(x,n-x)))

# Optimized solution
# coding:utf-8


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


n, x = inpl()


def func(a, b):
    if a < b:
        a, b = b, a
    if a == b:
        return a
    else:
        if a % b == 0:
            return (a // b * 2 - 1) * b
        else:
            q, mod = divmod(a, b)
            return 2 * q * b + func(b, mod)
            # return 2*b + func(a-b, b)#再帰回数が10000を超えるとエラー(20000000001, 4)など


if x == n / 2:
    print((3 * x))
else:
    print((n + func(x, n - x)))
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
ans += n

l1, l2 = min(n - x, x), max(n - x, x)
#while True:
#    if l1 == l2:
#        ans += l1
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
while True:
    if l2 % l1 == 0:
        ans += (l1 * ((l2 // l1) * 2 - 1))
        break
    else:
        ans += (l1 * 2)
        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
ans += n

l1, l2 = min(n - x, x), max(n - x, x)
#while True:
#    if l1 == l2:
#        ans += l1
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
#while True:
#    if l2 % l1 == 0:
#        ans += (l1 * ((l2 // l1) * 2 - 1))
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
while True:
    if l2 % l1 == 0:
        ans += (l1 * ((l2 // l1) * 2 - 1))
        break
    else:
        ans += (l1 * 2) * (l2 // l1)
        l1, l2 = l2 % l1, l1

print(ans)
# Original solution
import sys
import heapq as hp

class Edge:
    def __init__(self, end, cost):
        self.to = end
        self.cost = cost


class Dijkstra:
    def __init__(self, V):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self._inf = sys.maxsize
        self.dist = [self._inf for i in range(self._node)]

    def add_edge(self, st, ed, cost):
        self._graph[st].append(Edge(ed, cost))
    def solve(self, s):
        que = []
        self.dist[s] = 0
        hp.heappush(que, (0, s))
        while que:
            cur_cost, cur_vertex = hp.heappop(que)
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if cur_cost + e.cost < self.dist[e.to]:
                    self.dist[e.to] = cur_cost + e.cost
                    hp.heappush(que, (self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = list(map(int, input().split()))
    dk = Dijkstra(V)
    for i in range(E):
        s, t, d = list(map(int, input().split()))
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == sys.maxsize:
            print("INF")
        else:
            print(value)



# Optimized solution
import sys
from heapq import heappush, heappop


class Dijkstra:

    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, V):
        self._node = V
        self._graph = [[] for i in range(self._node)]
        self.inf = 10 ** 10
        self.dist = [self.inf for i in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = []
        self.dist[start] = 0
        heappush(que, (0, start))
        while que:
            cur_cost, cur_vertex = heappop(que)
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if cur_cost + e.cost < self.dist[e.to]:
                    self.dist[e.to] = cur_cost + e.cost
                    heappush(que, (self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = list(map(int, sys.stdin.readline().split()))
    dk = Dijkstra(V)
    for i in range(E):
        s, t, d = list(map(int, sys.stdin.readline().split()))
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            sys.stdout.writelines("INF\n")
        else:
            sys.stdout.writelines("%d\n" % value)