Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        A = [False] * N
        t = 0
        for i in range(M):
            while True:
                while A[t%N]:
                    t += 1
                A[t%N] = True
                if A[(t + i + 1)% N]:
                    A[t%N] = False
                    t += 1
                    continue
                break
            A[(t + i + 1) % N] = True
            print(t%N + 1, (t + i + 1)%N + 1)

main()


Fixed submission:
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        s = set()
        t = 0
        for i in range(M):
            a, b = i + 1, N - i - t
            if (b - a) in s or (a + N - b) in s or b - a == a + N - b:
                t += 1
                b = N - i - t
            print(a, b)
            s.add(b - a)
            s.add(N + a - b)

main()

Buggy python submission (verdict: Runtime Error):
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        A = [False] * N
        t = 0
        for i in range(M):
            while True:
                while A[t]:
                    t += 1
                A[t] = True
                if A[(t + i + 1)% N]:
                    A[t] = False
                    t += 1
                    continue
                break
            A[(t + i + 1) % N] = True
            print(t + 1, t + i + 2)

main()


Fixed submission:
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        s = set()
        t = 0
        for i in range(M):
            a, b = i + 1, N - i - t
            if (b - a) in s or (a + N - b) in s or b - a == a + N - b:
                t += 1
                b = N - i - t
            print(a, b)
            s.add(b - a)
            s.add(N + a - b)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())


Fixed submission:
def ff(n):
    i = 1
    r = set()
    while i * i <= n:
        if n % i == 0:
            r.add(i)
            if i != n // i:
                r.add(n // i)
        i += 1
    return sorted(r)

def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    T = [[] for _ in range(K + 1)]
    F = [ff(i) for i in range(K + 1)]
    for i, f in enumerate(F[1:], 1):
        for j in f:
            T[j].append(i)
    r = 0
    t = [0] * (K + 1)

    for i in reversed(range(1, K + 1)):
        q = (pow(len(T[i]), N, mod) - t[i]) % mod
        for j in F[i][:-1]:
            t[j] = (t[j] + q) % mod
        r = (r + i * q) % mod

    return r

print(main())

Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())


Fixed submission:
def ff(n):
    i = 1
    r = set()
    while i * i <= n:
        if n % i == 0:
            r.add(i)
            if i != n // i:
                r.add(n // i)
        i += 1
    return sorted(r)

def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    T = [[] for _ in range(K + 1)]
    F = [ff(i) for i in range(K + 1)]
    for i, f in enumerate(F[1:], 1):
        for j in f:
            T[j].append(i)
    r = 0
    t = [0] * (K + 1)

    for i in reversed(range(1, K + 1)):
        q = (pow(len(T[i]), N, mod) - t[i]) % mod
        for j in F[i][:-1]:
            t[j] = (t[j] + q) % mod
        r = (r + i * q) % mod

    return r

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    K = {}
    r = 0
    for i in S:
        L = {}
        L[i % P] = 1
        for j, k in K.items():
            p = (j * 10 + i) % P
            L[p] = L.get(p, 0) + k
        r += L.get(0, 0)
        K = L
    return r
   

print(main())


Fixed submission:
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    if P == 2 or P == 5:
        r = 0
        for i, s in enumerate(S):
            if s % P == 0:
                r += (i + 1)
        return r

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = (h * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7
    ncr = nCrMod(mod)

    r1, c1, r2, c2 = map(int, input().split())
    r1, c1 = r1 - 1, c1 - 1
    t = ncr(r2 + c2 + 2, c2 + 1) + ncr(r1 + c1 + 2, c1 + 1) - ncr(r1 + c2 + 2, c2 + 1) - ncr(r2 + c1 + 2, c1 + 1)
    print(t % mod)

main()


Fixed submission:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7
    ncr = nCrMod(mod)

    r1, c1, r2, c2 = map(int, input().split())
    r1, c1 = r1 - 1, c1 - 1
    t = ncr(r2 + c2 + 2, c2 + 1) + ncr(r1 + c1 + 2, c1 + 1) - ncr(r1 + c2 + 2, c2 + 1) - ncr(r2 + c1 + 2, c1 + 1)
    print(t % mod)

main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0, h0))
    r = h0
    for i, (x, h) in enumerate(XH):
        while Q:
            xx, hh = Q[0]
            if xx < x - D:
                Q.popleft()
            else:
                break
        for xx, hh in Q:
            h -= hh 
            if h <= 0:
                break
        else:
            Q.append((x, h))
            r += h
    print(r)

main()


Fixed submission:
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0 + D, h0))
    r = h0
    c = h0
    for x, h in XH:
        while Q and Q[0][0] < x:
            _, hh = Q.popleft()
            c -= hh
        h -= c
        if h > 0:
            Q.append((x + D, h))
            c += h
            r += h
    print(r)

main()
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

