Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03165 (python)

Fixed submission:
# dpF - LCS
def main():
    S, T = tuple(input().rstrip() for _ in range(2))
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            n -= 1
            m -= 1
            ans += [S[n]]
    print(*ans[::-1], sep="")


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def get_lcs(S: str, T: str):
    N, M = len(S), len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    reversed_lcs = ""
    while N and M:
        if S[N - 1] == T[M - 1]:
            N -= 1
            M -= 1
            reversed_lcs += S[N]
        if dp[N - 1][M] > dp[N][M - 1]:
            N -= 1
        else:
            M -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()
Problem p03212 (python)

Fixed submission:
# ABC114C - 755
def shichi_go_san(s="0"):
    if int(s) > n:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in "753") else 0
    for c in "753":
        ret += shichi_go_san(s + c)
    return ret


n = int(input())
print(shichi_go_san())

Buggy submission (verdict: Runtime Error):
# ABC114C - 755
n = input()
digit = len(n)
ans = 0
for i in range(1, digit):
    ans += len([i for i in itertools.product("357", repeat=i) if len(set(i)) == 3])
tup = tuple(i for i in n)
lst = [i for i in itertools.product("357", repeat=digit) if len(set(i)) == 3] + [tup]
lst.sort()
ans += lst.index(tup)
print(ans)
Problem p03231 (python)

