Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline


h, w, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]


cnt_h = [0] * h
cnt_w = [0] * w
is_ = [[0] * w for i in range(h)]
for i, j in info:
    i -= 1
    j -= 1
    cnt_h[i] += 1
    cnt_w[j] += 1
    is_[i][j] += 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt_h[i] + cnt_w[j] - is_[i][j])
print(ans)

Fixed submission:
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline

class SegmentTree:
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    build(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def build(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)


h, w, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]


cnt_h = [0] * h
cnt_w = [0] * w
memo_i = {}
for i in range(h):
    memo_i[i] = []

for i, j in info:
    i -= 1
    j -= 1
    cnt_h[i] += 1
    cnt_w[j] += 1
    memo_i[i].append(j)


st = SegmentTree(w, max, 0)
st.build(cnt_w)


ans = 0
for i in range(h):
    for j in memo_i[i]:
        st.update(j, cnt_w[j] - 1)
    ans = max(st.get_val(0, w) + cnt_h[i], ans)
    for j in memo_i[i]:
        st.update(j, cnt_w[j])

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
val = int(x, 2)

cnt1 = x.count("1")
p_cnt = cnt1 + 1
m_cnt = cnt1 - 1
p_amari = val % (cnt1 + 1)
m_amari = val % (cnt1 - 1)


#p_mod = [0] * (n + 1)
#for i in range(n + 1):
#    p_mod[i] = pow(2, i, p_cnt)

#m_mod = [0] * (n + 1)
#for i in range(n + 1):
#    m_mod[i] = pow(2, i, m_cnt)


for i in range(n):
    ans = 0
    if x[i] == "0":
        # pになる
        amari = p_amari + pow(2, n - i - 1, p_cnt)
        amari %= p_cnt
        ans += 1
    elif x[i] == "1":
        # mになる
        amari = m_amari - pow(2, n - i - 1, m_cnt)
        amari %= m_cnt
        ans += 1
    while amari != 0:
        amari %= bin(amari).count("1")
        ans += 1
    print(ans)

Fixed submission:
n = int(input())
x = input()
val = int(x, 2)

cnt1 = x.count("1")
p_cnt = cnt1 + 1
m_cnt = cnt1 - 1
p_amari = val % (cnt1 + 1)
if cnt1 - 1 != 0:
    m_amari = val % (cnt1 - 1)
else:
    m_amari = 0


for i in range(n):
    ans = 0
    if x[i] == "0":
        # pになる
        amari = p_amari + pow(2, n - i - 1, p_cnt)
        amari %= p_cnt
        ans += 1
    elif x[i] == "1":
        # mになる
        if cnt1 - 1 == 0:
            print(0)
            continue
        amari = m_amari - pow(2, n - i - 1, m_cnt)
        amari %= m_cnt
        ans += 1
    while amari != 0:
        amari %= bin(amari).count("1")
        ans += 1
    print(ans)
Buggy python submission (verdict: Runtime Error):
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue
 
        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]
 
        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()

    hand = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            # 手持ちでvalを作れるか確認する
            hand.sort(reverse=True)
            for num in memo_0:
                if val & num == num:
                    val -= num
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            hand.append(val)
            # 手持ちは基底で管理するので掃き出し法を行う
            hand = xor_gauss_jordan(memo_0)


    if flag:
        print(1)
    else:
        print(0)

Fixed submission:
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue
 
        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]
 
        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()

    hand = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            # 手持ちでvalを作れるか確認する
            hand.sort(reverse=True)
            for num in hand:
                if val.bit_length() == num.bit_length():
                    val ^= num
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            hand.append(val)
            # 手持ちは基底で管理するので掃き出し法を行う
            hand = xor_gauss_jordan(hand)


    if flag:
        print(1)
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

