Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))

class mod_pack:

    def __init__(self, MOD, MAX):
        self.MOD = MOD
        self.MAX = MAX
        self.fac, self.ifac = [1]*(MAX+1), [1]*(MAX+1)
        for i in range(1, MAX+1):
            self.fac[i] = self.fac[i-1]*i % MOD
            self.ifac[i] = self.ifac[i-1] * self.mpow(i, MOD-2) % MOD
    
    def mpow(self, x, n):
        ans = 1
        while n!=0:
            if n&1: ans = ans*x % self.MOD
            x = x*x % self.MOD
            n = n >> 1
        return ans

    def mcomb(self, m, n):
        if (m==0 and n==0): return 1
        return (self.ifac[m-n] * self.ifac[n] % self.MOD) * self.fac[m] % self.MOD

    def mperm(self, m, n):
        if (m < n): return 0
        return self.ifac[m-n] * self.fac[m] % MOD
    

mp = mod_pack(10**9+7, M)

tot = mp.mperm(M, N)
ans = 0
for k in range(1, N+1):
#    print(k, mp.mcomb(N, k), mp.mperm(M-k, N-k))
    ans = (ans + (-1)**(k-1) * mp.mcomb(N, k) * mp.mperm(M-k, N-k)) % MOD


print((tot * (tot - ans))%MOD)



Fixed submission:
N, M = list(map(int, input().split()))
MOD = 10 ** 9 + 7

class mod_pack:

    def __init__(self, MOD, MAX):
        self.MOD = MOD
        self.MAX = MAX
        self.fac, self.ifac = [1]*(MAX+1), [1]*(MAX+1)
        for i in range(1, MAX+1):
            self.fac[i] = self.fac[i-1]*i % MOD
            self.ifac[i] = self.ifac[i-1] * self.mpow(i, MOD-2) % MOD
    
    def mpow(self, x, n):
        ans = 1
        while n!=0:
            if n&1: ans = ans*x % self.MOD
            x = x*x % self.MOD
            n = n >> 1
        return ans

    def mcomb(self, m, n):
        if (m==0 and n==0): return 1
        return (self.ifac[m-n] * self.ifac[n] % self.MOD) * self.fac[m] % self.MOD

    def mperm(self, m, n):
        if (m < n): return 0
        return self.ifac[m-n] * self.fac[m] % MOD
    

mp = mod_pack(10**9+7, M)

tot = mp.mperm(M, N)
ans = 0
for k in range(1, N+1):
#    print(k, mp.mcomb(N, k), mp.mperm(M-k, N-k))
    ans = (ans + (-1)**(k-1) * mp.mcomb(N, k) * mp.mperm(M-k, N-k)) % MOD


print((tot * (tot - ans))%MOD)
Buggy python submission (verdict: Runtime Error):
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

array.array("L", (A[n] for n in range(N) if n!=i))

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])


Fixed submission:
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])

Buggy python submission (verdict: Runtime Error):
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

array.array("L", (A[n] for n in range(N) if n!=i))

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])


Fixed submission:
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])

Buggy python submission (verdict: Runtime Error):
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

array.array((A[n] for n in range(N) if n!=i))

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])


Fixed submission:
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])

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

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

for i in range(N):
    print(reduce(xor, array.array("L", (A[n] for n in range(N) if n!=i))))


Fixed submission:
import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])
Buggy python submission (verdict: Time Limit Exceeded):
import array

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

A.sort()
cnt = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            cnt += 1
            break
        if A[j] > A[i]: break

print (N-cnt)


Fixed submission:
import numpy as np
import random

rand = False
if rand:
    N = 10 ** 5
    A = random.choices(range(1, 10**6), k=N)
else:
    N = int(input())
    A = list(map(int, input().split()))

A.sort()
MX = max(A)
ret = np.zeros(MX+1, dtype=np.bool)
A = np.array(A, dtype=np.int32)
ret[ A ] = True

for i in range(N-1):
    m = A[i] * 2
    if A[i] == A[i+1]: m = A[i]
    ret[ np.arange(m, MX+1, A[i]) ] = False

print(np.sum(ret))
Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input().split))

print(A*B)


Fixed submission:
A, B = list(map(int, input().split()))

print(A*B)
Buggy python submission (verdict: Runtime Error):
	from collections import Counter
import math

NN = int(input())
c = Counter()
# create sieve
#MAXLEN = math.ceil(math.sqrt(N+1))+1
#sv = [False] * (MAXLEN+1)
#pr = list()
#for i in range(2, MAXLEN+1):
#    if sv[i]: continue
#    pr.append(i)
#    for j in range(i, MAXLEN+1, i):
#        sv[j] = True
#if N!=1: pr.append(N)
N = NN
for i in range(2, math.ceil(math.sqrt(N)+1)+1):
    while N%i == 0:
        c.update([i])
        N = N // i
if N!=1: c.update([N])
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)


Fixed submission:
from collections import Counter
import math

N = int(input())
c = Counter()

for i in range(2, math.ceil(math.sqrt(N)+1)+1):
    while N%i == 0:
        c.update([i])
        N = N // i