Fixed submission:
# AGC028
from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    l = n // gcd(n, m) * m
    x = {}
    for i in range(n):  # place S in x
        j = (l // n) * i
        x[j] = S[i]
    for i in range(m):  # check T adapts to x or not
        j = (l // m) * i
        if j in x and x[j] != T[i]:
            print(-1)
            break
    else:
        print(l)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# AGC028
from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    l = n // gcd(n, m) * m
    x = [""] * l
    for i in range(n):  # place S in x
        j = (l // n) * i
        x[j] = S[i]

    for i in range(m):  # check T adapts to x or not
        j = (l // m) * i
        if x[j] not in ("", T[i]):
            print(-1)
            break
    else:
        print(l)


if __name__ == "__main__":
    main()
Problem p03238 (python)

Fixed submission:
# ABC112A - Programming Education
n = int(input())
if n == 1:
    print("Hello World")
else:
    a, b = list(map(int, [input().rstrip() for _ in range(2)]))
    print(a + b)

Buggy submission (verdict: Runtime Error):
# ABC112A - Programming Education
def main():
    N, A, B = map(int, open(0).read().split())
    flg = N == 1
    print("Hello World" if flg else A + B)


if __name__ == "__main__":
    main()
Problem p03254 (python)

Fixed submission:
# AGC027A - Candy Distribution Again
# greedy algorithm
from itertools import accumulate


def main():
    # maximize the number of proper distribution -> begin with small values
    n, x = tuple(map(int, input().rstrip().split()))
    A = sorted(map(int, input().rstrip().split()))
    ac = list(accumulate(A))
    if ac[-1] < x:
        ans = n - 1
    else:
        ans = sum(i <= x for i in ac)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# AGC027A - Candy Distribution Again
# greedy algorithm
from itertools import accumulate as acc


def main():
    # maximize the number of proper distribution -> begin with small values
    N, X, *A = map(int, open(0).read().split())
    A.sort()
    ac = list(acc(A))
    if ac[-1] < x:  # the last one receives more than expected -> ans - 1
        ans = n - 1
    else:
        ans = sum(i <= x for i in ac)
    print(ans)


if __name__ == "__main__":
    main()
Problem p03262 (python)

Fixed submission:
# ABC109C - Skip
def gcd(a, b):
    while a:
        a, b = b % a, a
    return b
        

n, x = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
d = abs(x - lst[0])
for i in range(n):
    dif = abs(x - lst[i])
    if dif % d == 0:
        continue
    d = gcd(d, dif)
print(d)

Buggy submission (verdict: Runtime Error):
# ABC109C - Skip
from math import gcd

n, x = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
d = abs(x - lst[0])
for i in range(n):
    dif = abs(x - lst[i])
    if dif % d == 0:
        continue
    d = gcd(d, dif)
print(d)

Buggy submission (verdict: Runtime Error):
# ABC109C - Skip
from math import gcd

n, x = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
d = abs(x - lst[0])
for i in range(n):
    dif = abs(x - lst[i])
    if dif % d == 0:
        continue
    else:
        d = gcd(d, dif)
print(d)
Problem p03263 (python)

Fixed submission:
# ABC109D - Make Them Even
import sys
input = sys.stdin.readline


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    A = list(
        list(map(lambda x: int(x) % 2, input().rstrip().split())) for _ in range(H)
    )
    ans = []
    # move left to right
    for i in range(H):
        for j in range(W - 1):
            if A[i][j]:
                A[i][j] ^= 1
                A[i][j + 1] ^= 1
                ans += [(i + 1, j + 1, i + 1, j + 2)]
    # move up to down
    for i in range(H - 1):
        if A[i][W - 1]:
            A[i][W - 1] ^= 1
            A[i + 1][W - 1] ^= 1
            ans += [(i + 1, W, i + 2, W)]
    print(len(ans))
    for i in ans:
        print(*i)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC109D - Make Them Even
import sys
input = sys.stdin.readline


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    A = list(
        list(map(lambda x: int(x) % 2, input().rstrip().split())) for _ in range(H)
    )
    ans = []
    # move left to right
    for i in range(H):
        for j in range(W - 1):
            if A[i][j]:
                A[i][j] ^= 1
                A[i][j + 1] ^= 1
                ans += [(i + 1, j + 1, i + 1, j + 2)]
    for i in range(H - 1):
        if A[i][W]:
            A[i][W] ^= 1
            A[i + 1][W] ^= 1
            ans += [(i + 1, W + 1, i + 2, W + 1)]
    print(len(ans))
    for i in ans:
        print(*i)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC109D - Make Them Even (WA)
def main():
    H, W = tuple(map(int, input().split()))
    A = list(list(map(int, input().split())) for _ in range(H))
    ans = []
    # assume a single stroke
    for i in range(H):
        if i % 2 == 0:
            for j in range(W):
                if (i, j) == (H - 1, W - 1):
                    continue
                if A[i][j] % 2:
                    A[i][j] -= 1
                    if j + 1 != W:
                        A[i][j + 1] += 1
                        ans += [(i, j, i, j + 1)]
                    else:
                        A[i + 1][j] += 1
                        ans += [(i, j, i + 1, j)]
        else:
            for j in range(W, -1, -1):
                if (i, j) == (H - 1, W - 1):
                    continue
                if A[i][j] % 2:
                    A[i][j] -= 1
                    if j != 0:
                        A[i][j - 1] += 1
                        ans += [(i, j, i, j - 1)]
                    else:
                        A[i + 1][j] += 1
                        ans += [(i, j, i + 1, j)]
    print(len(ans))
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()
Problem p03274 (python)

Fixed submission:
# ABC107C - Candles (ARC101C)
def main():
    n, k = tuple(map(int, input().rstrip().split()))
    x = tuple(map(int, input().rstrip().split()))
    ans = float("inf")
    for i in range(n - k + 1):
        a, b = x[i], x[i + k - 1]
        if a < b < 0 or 0 < a < b:
            ans = min(ans, max(abs(a), abs(b)))
        else:
            ans = min(ans, max(abs(a), abs(b)) + min(abs(a), abs(b)) * 2)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC107C - Candles (ARC101C)
def main():
    N, K, *X = map(int, open(0).read().split())
    ans = float("inf")
    for l, r in zip(X, X[k - 1 :]):
        ans = min(ans, r - l + min(abs(l), abs(r)))
    print(ans)


if __name__ == "__main__":
    main()
Problem p03288 (python)

Fixed submission:
# ABC104A - Rated for Me
r = int(input())
if r < 1200:
    print("ABC")
elif 1200 <= r < 2800:
    print("ARC")
else:
    print("AGC")

Buggy submission (verdict: Runtime Error):
# ABC104A - Rated for Me
r = list(map(int, input().rstrip().split()))
if r < 1200:
    print("ABC")
elif 1200 <= r < 2800:
    print("ARC")
else:
    print("AGC")
Problem p03289 (python)

Fixed submission:
# ABC104B - AcCepted
s = input().rstrip()
if (
    s[0] == "A"
    and s[2:-1].count("C") == 1
    and s.replace("A", "").replace("C", "").islower()
):
    print("AC")
else:
    print("WA")

Buggy submission (verdict: Runtime Error):
# ABC104B - AcCepted
s = input().rstrip()
if (
    s[0] == "A"
    and s[2:-1].count("C") == 1
    and s.translate(str.maketrans({"A": None, "C": None}).islower()
):
    print("AC")
else:
    print("WA")
Problem p03316 (python)

Fixed submission:
# ABCB - Digit Sums
n = int(input())
sn = sum(list(map(int, list(str(n)))))
print("Yes" if n % sn == 0 else "No")

Buggy submission (verdict: Runtime Error):
# ABCB - Digit Sums
n = int(input())
sn = 0
for i in range(len(str(n))):
    n_temp = n
    sn += n_temp % 10
    n_temp //= 10
print("Yes" if n % sn == 0 else "No")

Buggy submission (verdict: Runtime Error):
# ABCB - Digit Sums
n = int(input())
sn = 0
for i in range(len(str(n))):
    n_temp = 0
    sn += n_temp % 10
    n_temp //= 10
print("Yes" if n % sn == 0 else "No")

Buggy submission (verdict: Runtime Error):
# ABCB - Digit Sums
n = int(input())
sn = 0
for i in range(len(str(n))):
    sn += n % 10
    s //= 10
print("Yes" if n % sn == 0 else "No")

Buggy submission (verdict: Runtime Error):
# ABCB - Digit Sums
n = int(input())
sn = 0
for i in range(len(str(n))):
    sn += n % 10
print("Yes" if n % sn == 0 else "No")
Problem p03352 (python)

Fixed submission:
# ABC097B - Exponential
x = int(input())
lst = []

for i in range(1, 32):
    for j in range(2, 10):
        if i ** j == x:
            print(x)
            exit()
        elif i ** j < x and i ** j not in lst:
            lst.append(i ** j)
        elif i ** j > x:
            break
            
lst.append(x)
lst = sorted(lst)

print(lst[lst.index(x) - 1])

Buggy submission (verdict: Runtime Error):
# ABC097B - Exponential
x = int(input())
lst = []

for i in range(1, 32):
    for j in range(1, 10):
        if i ** j == x:
            print(x)
            exit()
        elif i ** j < x and i ** j not in lst:
            lst.append(i ** j)
        elif i ** j > x:
            break
            
lst.append(x)
lst = sorted(lst)

print(lst[lst.index(1000) - 1])
Problem p03354 (python)

Fixed submission:
# ARC097D - Equals (ABC097D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    seen[v] = 1  # make vertex v searched
    group[v] = color
    for u in G[v]:  # search vertices available from v recursively
        if not seen[u]:  # skip if already searched
            dfs(u, color)


def main():
    # check i and Pi are connected components or not
    global G, seen, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # construct a graph (1-idx)
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    seen, group = [0] * (N + 1), [0] * (N + 1)
    color = 1
    for i in range(1, N + 1):  # connected components have the same color
        if not seen[i]:
            dfs(i, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC097D - Equals (ARC097D)
"""
Union-Find: O(α(N))

Verified:
    https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A
    https://judge.yosupo.jp/problem/unionfind
"""


class UnionFind:
    __slots__ = ["_data_size", "_first_index", "_parents"]

    def __init__(self, data_size: int, is_zero_indexed: bool = True) -> None:
        self._data_size = data_size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (data_size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x


def main():
    N, _, *PXY = open(0).read().split()
    P, XY = PXY[:N], PXY[N:]
    uf = UnionFind(N, is_zero_indexed=False)
    for x, y in zip(*[iter(XY)] * 2):
        uf.unite(x, y)
    ans = sum(uf.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()
Problem p03360 (python)

Fixed submission:
# ABC096B - Maximum Sum
a, b, c = sorted(list(map(int, input().rstrip().split())), reverse=True)
k = int(input())
if k == 1:
    print(a * 2 + b + c)
else:
    for i in range(1, k + 1):
        A = a * 2 + b + c
        B = a + b * 2 ++ c
        C = a + b + c * 2
        if max(A, B, C) == A:
            a *= 2
        elif max(A, B, C) == B:
            b *= 2
        else:
            c *= 2
    print(a + b + c)

Buggy submission (verdict: Runtime Error):
# ABC096B - Maximum Sum
a, b, c = sorted(list(map(int, input().rstrip().split())), reverse=True)
k = int(input())
if k == 1:
    print(a * 2 + b + c)
else:
    for i in range(1, k + 1):
        A = a * 2 + b + c
        B = a + b * 2 ++ c
        C = a + b + c * 2
        if max(A, B, C) == A:
            a *= 2
        elif max(A, B, C) == B:
            b *= 2
        else:
            c *= 2
	print(a + b + c)
Problem p03378 (python)

Fixed submission:
# ABC094B - Toll Gates
n, m, x = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
lst.append(x)
lst = sorted(lst)
print(min(len(lst[: lst.index(x)]), len(lst[lst.index(x) + 1 :])))

Buggy submission (verdict: Runtime Error):
# ABC094B - Toll Gates
from bisect import bisect_left


def main():
    N, M, X, *A = map(int, open(0).read().split())
    A.sort()
    cur = bisect_left(A, x)
    ans = min(cur, M - cur)
    print(ans)


if __name__ == "__main__":
    main()
Problem p03380 (python)

Fixed submission:
# ABC094D - Binomial Coefficients (ARC095D)
def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    n = max(A)
    r = A[0] if A[0] != n else A[1]
    cur = r * (n - r)
    for i in A:
        if i != n:
            x = i * (n - i)
            if x > cur:
                r, cur = i, x
    print(n, r)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC094D - Binomial Coefficients (ARC095D)
from bisect import bisect_left as bs


def main():
    # pascal's triangle := mid area (nCn/2) is the biggest -> bisect
    N = int(input())
    A = sorted(map(int, input().split()))
    if N == 2:
        print(A[1], A[0])
        return
    n, idx = A[-1], bs(A[:-1], A[-1] // 2)
    cand = [abs(A[i] - n / 2), A[i] for i in (idx - 1, idx, idx + 1)]
    r = min(cand)[1]
    print(n, r)


if __name__ == "__main__":
    main()
Problem p03425 (python)

Fixed submission:
# ABC089
import sys
input = sys.stdin.readline

from itertools import combinations

n = int(input())
lst = [input().rstrip() for _ in range(n)]
cond = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in lst:
    if i[0] in "MARCH":
        cond[i[0]] += 1
ans = 0
for x, y, z in combinations("MARCH", 3):
    ans += cond[x] * cond[y] * cond[z]
print(ans)

Buggy submission (verdict: Runtime Error):
# ABC089C - March
from itertools import combinations as comb


def main():
    N, *S = open(0).read().split()
    cnt = [sum(s.startswith(i) for S) for i in "MARCH"]
    ans = sum(x * y * z for x, y, z in comb(cnt, 3))
    print(ans)


if __name__ == "__main__":
    main()
Problem p03455 (python)

Fixed submission:
# ABC086A - Product
a, b = list(map(int, input().rstrip().split()))
print("Even" if a % 2 == 0 or b % 2 == 0 else "Odd")

Buggy submission (verdict: Runtime Error):
a, b = listmap(int, input().rstrip().split())
print("Even" if a % 2 or b % 2 else "Odd")
Problem p03475 (python)

Fixed submission:
# ABC084C - Special Trains
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    arr = tuple(tuple(map(int, input().split())) for _ in range(n - 1))
    for i in range(n):
        cur = 0
        for c, s, f in arr[i:]:
            if cur <= s:
                cur = s + c
            else:
                cur = (cur + f - 1) // f * f + c
        print(cur)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC084C - Special Trains
def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    for i in range(n):
        cur = 0
        for c, s, f in A[i:]:
            if cur <= s:
                cur = s + c
            else:
                cur = (cur + f - 1) // f * f + c
        print(cur)


if __name__ == "__main__":
    main()
Problem p03478 (python)

Fixed submission:
# ABC083B - Some Sums

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

for i in range(n + 1):
    total = sum(list(map(int, list(str(i)))))
    if a <= total <= b:
        answer += i
    
print(answer)

Buggy submission (verdict: Runtime Error):
# ABC083B - Some Sums
def main():
    N, A, B = tuple(map(int, input().split()))
    ans = sum(i for i in range(1, N + 1) if a <= sum(map(int, str(i))) <= b)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC083B - Some Sums
import sys

n, a, b = list(map(int, stdin.readline().split()))
answer = 0
for i in range(1, n + 1):
    total = 0
    while i > 9:
        total += i % 10
        i //= 10
    if a <= i and i <= b:
        answer += total

print(answer)
Problem p03489 (python)

Fixed submission:
# ARC087C - Good Sequence (ABC082C)
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lst = list(map(int, input().rstrip().split()))
    cnt = {}
    for i in lst:
        if i not in cnt:
            cnt[i] = 0
        cnt[i] += 1
    ans = 0
    for i, j in cnt.items():
        if i > j:
            ans += j
        elif i < j:
            ans += j - i
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ARC087C - Good Sequence (ABC082C)
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lst = list(map(int, input().rstrip().split()))
    cnt = [0] * (10 * 9 + 1)
    for i in lst:
        cnt[i] += 1
    ans = 0
    for i, j in enumerate(cnt):
        if i > j:
            ans += j
        elif i < j:
            ans += j - i
    print(ans)


if __name__ == "__main__":
    main()
Problem p03495 (python)

Fixed submission:
# ABC081C - Not so Diverse (ARC086C)
n, k = list(map(int, input().rstrip().split()))
lst = sorted(list(map(int, input().rstrip().split())))
dic = {}
for i in lst:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

cnt = sorted([i for i in dic.values()], reverse=True)
ans = 0
for i in range(len(cnt)):
    if k > 0:
        k -= 1
        continue
    ans += cnt[i]
print(ans)

Buggy submission (verdict: Runtime Error):
# ABC081C - Not so Diverse (ARC086C)
from collections import Counter


def main():
    N, K, *A = map(int, open(0).read().split())
    C = Counter(A).values()
    C.sort(reverse=1)
    ans = sum(C[K:])
    print(ans)


if __name__ == "__main__":
    main()
Problem p03523 (python)

Fixed submission:
# cf17-finalA - AKIBA
def main():
    S = input().rstrip()
    flg = (
        S.replace("A", "") == "KIHBR"
        and "AA" not in S
        and "KA" not in S
        and "IA" not in S
    )
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# cf17-finalA - AKIBA
def main():
    S = input().rstrip()
    flg = S.replace("A", "") == "KIHBR" and "AA" not in S and "KA
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()
Problem p03569 (python)

Fixed submission:
# code-festival-2017-qualcC - Inserting 'x'
from collections import deque


def main():
    S = deque(list(input().rstrip()))
    ans = 0
    while len(S) >= 2:
        l, r = S[0], S[-1]
        if l == r:
            S.popleft(), S.pop()
        else:
            ans += 1
            if l == "x":
                S.append("x")
            elif r == "x":
                S.appendleft("x")
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# code-festival-2017-qualcC - Inserting 'x'
def main():
    S = input().rstrip()
    ans, l, r = 0, 0, len(S) - 1
    while l != r:
        if S[l] == S[r]:
            l += 1
            r -= 1
        else:
            ans += 1
            if S[l] == "x":
                l += 1
            elif S[r] == "x":
                r -= 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()