def llcm(l):
    return reduce(lcm, l)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = A[0]
    r = 0
    MOD = 10**9 + 7
    for i, a in enumerate(A):
        nl = lcm(l, a)
        r = (r * (nl // l) + nl // a) % MOD
        l = nl
    print(r)

main()


Fixed submission:
from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

def llcm(l):
    return reduce(lcm, l)

def modinv(a, m):
    b, u, v = m, 1, 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    u %= m
    if u < 0:
        u += m
    return u

def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A) % MOD
    r = 0
    for i, a in enumerate(A):
        r = (r + l * modinv(a, MOD)) % MOD
    return r

print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

MOD = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def llcm(l):
    return reduce(lcm, l)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A)
    r = 0
    for i in A:
        r = (r + (l // i)) % MOD
    print(r)

main()


Fixed submission:
from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

def llcm(l):
    return reduce(lcm, l)

def modinv(a, m):
    b, u, v = m, 1, 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    u %= m
    if u < 0:
        u += m
    return u

def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A) % MOD
    r = 0
    for i, a in enumerate(A):
        r = (r + l * modinv(a, MOD)) % MOD
    return r

print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

MOD = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def llcm(l):
    return reduce(lcm, l)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A)
    r = 0
    for i in A:
        r = (r + (l // i)) % MOD
    print(r)

main()


Fixed submission:
from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

def llcm(l):
    return reduce(lcm, l)

def modinv(a, m):
    b, u, v = m, 1, 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    u %= m
    if u < 0:
        u += m
    return u

def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A) % MOD
    r = 0
    for i, a in enumerate(A):
        r = (r + l * modinv(a, MOD)) % MOD
    return r

print(main())
Buggy python submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    EE = shortest_path(csgraph_from_dense(m, null_value=0))
    print(int(np.max(EE[~np.isinf(EE)])))


main()


Fixed submission:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    g = csgraph_from_dense(m)
    EE = floyd_warshall(g)
    print(int(np.max(EE[~np.isinf(EE)])))


main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
def main():
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    c = 1
    ma = 0
    for i, (amax, amin) in enumerate(zip(A[k - 1:], reversed(A[:n - k + 1])), k - 1):
        ma = (ma + c * (amax - amin)) % MOD
        c = c * (i + 1) // (i - k + 2)
    print(ma)

main()


Fixed submission:
MOD = 10 ** 9 + 7

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = MOD
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def prep(n):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)


def main():
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    c = 1
    ma = 0
    prep(n)
    for i, (amax, amin) in enumerate(zip(A[k - 1:], reversed(A[:n - k + 1])), k - 1):
        ma = (ma + cmb(i, k - 1, MOD) * (amax - amin)) % MOD
    print(ma)

main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    t = 0
    for i, Ai in enumerate(A[:-1]):
        t = (t + sum(Ai ^ Aj for Aj in A[i + 1:])) % MOD
    print(t)

main()


Fixed submission:
MOD = 10 ** 9 + 7
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0] * 60
    for i in A:
        for j in range(60):
            if i & (1 << j):
                B[j] += 1
    r = 0
    for ii, i in enumerate(A[:-1]):
        for j in range(60):
            if i & (1 << j):
                B[j] -= 1
                r = (r + (1 << j) * (N - ii - 1 - B[j])) % MOD
            else:
                r = (r + (1 << j) * B[j]) % MOD
    print(r)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for _ in range(H)]
    B = [[int(i) for i in input().split()] for _ in range(H)]
    M = (H + W) * 80 + 1

    u = [[False] * M for _ in range(W)]
    v = [[False] * M for _ in range(W)]
    v[0][0] = True
    for h in range(H):
        v, u = u, v
        for w in range(W):
            a, b = A[h][w], B[h][w]
            d = a - b if a > b else b - a
            for i in range(M):
                t = False
                if 0 <= i + d < M:
                    t = t or u[w][i + d] or (w > 0 and v[w - 1][i + d])
                if 0 <= i - d < M:
                    t = t or u[w][i - d] or (w > 0 and v[w - 1][i - d])
                if 0 <= d - i < M:
                    t = t or u[w][d - i] or (w > 0 and v[w - 1][d - i])
                v[w][i] = t
    vv = v[-1]
    for i in range(M):
        if vv[i]:
            print(i)
            return
    raise

main()


Fixed submission:
def main():
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for _ in range(H)]
    B = [[int(i) for i in input().split()] for _ in range(H)]
    M = (H + W) * 80 + 1

    u = [[False] * M for _ in range(W)]
    v = [[False] * M for _ in range(W)]
    F = [False] * M
    v[0][0] = True
    for h in range(H):
        v, u = u, v
        vl = F
        for w in range(W):
            a, b = A[h][w], B[h][w]
            d = a - b if a > b else b - a
            uu = u[w]
            vv = v[w]
            for i in range(M):
                di = i - d if i > d else d - i
                vv[i] = ((i + d < M and (uu[i + d] or vl[i + d])) or
                           (uu[di] or vl[di]))
            vl = vv
    va = v[-1]
    for i in range(M):
        if va[i]:
            print(i)
            return
    raise

main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()

Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    E = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        E[a].add(b)
        E[b].add(a)
    c = [0] * N
    clrs = max(len(i) for i in E)
    BAD = 1 << clrs - 1
    def color(n):
        t = set()
        for i in E[n]:
            t.add(c[i])
        for i in range(1, clrs + 1):
            if i in t:
                continue
            c[n] = i
            for j in E[n]:
                if c[j] == 0:
                    color(j)
            return
        raise
    color(0)
    print(clrs)
    for i in c:
        print(i)

main()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = [0] * N
    r = 0
    for i, a in enumerate(A, 1):
        for j in range(i):
            v[j] = t = (v[j] + a) % K
            if t == i - j:
                r += 1
    return(r)


print(main())


Fixed submission:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    r = 0
    for i in range(N):
        t = 0
        for c, a in enumerate(A[i:], 1):
            t = (t + a) % K
            if t == c:
                r += 1
    return(r)


print(main())


Fixed submission:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    r = 0
    for i in range(N):
        t = 0
        for c, a in enumerate(A[i:], 1):
            t = (t + a) % K
            if t == c:
                r += 1
    return(r)


print(main())


Fixed submission:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())