Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
x = input()

from collections import Counter
cnt1 = Counter( list(x) )['1']
x10 = int(x,2)

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
add_val = 1<<n
for i in range(n):
  add_val = add_val >> 1
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - add_val ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + add_val ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    one_cnt = Counter( list(mod) )['1']
    mod_10 = int(mod,2)
    mod = format( mod_10 % one_cnt, 'b')
    cnt += 1
  print(cnt)
  

### FIXED CODE ###

n = int(input())
x = input()
cnt1 = x.count('1')
x10 = int(x,2)

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
for i in range(n):
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - pow(2,n-1-i,cntx) ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + pow(2,n-1-i,cntx) ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    mod = format( int(mod,2) % mod.count('1'), 'b')
    cnt += 1
  print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[0]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int",c:"int"):
    for j in range(n):
        if a[i][j] and not visited[j]>0:
            visited[j]=1
            if a[i][j]%2==0:
                col[j]=c
            else:
                col[j]=c*-1
            dfs(j, col[j])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1][v-1]=a[v-1][u-1]=d
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int", c:"int"):
    for j in a[i]:
        if not visited[j[0]]:
            visited[j[0]]=1
            if j[1]%2==0:
                col[j[0]]=c
            else:
                col[j[0]]=c*-1
            dfs(j[0], col[j[0]])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1].append([v-1, d])
        a[v-1].append([u-1, d])
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        if dist[i][j] < d:
            continue
        for di, dj in ((-1, 0),  (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 <= dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
                else:
                    break
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        #if dist[i][j] < d:
        #    continue
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
set_s = sorted(set(s))
max_num = 0
for i in set_s:
    max_num = max(max_num, s.count(i))
for i in set_s:
    if s.count(i) == max_num:
        print(i)


### FIXED CODE ###

from collections import Counter
n = int(input())
s = sorted([input() for i in range(n)])

counter = Counter(s)
max_num = max(counter.values())
ans_list = [i for i in counter if counter[i] == max_num]
for i in sorted(ans_list):
    print(i)
### BUGGY CODE ###

import math
n=int(input())
lim=math.ceil(math.sqrt(n))
cnt=0
rec=0

for i in range(lim, n+1):
  if n%i==0:
    print(len(str(i)))
    exit()
  if n%(i+1-lim)==0 and cnt==0:
    rec=n/(i+1-lim)
    cnt+=1
  if i>=rec:
    print(len(str(rec)))
    exit()

### FIXED CODE ###

n=int(input())
l=int((n**0.5))+1
ans=n
for i in range(1, l+1):
  if n%i==0:
    ans=min(ans, len(str(n//i)))
print(ans)
### BUGGY CODE ###

def primes(n):
  tf = [True] * (n + 1)
  tf[0] = tf[1] = False
  for i in range(2, int(n ** (1 / 2)) + 1):
    if tf[i]:
      for j in range(i ** 2, n + 1, i):
        tf[j] = False
  return [i for i in range(n, -1, -1) if tf[i]]

def search_twin(prime_lst):
  prime_lst2 = prime_lst[1:]
  for x, y in zip(prime_lst, prime_lst2):
    if x - y == 2:
      return (y, x)

while True:
  n = int(input())
  if n == 0:
    break
  prime_lst = primes(n)
  print(*search_twin(prime_lst))


### FIXED CODE ###

def primes(n):
  tf = [True] * (n + 1)
  tf[0] = tf[1] = False
  for i in range(2, int(n ** (1 / 2)) + 1):
    if tf[i]:
      for j in range(i ** 2, n + 1, i):
        tf[j] = False
  return [i for i in range(n + 1) if tf[i]]

def add_twin(prime_lst, twin_lst):
  prime_lst2 = prime_lst[1:]
  for x, y in zip(prime_lst, prime_lst2):
    if y - x == 2:
      twin_lst.append(y)

def search_twin(x, twin_lst):
  left = 0
  right = len(twin_lst)
  while left + 1 < right:
    mid = (left + right) // 2
    if twin_lst[mid] > x:
      right = mid
    elif twin_lst[mid] < x:
      left = mid
    else:
      return x
  return twin_lst[left]

prime_lst = primes(10000)
twin_lst = []
add_twin(prime_lst, twin_lst)

while True:
  n = int(input())
  if n == 0:
    break
  a = search_twin(n, twin_lst)
  print(a - 2, a)
### BUGGY CODE ###

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    w, v = map(int, input().split())
    for rj in range(W, w - 1, -1):
        num = DP[rj - w] + v
        if num > DP[rj]:
            DP[rj] = num

print(max(DP))


### FIXED CODE ###

import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))
### BUGGY CODE ###

N,M = map(int, raw_input().split())

P=[]
Y=[]
for i in range(M):
	P_tmp,Y_tmp = map(int, raw_input().split())
	P.append(P_tmp)
	Y.append(Y_tmp)

S={}

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	#print "key: "+key
	try:
		S[key]
	except:
		S[key]=[]
	S[key].append(i)

for i in S.keys():
	S[i]=sorted(S[i])

#print S

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	print "{0:06d}".format(P[Y.index(i)]) + "{0:06d}".format(S[key].index(i)+1)

### FIXED CODE ###

from collections import defaultdict as dd
 
d=dd(int)
n,m=map(int,input().split())
l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]
 
o=sorted(l,key=lambda x:x[2])
for i,j in enumerate(o):
  d[j[1]]+=1
  o[i][3]=d[j[1]]
 
for i in sorted(o):
  print('{0:06d}'.format(i[1])+'{0:06d}'.format(i[3]))
### BUGGY CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            # p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
            p = (2**aindex) + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])


