Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input().strip())

S = input()

count = [[0,0,0] for i in range(N)]
for i in range(N-1, 0, -1):
    for j in range(3):
        count[i-1][j] = count[i][j]
    if S[i] == "R":
        count[i-1][0] += 1
    elif S[i] == "G":
        count[i-1][1] += 1
    elif S[i] == "B":
        count[i-1][2] += 1
"""
for j in range(3):
    for i in range(N):
        print(count[i][j], end = " ")
    print()
"""
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            continue
        if (S[i] == "R" and S[j] == "G") or (S[i] == "G" and S[j] == "R"):
            ans += count[j][2]
            diff = j-i
            if j+diff < N and S[j+diff] == "B":
                ans -= 1
        elif (S[i] == "B" and S[j] == "R") or (S[i] == "R" and S[j] == "B"):
            ans += count[j][1]
            diff = j-i
            if j+diff < N and S[j+diff] == "G":
                ans -= 1
        elif (S[i] == "G" and S[j] == "B") or (S[i] == "B" and S[j] == "G"):
            ans += count[j][0]
            diff = j-i
            if j+diff < N and S[j+diff] == "R":
                ans -= 1
print(ans)

Fixed submission:
N = int(input().strip())

S = input()

count = [[0,0,0] for i in range(N)]
for i in range(N-1, 0, -1):
    for j in range(3):
        count[i-1][j] = count[i][j]
    if S[i] == "R":
        count[i-1][0] += 1
    elif S[i] == "G":
        count[i-1][1] += 1
    elif S[i] == "B":
        count[i-1][2] += 1
"""
for j in range(3):
    for i in range(N):
        print(count[i][j], end = " ")
    print()
"""
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            continue
        if (S[i] == "R" and S[j] == "G") or (S[i] == "G" and S[j] == "R"):
            ans += count[j][2]
            diff = j-i
            if j+diff < N and S[j+diff] == "B":
                ans -= 1
        elif (S[i] == "B" and S[j] == "R") or (S[i] == "R" and S[j] == "B"):
            ans += count[j][1]
            diff = j-i
            if j+diff < N and S[j+diff] == "G":
                ans -= 1
        elif (S[i] == "G" and S[j] == "B") or (S[i] == "B" and S[j] == "G"):
            ans += count[j][0]
            diff = j-i
            if j+diff < N and S[j+diff] == "R":
                ans -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