if n % 2 == 1:
    info = sorted(info)
    l = info[n // 2][0]
    info = sorted(info)[::-1]
    r = info[n // 2][1]
    print(r - l + 1)
else:
    print(re)


Fixed submission:
from operator import itemgetter

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
a = [info[i][0] for i in range(n)]
b = [info[i][1] for i in range(n)]

a = sorted(a)
b = sorted(b)
if n % 2 == 1:
    l = a[n // 2]
    r = b[n // 2]
    print(r - l + 1)
else:
    l1, l2 = a[n // 2 - 1], a[n // 2]
    r1, r2 = b[n // 2 - 1], b[n // 2]
    print((r1 + r2) - (l1 + l2) + 1)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

s = input()
MOD = 2019

dp = [0] * ((MOD) * (len(s) + 1))
# dp = [[0] * (MOD) for i in range(len(s) + 1)]

dp[0] = 0
for i in range(len(s)):
    tmp = int(s[i])
    dp[(i + 1) * MOD + tmp] += 1
    for val in range(MOD):
        dp[(i + 1) * MOD + (val * 10 + tmp) % MOD] += dp[i * MOD + val]

ans = 0
for i in range(len(s) + 1):
    ans += dp[i * MOD]
    
print(ans)


Fixed submission:
s = input()
MOD = 2019

dp = [0] * MOD
dq = [0] * MOD
ans = 0

for i in range(len(s)):
    tmp = int(s[i])
    if i % 2 == 0:
        for val in range(MOD):
            dp[((val * 10) + tmp) % MOD] += dq[val]
            dq[val] = 0
        dp[tmp] += 1
        ans += dp[0]

    else:
        for val in range(MOD):
            dq[((val * 10) + tmp) % MOD] += dp[val]
            dp[val] = 0
        dq[tmp] += 1
        ans += dq[0] 
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
MOD = 2019

dp = [[0] * (MOD) for i in range(len(s) + 1)]

dp[0][0] = 0
for i in range(len(s)):
    tmp = int(s[i])
    for val in range(MOD):
        dp[i + 1][((val * 10) + tmp) % MOD] += dp[i][val]
    dp[i + 1][tmp] += 1

ans = 0
for i in range(len(s) + 1):
    ans += dp[i][0]
    
print(ans)


Fixed submission:
s = input()
MOD = 2019

dp = [0] * MOD
dq = [0] * MOD
ans = 0

for i in range(len(s)):
    tmp = int(s[i])
    if i % 2 == 0:
        for val in range(MOD):
            dp[((val * 10) + tmp) % MOD] += dq[val]
            dq[val] = 0
        dp[tmp] += 1
        ans += dp[0]

    else:
        for val in range(MOD):
            dq[((val * 10) + tmp) % MOD] += dp[val]
            dp[val] = 0
        dq[tmp] += 1
        ans += dq[0] 
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline


def convolve(a, b):
    """配列a, bの畳み込みをNTT(number-theoretical transform)によって計算する
    res[k] = (sum{i=0...n}a[i]*b[k-i]) % MOD
    """
    MOD = 998244353
    ROOT = 5

    def ntt(a, inverse=False):
        # バタフライ演算用の配置入れ替え
        for i in range(n):
            j = 0
            for k in range(log_sz):
                j |= (i >> k & 1) << (log_sz - 1 - k)
            if i < j:
                a[i], a[j] = a[j], a[i]

        h = pow(ROOT, (MOD - 1) * pow(n, MOD - 2, MOD) % MOD, MOD)
        if inverse:
            h = pow(h, MOD - 2, MOD)

        # バタフライ演算
        m = 1
        while m < n:
            zeta_pow = 1
            zeta = pow(h, n // (2 * m), MOD)
            for j in range(m):
                for k in range(0, n, 2 * m):
                    s = a[j + k]
                    t = a[j + k + m] * zeta_pow
                    a[j + k] = (s + t) % MOD
                    a[j + k + m] = (s - t) % MOD
                zeta_pow *= zeta
                zeta_pow %= MOD
            m <<= 1

        # 逆変換時には配列のサイズの逆元をかける
        if inverse:
            n_inv = pow(n, MOD - 2, MOD)
            for i in range(n):
                a[i] *= n_inv
                a[i] %= MOD
        return a

    def intt(a):
        return ntt(a, inverse=True)

    n = 1 << (len(a) + len(b) - 1).bit_length()
    log_sz = n.bit_length() - 1
    a += [0] * (n - len(a))
    b += [0] * (n - len(b))

    # in-placeで計算を進めることに注意
    ntt(a), ntt(b)
    for i, val in enumerate(b):
        a[i] *= val
        a[i] %= MOD
    intt(a)

    return a
  

n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

ptn = [1]
ans = 0
for i in range(n):
    add = [0] * (a[i] + 1)
    add[0] = 1
    add[-1] = 1
    ptn = convolve(ptn, add)[:s + 1]
    if len(ptn)  > s:
        ans += ptn[s]
        ans %= MOD
    ptn[0] += 1

print(ans)

Fixed submission:
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

dp = [0] * (3000 + 1)
dp[0] = 1
ans = 0
for i in range(n):
    for w in range(3000 + 1)[::-1]:
        # 選ぶとき
        if w - a[i] > 0:
            dp[w] += dp[w - a[i]]
        if w - a[i] == 0:
            dp[w] += dp[w - a[i]] * (i + 1)
        dp[w] %= MOD
    ans += dp[s]
    ans %= MOD
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
n = int(input())

s = input()
a = []
for i in range(n - 1):
    a.append(abs(int(s[i]) - int(s[i + 1])))

ans = []
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)

Fixed submission:
n = int(input())

s = input()
a = []
for i in range(n - 1):
    a.append(abs(int(s[i]) - int(s[i + 1])))

ans = []
for r in range(n - 1):
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import copy

n, p = list(map(int, input().split()))
s = input()


memo = {}
ans = 0
for i in range(n):
    memo2 = {int(s[i]) % p: 1}
    for j in memo:
        if (j * 10 + int(s[i])) % p not in memo2:
            memo2[(j * 10 + int(s[i])) % p] = memo[j]
        else:
            memo2[(j * 10 + int(s[i])) % p] += memo[j]
    memo = copy.deepcopy(memo2)
    if 0 in memo:
        ans += memo[0]
print(ans)


Fixed submission:
n, p = map(int, input().split())
s = input()

ans = 0
if p == 2:
    for i, char in enumerate(s):
        if int(char) % 2 == 0:
            ans += i + 1
    print(ans)

elif p == 5:
    for i, char in enumerate(s):
        if int(char) % 5 == 0:
            ans += i + 1
    print(ans)

else:
    a = [0] * (n + 1)
    for i in range(n):
        a[i + 1] = a[i] + int(s[n - i - 1]) * pow(10, i, p)
        a[i + 1] %= p
    memo = {}
    for i in range(n + 1):
        if a[i] not in memo:
            memo[a[i]] = 1
        else:
            memo[a[i]] += 1
    for i in memo:
        ans += memo[i]* (memo[i] - 1) // 2
    print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = [0] * n
ans = 0
for i in range(n):
    ans[i] = (p[i] + 1) / 2

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)
    

Fixed submission:
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = [0] * n
for i in range(n):
    ans[i] = (p[i] + 1) / 2

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)

Buggy python submission (verdict: Runtime Error):
5 3
1 2 2 4 5

Fixed submission:
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = [0] * n
for i in range(n):
    ans[i] = (p[i] + 1) / 2

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    r *= (r2 + 1 + (i + 1))
    r *= pow((i + 2), MOD - 2, MOD)
    l *= (r1 + (i + 1))
    l *= pow((i + 2), MOD - 2, MOD)
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)

Fixed submission:
r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    gyaku = pow((i + 2), MOD - 2, MOD)
    r *= (r2 + 1 + (i + 1))
    r *= gyaku
    l *= (r1 + (i + 1))
    l *= gyaku
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


def compress(array):
    """座標圧縮したリストを返す"""
    array2 = sorted(set(array))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

n, d, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

info = sorted(info)
b = [info[i][0] for i in range(n)]
memo = compress([info[i][0] for i in range(n)])
bit = BIT(n)

for i in range(n):
    ind, val = info[i]
    bit.add(memo[ind], memo[ind] + 1, val)

ans = 0
for i in range(n):
    tmp = bit.get_val(i)
    if tmp <= 0:
        continue
    ans += -((-tmp) // a)
    ind, _ = info[i]
    nxt_ind = ind + 2 * d
    ii = bisect.bisect_right(b, nxt_ind)
    bit.add(i, ii, ((-tmp) // a) * a)
print(ans)

Fixed submission:
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from operator import itemgetter
n, d, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

info = sorted(info, key = itemgetter(0))
bit = BIT(n)

for i in range(n):
    bit.add(i, i+1, info[i][1])

info.append([10**18, 0])
ans = 0 
r = 0
for i in range(n):
    num = bit.get_val(i)
    if num <= 0:
        continue
    while True:
        if info[r][0] - info[i][0] > 2*d:
            break
        else:
            r += 1
    ans += -((-num) // a)
    bit.add(i, r, -(-((-num) // a)) * a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a)
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
    ans %= MOD
print(ans % MOD)


Fixed submission:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a)
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
from collections import deque


def dfs(start, goal, tree):
    """startからgoalまでの木上のpathを出力する"""
    q = deque([start])
    visited = {}
    visited[start] = -1
    while True:
        pos = q.pop()
        if pos == goal:
            break
        for child in tree[pos]:
            if child in visited:
                continue
            visited[child] = pos
            q.append(child)
    res = []
    pos = goal
    while True:
        par = visited[pos]
        if par == -1:
            break
        res.append((min(par, pos), max(par, pos)))
        pos = par
    return res


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i
  

li_path = [0] * m
for i in range(m):
    s, g = path[i]
    s -= 1
    g -= 1
    res = dfs(s, g)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)


Fixed submission:
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i


def dfs(par, pos, goal):
    if pos == goal:
        return True
    for child in tree[pos]:
        if child == par:
            continue
        if dfs(pos, child, goal):
            res.append((min(pos, child), max(pos, child)))
            return True
    return False
  

li_path = [0] * m
for i in range(m):
    res = []
    s, g = path[i]
    s -= 1
    g -= 1
    dfs(-1, s, g)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)

             
def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0] 
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))

l = [0] * n
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            cnt += 1
            tmp //= 2
        else:
           break
    l[i] = cnt
if max(l) != min(l):
    print(0)
    exit()
    
div = multi_lcm(a)
ans = 0
if m - div // 2 >= 0:
    ans += 1
m = m - div // 2 
ans += m // div
if m < 0:
    print(0)
else:
    print(ans)


Fixed submission:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)

             
def multi_lcm(array, m):
    """arrayのLCMを求める"""
    ans = array[0] 
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
        if ans > 5*m:
            return 5*m
    return ans 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))

l = [0] * n
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            cnt += 1
            tmp //= 2
        else:
           break
    l[i] = cnt
if max(l) != min(l):
    print(0)
    exit()
    
div = multi_lcm(a, m)
ans = 0
if m - div // 2 >= 0:
    ans += 1
m = m - div // 2 
ans += m // div
if m < 0:
    print(0)
else:
    print(ans)