### FIXED CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)
### BUGGY CODE ###

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    if cache.get(x) is not None:
        return cache[x]
    ans = factorial(x)
    cache[x] = ans
    return ans


def choose_combination(n, r):
    if r > n:
        return 0
    return int((fac(n) / fac((n - r))) * (1 / fac(r)))


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    for k_i, k in enumerate(array):
        ways = 0
        for x, count in counts.items():
            adjusted_count = counts[x]
            if x == k:
                adjusted_count -= 1
            ways += choose_combination(adjusted_count, 2)
        print(ways)


N = read_int()
array = read_array()
solve(N, array)


### FIXED CODE ###

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    return factorial(x)


def choose_combination(n, r):
    if r > n:
        return 0
    # return int((fac(n) / fac((n - r))) * (1 / fac(r)))
    # return (fac(n) // fac((n - 2)) * (1 / 2))
    # return fac((n // n - 2)) * (1 / 2))
    return (n * (n-1)) // 2


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    total_ways = 0
    for x, count in counts.items():
        total_ways += choose_combination(counts[x], 2)
    for k in array:
        ways = choose_combination(counts[k] - 1, 2)
        print(total_ways + ways - choose_combination(counts[k], 2))


N = read_int()
array = read_array()
solve(N, array)
### BUGGY CODE ###

#input
N = int(input())
S = str(input())
 