if N!=1: c.update([N])
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
c = Counter()
# create sieve
MAXLEN = math.ceil(math.sqrt(N+1))+1
sv = [False] * (MAXLEN+1)
pr = list()
for i in range(2, MAXLEN+1):
    if sv[i]: continue
    pr.append(i)
    for j in range(i, MAXLEN+1, i):
        sv[j] = True
if N!=1: pr.append(N)

i = 2
for i in range(len(pr)):
    p = pr[i]
    while N%p == 0:
        c.update([p])
        N = N // p
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)


Fixed submission:
from collections import Counter
import math

N = int(input())
c = Counter()

for i in range(2, math.ceil(math.sqrt(N)+1)+1):
    while N%i == 0:
        c.update([i])
        N = N // i
if N!=1: c.update([N])
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

path = [0]*N

pos = 1
for i in range(K):
    if pos in path: break
    path[i] = pos
    pos = A[pos]

head = path[:path.index(pos)]
rep = path[path.index(pos):i]

print(rep[(K - len(head)) % len(rep)])



Fixed submission:
N, K = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

path = [0]*(N+1)
visited = set()

pos = 1
for i in range(N+1):
    if pos in visited: break
    path[i] = pos
    visited.add(pos)
    pos = A[pos]

loc = path.index(pos)
head = path[:loc]
rep = path[loc:i]

if K < len(head):
    print(head[K])
else:
    print(rep[(K - len(head)) % len(rep)])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i]*A[j]
            ans %= MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


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

MOD = 10**9+7


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    t = 0
    for i in reversed(range(N-1)):
        t += A[i+1]
        t %= MOD
        ans += t * A[i]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


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


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            has_r = False
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    has_r = True
                    break
            if not has_r:
                break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    counter = collections.Counter(a)
    q = int(input())
    for i in range(q):
        b, c = map(int, input().split())
        cnt = counter[b]
        del counter[b]
        counter[c] += cnt
        ans = 0
        for key in counter:
            ans += key * counter[key]
        print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


Fixed submission:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    counter = collections.Counter(a)
    q = int(input())
    sum = 0
    for key in counter:
        sum += key * counter[key]
    for i in range(q):
        b, c = map(int, input().split())
        cnt = counter[b]
        del counter[b]
        counter[c] += cnt
        sum += (c-b)*cnt

        print(sum)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        if i > 0 and a[i] == a[i-1]:
            continue
        if i + 1 < n and a[i] == a[i+1]:
            continue
        isDiv = False
        for j in range(i):
            if i != j and a[i] % a[j] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


Fixed submission:
import sys
import collections
sys.setrecursionlimit(10**6)

M = 10**6+5


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * M
    for i in range(n):
        if cnt[a[i]] != 0:
            cnt[a[i]] += 1
            continue

        for j in range(a[i], M, a[i]):
            cnt[j] += 1
    ans = 0
    for i in range(n):
        if cnt[a[i]] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = list(collections.Counter(a).items())
    ans = 0
    for i in range(len(a)):
        if a[i][1] > 1:
            continue
        isDiv = False
        for j in range(i):
            if a[i][0] % a[j][0] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


Fixed submission:
import sys
import collections
sys.setrecursionlimit(10**6)