A, B = map(int, input().strip().split())
print(A * B // math.gcd(A,B))

Fixed submission:
import fractions

A, B = map(int, input().strip().split())
print(A * B // fractions.gcd(A,B))
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

class Graph_CONNECT:
    """
    接続リスト方式
    """
    def __init__(self, N):
        self.number_of_node = N
        self.neighbour_list = [[] for _ in range (N)]

    def connect(self, from_node, to_node, weight):
        """
        from_nodeからto_nodeに長さweightの辺を追加する
        """
        self.neighbour_list[from_node].append((to_node, weight))

    def dijkstra(self, source_node, target_node = None):
        """
        source_nodeからtarget_nodeへの最短路計算
        source_nodeの入次数は0と仮定する
        """
        INF = 1 << 32
        dist = [INF] * self.number_of_node
        #prev = [-1] * self.number_of_node
        dist[source_node] = 0
        hq = []
        heapq.heappush(hq, (0, source_node))
        while len(hq) > 0:
            d, from_node = heapq.heappop(hq)
            if dist[from_node] < d:
                continue
            for to_node, weight in self.neighbour_list[from_node]:
                """
                weight = adj[from_node][to_node]
                # 辺がないところはスキップ
                if weight < 0:
                    continue
                """
                if dist[to_node] == INF or dist[from_node] + weight < dist[to_node]:
                    dist[to_node] = dist[from_node] + weight
                    heapq.heappush(hq, (dist[to_node], to_node))
                    #prev[to_node] = from_node
        if target_node is None:
            return dist
        else:
            return dist[target_node]

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

graph = Graph_CONNECT(N + 1)
for i in range(N+1):
    for j in range(i+1, N+1):
        if A[i] + 1 == A[j]:
            graph.connect(i,j,-1)

dist = graph.dijkstra(0)

ans = min(dist)
if ans >= 0:
    print(-1)
else:
    print(N+ans)

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

cnt = 0
for num in A:
    if num == cnt + 1:
        cnt+=1
if cnt == 0:
    print(-1)
else:
    print(N - cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N = int(input().strip())
A = list(map(int, input().strip().split()))
A.insert(0,0)
#print(A)
INF = 1 << 32
adj = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    for j in range(i+1, N+1):
        if A[i] + 1 == A[j]:
            adj[i][j] = 1

#print(adj)

dist = [INF] * (N + 1)
dist[0] = 0
hq = []
heapq.heappush(hq, (0, 0))
while len(hq) > 0:
    d, from_node = heapq.heappop(hq)
    if dist[from_node] < d:
        continue
    for to_node in range(N + 1):
        weight = adj[from_node][to_node]
        # 辺がないところはスキップ
        if weight == INF:
            continue
        weight = - weight
        if dist[to_node] == INF or dist[from_node] + weight < dist[to_node]:
            dist[to_node] = dist[from_node] + weight
            heapq.heappush(hq, (dist[to_node], to_node))
#print(dist)
ans = min(dist)
if ans >= 0:
    print(-1)
else:
    print(N+ans)

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

cnt = 0
for num in A:
    if num == cnt + 1:
        cnt+=1
if cnt == 0:
    print(-1)
else:
    print(N - cnt)
Buggy python submission (verdict: Runtime Error):
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 = 10**9+7 #出力の制限x
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


X, Y = map(int, input().strip().split())

min_num = min(X,Y)
z = min_num//3

tX = z * 3
tY = z * 3
cA = z
cB = z

rx = X - tX
ry = Y - tY
if rx == 0 and ry == 0:
    print(cmb(cA+cB, cA, mod))
    exit(0)
if rx * 2 == ry:
    cA += rx
elif ry * 2 == rx:
    cB += ry
else:
    raise Exception
    print(0)
    exit(0)
print(cmb(cA+cB, cA, mod))


Fixed submission:
r = int(input().strip())

print(r**2)
Buggy python submission (verdict: Runtime Error):
N = int(input())
D = list(map(int, input().split()))
#print(D)
sum = 0
for i in range(N):
  for j in range(i+1,N):
    sum += D[i]*D[j]

print(sum)



Fixed submission:
A,B = map(int, input().split())
print(max(0, A-2*B))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0
for i in range(1, N):
    ans += i
print(ans)

Fixed submission:
N = int(input())
ans = 0
if N%2 == 0:
    ans = N//2 * (N-1)
else:
    ans = (N-1)//2 * N
print(ans)
Buggy python submission (verdict: Runtime Error):
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

ll gcd(ll a, ll b) {
    if(a < b) return gcd(b, a);
    ll r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}


int main(){
    ll n, m, a[101000];
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] /= 2;
    }

    ll hist = a[0];
    for(int i = 1; i < n; i++){
        if(hist > m){
            cout << 0 << endl;
            return 0;
        }
        ll x = hist * a[i] / gcd(hist, a[i]);
        if((x / hist) % 2 == 0){
            cout << 0 << endl;
            return 0;
        }
        else{
            hist = x;
        }

        if(hist > m){
            cout << 0 << endl;
            return 0;
        }
    }
    if(hist > m){
        cout << 0 << endl;
        return 0;
    }

    cout << (m - hist) / (2 * hist) + 1 << endl;



    return 0;
}


Fixed submission:
import fractions
n,m = map(int,input().split())
l = input().split()
lcm = 1
sum = 0
for i in range(len(l)):
    lcm = (int(l[i]) * lcm) // fractions.gcd(int(l[i]), lcm)
for i in range(len(l)):
    if (lcm // int(l[i])) % 2 == 1:
        sum += 1
if sum == len(l):
    x = m // (int(lcm) // 2)
    y = m // lcm
    print(int(x - y))
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
import fractions
n,m = map(int,input().split())
l = input().split()
lcm = 1
sum = 0
for i in range(len(l)):
    lcm = (int(l[i]) * lcm) // fractions.gcd(int(l[i]), lcm)
for i in range(len(l)):
    if (lcm // int(l[i])) % 2 == 1:
        sum += 1
if sum == len(l):
    x = m // (int(lcm) / 2)
    y = m // lcm
    print(int(x - y))
else:
    print(0)

Fixed submission:
import fractions
n,m = map(int,input().split())
l = input().split()
lcm = 1
sum = 0
for i in range(len(l)):
    lcm = (int(l[i]) * lcm) // fractions.gcd(int(l[i]), lcm)
for i in range(len(l)):
    if (lcm // int(l[i])) % 2 == 1:
        sum += 1
if sum == len(l):
    x = m // (int(lcm) // 2)
    y = m // lcm
    print(int(x - y))
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
offset = 0
for i in range(n):
  if pred(i, p, offset):
    sum += 1
    offset = i

print(sum)

Fixed submission:
def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
minimum = n + 1
for i in range(n):
  if p[i] < minimum:
    sum += 1
    minimum = p[i]

#sum = 0
#offset = 0
#for i in range(n):
#  if pred(i, p, offset):
#    sum += 1
#    offset = i

print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
def pred(i, lst):
  for cmpd in lst[:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
for i in range(n):
  if pred(i, p):
    sum += 1

print(sum)

Fixed submission:
def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

n = int(input())
p = [int(m) for m in input().split(' ')]

sum = 0
minimum = n + 1
for i in range(n):
  if p[i] < minimum:
    sum += 1
    minimum = p[i]

#sum = 0
#offset = 0
#for i in range(n):
#  if pred(i, p, offset):
#    sum += 1
#    offset = i

print(sum)
Buggy python submission (verdict: Runtime Error):
input_lst = readline().split(' ')
cand = int(input_lst[1]) - 2 * int(input_lst[0])
print(max(0, cand))

Fixed submission:
input_lst = input().split(' ')
cand = int(input_lst[0]) -  2 * int(input_lst[1])
print(max(0, cand))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod

print((ans - 1 + nzero) % mod)


Fixed submission:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod
    ans %= mod

print((ans - 1 + nzero) % mod)
Buggy python submission (verdict: Runtime Error):
n, A, B, C = map(int, input().split())
s = [list(input()) for _ in range(n)]

cur = dict()
cur['A'], cur['B'], cur['C'] = A, B, C

counts = dict()
counts['AB'], counts['AC'], counts['BC'] = 0, 0, 0
for ss in s:
    counts[''.join(ss)] += 1

f = True
ans = []
for i, ss in enumerate(s):
    if cur[ss[0]] == 1 and cur[ss[1]] == 1 and sorted(list(cur.values())) == [0, 1, 1] and i < len(s):
        if ss[0] in s[i + 1]:
            cur[ss[0]] += 1
            cur[ss[1]] -= 1
            ans.append(ss[0])
        elif ss[1] in s[i + 1]:
            cur[ss[1]] += 1
            cur[ss[0]] -= 1
            ans.append(ss[1])

    else:
        if cur[ss[0]] >= cur[ss[1]]:
            cur[ss[0]] -= 1
            cur[ss[1]] += 1
            ans.append(ss[1])
        else:
            cur[ss[0]] += 1
            cur[ss[1]] -= 1
            ans.append(ss[0])

    if -1 in list(cur.values()):
        f = False
        break

if f:
    print('Yes')
    for a in ans:
        print(a)
else:
    print('No')


Fixed submission:
n, A, B, C = map(int, input().split())
s = [list(input()) for _ in range(n)]

cur = dict()
cur['A'], cur['B'], cur['C'] = A, B, C

f = True
ans = []
for i, ss in enumerate(s):
    if cur[ss[0]] == 1 and cur[ss[1]] == 1 and sorted(list(cur.values())) == [0, 1, 1] and i < len(s) - 1:
        if ss[0] in s[i + 1]:
            cur[ss[0]] += 1
            cur[ss[1]] -= 1
            ans.append(ss[0])
        elif ss[1] in s[i + 1]:
            cur[ss[1]] += 1
            cur[ss[0]] -= 1
            ans.append(ss[1])

    else:
        if cur[ss[0]] >= cur[ss[1]]:
            cur[ss[0]] -= 1
            cur[ss[1]] += 1
            ans.append(ss[1])
        else:
            cur[ss[0]] += 1
            cur[ss[1]] -= 1
            ans.append(ss[0])

    if -1 in list(cur.values()):
        f = False
        break

if f:
    print('Yes')
    for a in ans:
        print(a)
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n, x , y = map(int, input().split())

from collections import defaultdict
g = [[0] * n for _ in range(n)]
for i in range(1, n):
    g[i-1][i] = 1
    g[i][i-1] = 1
g[x-1][y-1] = 1
g[y-1][x-1] = 1

from scipy.sparse.csgraph import floyd_warshall
cost = floyd_warshall(g)

from collections import Counter
c = Counter()
for i in range(n):
    for j in range(i+1, n):
        c[cost[i][j]] += 1

for k in range(1, n):
    print(c[k])


Fixed submission:
n, x , y = map(int, input().split())

import heapq
from collections import defaultdict
cost = defaultdict(list)
for i in range(1, n):
    cost[i-1].append((i, 1))
    cost[i].append((i - 1, 1))
cost[x-1].append((y - 1, 1))
cost[y-1].append((x - 1, 1))

dists = []

for start in range(n):
    d = [float('inf')] * n # 最短距離
    d[start] = 0

    q = [(d[start], start)] # min-heap, (距離, 頂点)
    prev = [None] * n # 経路をたどるときに使う
    heapq.heapify(q)
    while q:
        du, u = heapq.heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            if du + weight < d[v]:
                d[v] = du + weight
                prev[v] = u
                heapq.heappush(q, (d[v], v))

    dists.append(d)



from collections import Counter
c = Counter()
for i in range(n):
    for j in range(i+1, n):
        c[dists[i][j]] += 1

for k in range(1, n):
    print(c[k])

Buggy python submission (verdict: Runtime Error):
n, x , y = map(int, input().split())

from collections import defaultdict
g = [[0] * n for _ in range(n)]
for i in range(1, n):
    g[i-1][i] = 1
    g[i][i-1] = 1
g[x-1][y-1] = 1
g[y-1][x-1] = 1

from scipy.sparse.csgraph import floyd_warshall
cost = floyd_warshall(g)

from collections import Counter
c = Counter()
for i in range(n):
    for j in range(i+1, n):
        c[cost[i][j]] += 1

for k in range(1, n):
    print(c[k])


Fixed submission:
n, x , y = map(int, input().split())

import heapq
from collections import defaultdict
cost = defaultdict(list)
for i in range(1, n):
    cost[i-1].append((i, 1))
    cost[i].append((i - 1, 1))
cost[x-1].append((y - 1, 1))
cost[y-1].append((x - 1, 1))

dists = []

for start in range(n):
    d = [float('inf')] * n # 最短距離
    d[start] = 0

    q = [(d[start], start)] # min-heap, (距離, 頂点)
    prev = [None] * n # 経路をたどるときに使う
    heapq.heapify(q)
    while q:
        du, u = heapq.heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            if du + weight < d[v]:
                d[v] = du + weight
                prev[v] = u
                heapq.heappush(q, (d[v], v))

    dists.append(d)



from collections import Counter
c = Counter()
for i in range(n):
    for j in range(i+1, n):
        c[dists[i][j]] += 1

for k in range(1, n):
    print(c[k])
Buggy python submission (verdict: Runtime Error):
h, w, K = map(int, input().split())
s = [input() for _ in range(h)]

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    # print(cut_h)
    # print(blocks)
    # print(counts)

    maxcounts = 0
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            mincounts = max(mincounts, counts[j][k])
    if maxcounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            # print(cumsums)
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    # print(tmpans)
print(ans)


Fixed submission:
h, w, K = map(int, input().split())
s = [input() for _ in range(h)]

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    # print(cut_h)
    # print(blocks)
    # print(counts)

    maxcounts = 0
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            maxcounts = max(maxcounts, counts[j][k])
    if maxcounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            # print(cumsums)
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    # print(tmpans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)


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

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        tmp2 %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    for i in range(n):
        tmp += int(s2[i]) * 10 ** i
        tmp %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)


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

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        tmp2 %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a = a[::-1]

s = [0] * (p - 1)
for i in range(p, n + 1):
    s.append(s[-1] + a[i - 1])


ans = 0
for i in range(1, n + 1):
    if i <= p:
        ans += 1
    else:
        if v <= p - 1:
            if a[i - 1] + m >= a[p - 1]:
                ans += 1

        else:
            if v - p <= n - i:
                if a[i - 1] + m >= a[p - 1]:
                    ans += 1
            else:
                if (a[i-1] + m) * (i - p) - s[i - 1] >= m * (v - p - n + i):
                    ans += 1

print(ans)


Fixed submission:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a = a[::-1]

s = [0] * p
for i in range(p, n + 1):
    s.append(s[-1] + a[i - 1])
s = s[1:]

ans = 0
for i in range(1, n + 1):
    if i <= p:
        ans += 1
    else:
        if v - 1 <= p - 1:
            if a[i - 1] + m >= a[p - 1]:
                ans += 1

        else:
            if v - p <= n - i:
                if a[i - 1] + m >= a[p - 1]:
                    ans += 1
            else:
                if a[i - 1] + m < a[p - 1]:
                    continue
                elif a[i-1] * (i - p) >= m * (v - n) + s[i - 2]:
                    ans += 1

print(ans)