#output
from collections import Counter
answer = 0
if N > 3:
    for i in range(1, N-1):
        if S[i] == "R":
            a = Counter(S[:i])["G"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["G"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "R" and S[i+j] != "R" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "B":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["G"]
            c = Counter(S[:i])["G"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "B" and S[i+j] != "B" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "G":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "G" and S[i+j] != "G" and S[i-j] != S[i+j]:
                    answer -= 1
 
print(answer)

### FIXED CODE ###

#input
N = int(input())
S = str(input())

#output
from collections import Counter
answer = 0
if N > 3:
    for i in range(1, N-1):
        if S[i] == "R":
            a = Counter(S[:i])["G"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["G"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "R" and S[i+j] != "R" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "B":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["G"]
            c = Counter(S[:i])["G"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "B" and S[i+j] != "B" and S[i-j] != S[i+j]:
                    answer -= 1
        elif S[i] == "G":
            a = Counter(S[:i])["R"]
            b = Counter(S[i+1:])["B"]
            c = Counter(S[:i])["B"]
            d = Counter(S[i+1:])["R"]
            answer += a*b + c*d
            for j in range(1, min(i+1, N-i)):
                if S[i-j] != "G" and S[i+j] != "G" and S[i-j] != S[i+j]:
                    answer -= 1

print(answer)
### BUGGY CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
x = []

for i in range(n-k+1):
    x.append(max(l[i:i+k]) - min(l[i:i+k]))

print(min(x))

### FIXED CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
#print(l)
x = []
for i in range(n-k+1):
    x.append(l[i+k-1] - l[i])
x  = sorted(x)
#print(x)

print(min(x[:k-1]))
### BUGGY CODE ###

N, W = map(int, raw_input().split())

w = []
v = []
for i in range(0, N):
    w_i, v_i = map(int, raw_input().split())
    w.append(w_i)
    v.append(v_i)

items = sorted([{'w': w[i], 'v': v[i]} for i in range(0, N)],
               lambda i1, i2: cmp(i2['w'], i1['w']))

def add(i, w_max):
    if i == N:
        return 0;
    if w_max < items[i]['w']:
        return add(i+1, w_max)

    return max(
        add(i+1, w_max),
        add(i+1, w_max - items[i]['w']) + items[i]['v']
    )

print(add(0, W))


### FIXED CODE ###

from collections import defaultdict
N, W = map(int, raw_input().split())

w = []
v = []
for i in range(0, N):
    w_i, v_i = map(int, raw_input().split())
    w.append(w_i)
    v.append(v_i)

items = sorted([{'w': w[i], 'v': v[i]} for i in range(0, N)],
               lambda i1, i2: cmp(i2['w'], i1['w']))

def default():
    return defaultdict(lambda:-1)

results = defaultdict(default)

def add(i, w_max):
    if results[i][w_max] != -1:
        return results[i][w_max]

    if i == N:
        return 0;

    if w_max < items[i]['w']:
        res = add(i+1, w_max)
    else:
        res = max(
            add(i+1, w_max),
            add(i+1, w_max - items[i]['w']) + items[i]['v']
        )
    results[i][w_max] = res
    return res

print(add(0, W))
### BUGGY CODE ###

import sys
S = input()
T = input()
tmp = {}
for i in range(len(S)):
    if S.count(S[i]) > 1:
        if S[i] not in tmp:
            tmp[S[i]] = T[i]
        elif tmp[S[i]] == T[i]:
            pass
        else:
            print("No")
            sys.exit()
tmp = {}
for i in range(len(T)):
    if T.count(T[i]) > 1:
        if T[i] not in tmp:
            tmp[T[i]] = S[i]
        elif tmp[T[i]] == S[i]:
            pass
        else:
            print("No")
            sys.exit()
print("Yes")


### FIXED CODE ###

import sys
S = input()
T = input()
tmp1 = [set() for i in range(26)]
tmp2 = [set() for i in range(26)]
alpha2num = lambda c: ord(c) - ord('a')
for i in range(len(S)):
    tmp1[alpha2num(S[i])].add(T[i])
    tmp2[alpha2num(T[i])].add(S[i])
for i in range(26):
    if len(tmp1[i]) > 1 or len(tmp2[i]) > 1:
        print("No")
        sys.exit()
print("Yes")
### BUGGY CODE ###

def main():
    n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    
    while True:
        i = 0
        max = l[i] + l[i+1]
        if max < x:
            ans += 1
            
        i += 1
        
    print(ans)

main()

### FIXED CODE ###

def main():
    n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    max = 0

    #while True:
        #i = 0
        #max += l[i]
        #if max < x:
            #ans += 1
        #i += 1

    for i in range(len(l)):
        max += l[i]
        if max <= x:
            ans += 1
    print(ans)

main()
### BUGGY CODE ###


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd
from functools import reduce

def lcm(x, y):
  return x * y // gcd(x, y)

L = reduce(lcm, A)

B = [None] * N

for i in range(N):
  B[i] = (L // A[i]) % mod

print(sum(B) % mod)

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd

L = A[0]
for i in range(1,N):
  L=(L*A[i])//gcd(L,A[i])

ans = 0

for i in range(N):
  ans += (L // A[i])

print(ans % mod)
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    return get_par(par[n])

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = i
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(y-y2),i,j))
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    #state = [[1<<61] * (max_m+1) for _ in range(N+1)]
    state = [float('inf') for _ in range(N+1)]
    update = [False for _ in range(N+1)]
    nodes = [0] * N
    #while queue:
    while nodes:
        time, node, coin = heappop(queue)

        if not update[node]:
            state[node] = min(state[node], time)
            update[node] = True
            nodes.pop()

        #if state[node][coin] < time: continue
        #if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
        if coin + C[node] <= max_m:
            #state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            #if coin >= n_coin and state[n_node][coin-n_coin] > n_time + time:
            if coin >= n_coin:
                #state[n_node][coin - n_coin] = n_time + time
                heappush(queue, (time + n_time, n_node, coin - n_coin))

    for s in state[2:]:
        #print(min(s))
        print(s)
if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))