M = 10**6+5


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * M
    for i in range(n):
        if cnt[a[i]] != 0:
            cnt[a[i]] += 1
            continue

        for j in range(a[i], M, a[i]):
            cnt[j] += 1
    ans = 0
    for i in range(n):
        if cnt[a[i]] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    vx = [0, 1, 0, -1]
    vy = [-1, 0, 1, 0]

    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    table = [[] for _ in range(H)]
    for i in range(H):
        table[i] = list(input().strip())
    q = deque()
    q.append((x1-1, y1-1, 0))
    table[x1-1][y1-1] = 0
    while len(q) > 0:
        x, y, cnt = q.popleft()
        for i in range(4):
            for k in range(1, K+1):
                nx = x + vx[i] * k
                ny = y + vy[i] * k
                if nx < 0 or ny < 0 or nx >= H or ny >= W:
                    break
                if table[nx][ny] == '@':
                    break
                if table[nx][ny] != '.':
                    continue
                table[nx][ny] = cnt+1
                q.append((nx, ny, cnt+1))
    if table[x2-1][y2-1] == '.':
        print(-1)
    else:
        print(table[x2-1][y2-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    vx = [0, 1, 0, -1]
    vy = [-1, 0, 1, 0]

    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    table = [[] for _ in range(H)]
    for i in range(H):
        table[i] = list(input().strip())
    q = deque()
    q.append((x1-1, y1-1, 0))
    table[x1-1][y1-1] = 0
    while len(q) > 0:
        x, y, cnt = q.popleft()
        for i in range(4):
            for k in range(1, K+1):
                nx = x + vx[i] * k
                ny = y + vy[i] * k
                if nx < 0 or ny < 0 or nx >= H or ny >= W:
                    break
                if table[nx][ny] == '@':
                    break
                if table[nx][ny] != '.':
                    if table[nx][ny] < cnt + 1:
                        break
                    else:
                        continue
                table[nx][ny] = cnt+1
                q.append((nx, ny, cnt+1))
    if table[x2-1][y2-1] == '.':
        print(-1)
    else:
        print(table[x2-1][y2-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    x = list(map(int, input().split()))
    ans = 1
    for i in range(len(x)):
        ans *= x[i]
    if ans > 10**18:
        print('-1')
    else:
        print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


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


def main(input, print):
    n = int(input())
    x = list(map(int, input().split()))
    ans = 1
    if 0 in x:
        print('0')
        return
    for i in range(len(x)):
        ans *= x[i]
        if ans > 10**18:
            print('-1')
            return
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    table = [0] * (10**5+5)
    for i in range(len(a)):
        table[a[i]-1] += 1

    for i in range(n):
        print(table[i])


main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    table = [0] * (2*10**5+5)
    for i in range(len(a)):
        table[a[i]-1] += 1

    for i in range(n):
        print(table[i])


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def make_cmb_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], -1)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i
    return (fact, ifact)


def cmb(n, r, table):
    if r > n:
        return 0
    return int(table[0][n] * table[1][n - r] * table[1][r])


def main():
    n = int(input())
    a = list(map(str, input().split()))
    table = make_cmb_table(n)

    d = dict()
    for i in range(n):
        if a[i] in d:
            d[a[i]] = d[a[i]] + 1
        else:
            d[a[i]] = 1

    total = 0
    normal = dict()
    target = dict()
    for k, v in d.items():
        t = cmb(v, 2, table)
        normal[k] = t
        target[k] = cmb(v-1, 2, table)
        total += t

    for i in range(n):
        print(total - normal[a[i]] + target[a[i]])


main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n = int(input())
    a = list(map(str, input().split()))

    d = dict()
    for i in range(n):
        if a[i] in d:
            d[a[i]] = d[a[i]] + 1
        else:
            d[a[i]] = 1

    total = 0
    normal = dict()
    target = dict()
    for k, v in d.items():
        if v == 1:
            normal[k] = 0
            target[k] = 0
        else:
            normal[k] = (v-1) * ((v-1) + 1) // 2
            target[k] = normal[k] - (v-1)
            total += normal[k]

    for i in range(n):
        print(total - normal[a[i]] + target[a[i]])


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            a.reverse()
            tmp = end
            end = len(a)-start-1
            start = len(a)-tmp-1
        elif query[0] == '2':
            if query[1] == '1':
                a[start-1] = query[2]
                start -= 1
            elif query[1] == '2':
                a[end+1] = query[2]
                end += 1
    print(''.join(a[start:end+1]))


main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    frip = False
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            frip = not frip
        elif query[0] == '2':
            if (query[1] == '1' and frip == False) or (query[1] == '2' and frip == True):
                a[start-1] = query[2]
                start -= 1
            else:
                a[end+1] = query[2]
                end += 1
    if frip:
        a.reverse()
        tmp = end
        end = len(a)-start-1
        start = len(a)-tmp-1
    print(''.join(a[start:end+1]))


main()

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = list(input())
    q = int(input())
    s.pop(-1)
    a = [''] * (10**5*2)
    a.append(*s)
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            tmp = a[start]
            a[start] = a[end]
            a[end] = tmp
        elif query[0] == '2':
            if query[1] == '1':
                a[start-1] = query[2]
                start -= 1
            elif query[1] == '2':
                a[end+1] = query[2]
                end += 1
    print(''.join(a[start:end+1]))


main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    frip = False
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            frip = not frip
        elif query[0] == '2':
            if (query[1] == '1' and frip == False) or (query[1] == '2' and frip == True):
                a[start-1] = query[2]
                start -= 1
            else:
                a[end+1] = query[2]
                end += 1
    if frip:
        a.reverse()
        tmp = end
        end = len(a)-start-1
        start = len(a)-tmp-1
    print(''.join(a[start:end+1]))


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():

    n = int(input())
    s = list(input())
    q = int(input())
    for i in range(q):
        a, b, c = map(str, input().split())
        if a == '1':
            s[int(b)-1] = c
        else:
            p = s[int(b)-1:int(c)]
            print(len(set(p)))


main()


Fixed submission:
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():

    n = int(input())
    s = list(input().strip())
    q = int(input())
    alpha = g = [[] for _ in range(26)]
    orda = ord('a')
    for i in range(n):
        alpha[ord(s[i])-orda].append(i)
    for i in range(q):
        a, b, c = map(str, input().split())
        if a == '1':
            b = int(b)-1
            if c != s[b]:
                alpha[ord(s[b])-orda].remove(b)
                s[b] = c
                bisect.insort(alpha[ord(c)-orda], b)
        else:
            ans = 0
            for i in range(26):
                if len(alpha[i]) > 0:
                    it = bisect.bisect_left(alpha[i], int(b)-1)
                    if it < len(alpha[i]) and alpha[i][it] < int(c):
                        ans += 1
            print(ans)


main()