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

import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    A = string_to_int(inputs[0])
    odd_count = 0
    count = -1
    while odd_count < len(A):
        odd_count = 0
        first_even_i = -1
        count += 1
        for i in range(len(A)):
            if A[i] % 2 == 0:
                if first_even_i == -1:
                    first_even_i = i
            elif A[i] % 2 == 1:
                odd_count += 1
        if first_even_i != -1:
            A[first_even_i] /= 2
    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)


### FIXED CODE ###

import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    A = string_to_int(inputs[0])
    odds = []

    for a in A:
        if a % 2 == 0:
            odds.append(a)
    count = 0
    for o in odds:
        while o % 2 != 1:
            o /= 2
            count += 1

    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    N,K = map(int, input().split())
    H = list(map(int, input().split()))

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i,h in enumerate(H):
        if i == 0:
            continue
        m = max(0, i-K)
        for j in range(i-1, m-1, -1):
            dp[i] = min(dp[i], dp[j] + abs(h - H[j]))
    print(dp[N-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N,K = map(int, input().split())
    H = list(map(int, input().split()))

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i,h in enumerate(H):
        if i == 0:
            continue
        m = max(0, i-K)
        # 普通なら j=i~m のループを回すが、高速化のためこうする（配列アクセスを減らす）
        dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
    print(dp[N-1])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

used = [False] * N
def solve(index, cur_elem, cost, cur_min):
    #print(" " * index, cur_elem, cost, cur_min)
    for i in range(N):
        if used[i]:
            continue

        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                new_cost = cost
                for j in range(i, N):
                    if used[j]:
                        new_cost += 1
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, A[i], new_cost, cur_min))
                        used[i] = False
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if used[j]:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, B[i], new_cost, cur_min))
                        used[i] = False
    return cur_min

ans = solve(0, -1, 0, 100000)
if ans == 100000:
    print(-1)
else:
    print(ans)



### FIXED CODE ###

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

dp = [[100100] * (1 << N) for _ in range(N)]
for i in range(N):
    dp[i][1 << i] = 0
for mask in range(1, 1 << N):
    mask_pop = format(mask, 'b').count('1')
    for j in range(N):
        if (1 << j) & mask:
            if (j - mask_pop) % 2 == 1:
                cur_elem = A[j]
            else: 
                cur_elem = B[j]
            prev_mask = mask & ~(1 << j)
            cost_delta = format(prev_mask & (-1 << j), 'b').count('1')
            for t in range(N):
                if (1 << t) & prev_mask:
                    prev_elem = A[t] if (t - mask_pop - 1) % 2 == 1 else B[t]
                    if prev_elem <= cur_elem:
                        if dp[j][mask] > dp[t][prev_mask] + cost_delta:
                            dp[j][mask] = dp[t][prev_mask] + cost_delta
            
# print(*dp, sep = '\n')

ans = min((dp[i][-1] for i in range(N)))
if ans == 100100:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

ans = 1
for i in range(1, N):
    count = 0
    for j in range(i):
        if P[i] <= P[j]:
            count += 1
    if count == i:
        ans += 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

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

    ans = 1
    m = P[0]
    for i in range(1, N):
        if P[i - 1] < m:
            m = P[i - 1]
        if m >= P[i]:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
charar = input()
charlist = []
while not all([x==charar[0] for x in charar]):
    for i in range(len(charar)-1):
        if charar[i] != charar[i+1]:
            charlist.append(charar[:i+1])
            charar = charar[i+1:]
            break
print(len(charlist)+1)

### FIXED CODE ###

n = int(input())
charar = input()
sum = 0
for i in range(len(charar) - 1):
    if charar[i] != charar[i + 1]:
        sum +=1
print(sum+1)
### BUGGY CODE ###

N = int(input())

# Nの階乗を計算する
factorial = [1] * (N+1)
mod = 10 ** 9 + 7
for i in range(1, N+1):
    factorial[i] = i * factorial[i - 1]
    
#print(factorial)

n = factorial[-1]
#print(n)

ans =0

# 割り切れる数を探す。
for i in range(1, n+1):
    if n%i ==0:
        ans +=1

print(ans)

### FIXED CODE ###

import math

n=int(input())
mod = 10**9+7

def get_sieve_of_eratosthenes(n):
    if n==1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

# エラトステネスの篩を使い、素数のリストを作る
E=get_sieve_of_eratosthenes(n)
# 素数の数を数える
l=len(E)
#print("len(e): ",l)

# カウンタ
co=1
# 0から素数までの値で、nを何回割れるかを数える
for e in E:
    co_sub=1
    # 対数。n=25,e=5の時,2を返す(5**"2"==25)
    l_sub=int(math.log(n,e))
    # 対数の数だけ繰り返す
    for j in range(1,l_sub+1):
        # 割れる回数をカウンタに追加
        co_sub+=n//(e**j)
    co*=co_sub
    # 大きすぎるのでmodのあまりにする
    co%=mod
    #print(co_sub)
print(co)
### BUGGY CODE ###

def solve(X, xs):
    divs = range(1, int(10 ** 4.5) + 1)
    def divisors(X, smaller_only=False):
        fwd, bwd = [], []
        for p in divs:
            if X % p == 0:
                fwd.append(p)
                if not smaller_only and X // p != p:
                    bwd.append(X // p)
        bwd.reverse()
        return fwd + bwd

    s = None
    for x in xs:
        ds = set(divisors(abs(x - X)))
        if s:
            s &= ds
        else:
            s = ds
    return max(s)

def test():
    print(solve(1, [2 ** i for i in range(30)]))

if __name__=='__main__':
    N, X = map(int, input().split())
    xs = map(int, input().split())

    print(solve(X, xs))


### FIXED CODE ###

try:
    from math import gcd # >=Python 3.5
except:
    from fractions import gcd # <Python 3.5 (AtCoder : 3.4)

def solve(X, xs):
    xs = list(xs) + [X]
    xs.sort()
    zs = [x - xs[0] for x in xs]

    for z in zs:
        if z == 0:
            D = z
        else:
            D = gcd(D, z)
    return D

def test():
    print(solve(13, [16 + 3 * 102485 * i for i in range(10**5)]))

if __name__=='__main__':
    N, X = map(int, input().split())
    xs = map(int, input().split())

    print(solve(X, xs))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = {}
for i in range(N):
  if a[i] in cnt.keys():
	  cnt[a[i]] += 1
  else:
      cnt[a[i]] = 1

ans = 0
for i in cnt:
  if cnt[i] > int(i):
      ans += cnt[i] - int(i)
  elif int(i) > cnt[i]:
      ans += cnt[i]

print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)

ans = 0
for i in cnt:
  if cnt[i] > int(i):
      ans += cnt[i] - int(i)
  elif int(i) > cnt[i]:
      ans += cnt[i]

print(ans)
### BUGGY CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

n, m, s, t =  map(int,input().split())
E = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [d1[v]+d2[v] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(d[i+1:]))

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    N, Q = (int(i) for i in input().split())
    A = [0] + [int(i) for i in input().split()]

    cum = [0] + [a for a in accumulate(A[1:])]
    cum_e = [e for e in accumulate(A[(1 if N & 1 else 0)::2])]

    def binary_search(x):
        ng = 0
        ok = N
        while ok - ng > 1:
            mid = ng + (ok - ng) // 2
            if A[mid] < x:
                ng = mid
            else:
                upper = N - mid + 1
                lower = mid - bisect_left(A, max(1, 2*x-A[mid])) + 1
                if upper > lower:
                    ng = mid
                else:
                    ok = mid
        return ok
    # print(cum, cum_e)
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        # print(ok, t)
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    A = [0] + [int(i) for i in input().split()]

    cum = [0] + [a for a in accumulate(A[1:])]
    cum_e = [e for e in accumulate(A[(1 if N & 1 else 0)::2])]

    def binary_search(x):
        ng = 0
        ok = N
        while ok - ng > 1:
            mid = ng + (ok - ng) // 2
            if A[mid] < x:
                ng = mid
            else:
                upper = N - mid + 1
                lower = mid - bisect_left(A, max(1, 2*x-A[mid])) + 1
                if upper > lower:
                    ng = mid
                else:
                    ok = mid
        return ok
    # print(cum, cum_e)
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        # print(ok, t)
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
n = int(input())

dic = {}
for _ in range(n):
    s = input()
    dic[s] = dic.get(s, 0) + 1

c = collections.Counter(dic)

print("\n".join(sorted([ k for k,v in c.items() if v == max(c.values()) ])))

### FIXED CODE ###

import collections
n = int(input())

c = {}
for _ in range(n):
    s = input()
    c[s] = c.get(s, 0) + 1

u = max(c.values())
print("\n".join(sorted([ k for k,v in c.items() if v == u ])))
### BUGGY CODE ###

import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
l = na()
l.sort(reverse=True)
c = 0
for ll in range(n):
    for lm in range(ll+1, n):
        for lr in range(lm+1, n):
            if l[ll] < l[lm] + l[lr]:
                c += 1

print(c)

### FIXED CODE ###

import sys
import math
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
l = na()
l.sort()


c = 0
for i_1 in range(n-2):
    for i_2 in range(i_1+1, n-1):
        m = l[i_1] + l[i_2]
        i_3max = bisect.bisect_left(l, m) - 1
        c += i_3max - i_2

print(c)
### BUGGY CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))


### FIXED CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))
### BUGGY CODE ###

mod = 10 ** 9 + 7
s = input()
l = len(s)
dp =[[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] =1
for i in range(l):
    obj =s[l - i - 1]
    if obj == "?":
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * (10 ** i) + k) % 13] +=dp[i][k] % mod
    else:
        for k in range(13):
            dp[i + 1][(int(obj) * (10 ** i) + k) % 13] +=dp[i][k] % mod
print(dp[-1][5] % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0]=1
for i in range(n):
    if s[i] == '?': 
        for j in range(10):
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13]+=dp[i][k] % mod
    else:
        for k in range(13): 
            dp[i + 1][(k * 10+ int(s[i])) % 13]+=dp[i][k] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = heappop(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    heappush(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    heappush(q, (cnt+1, nh, nw))
    return -1

print(main())


### FIXED CODE ###

from collections import deque
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, sh-1, sw-1))
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = deque.popleft(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    deque.appendleft(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    deque.append(q, (cnt+1, nh, nw))
    return -1

print(main())
### BUGGY CODE ###

from collections import defaultdict
N,M=map(int,input().split())
x=defaultdict(list)
for i in range(N):
    a,b=map(int,input().split())
    x[a].append(b)
y=[]
an=0
for i in range(M+1):
    y+=x[i]
    try:
        an+=max(y)
        y.remove(max(y))
    except:
        pass
print(an)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
x={}
for i in range(M+1):
    x[i]=[]
for i in range(N):
    a,b=map(int,input().split())
    if a>M:
        continue
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    for n in x[i]:
        heapq.heappush(y,n)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)
### BUGGY CODE ###

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

length = N
amount = 0
for i in range(length-1):
  for j in range(i+1, length):
    num1 = num_list[i]
    num2 = num_list[j]
    bit_num1 = format(num1, "b")
    bit_num2 = format(num2, "b")
    length_num1 = len(bit_num1)
    length_num2 = len(bit_num2)
    max_length = max(length_num1, length_num2)
    bit_num1 = bit_num1.zfill(max_length)
    bit_num2 = bit_num2.zfill(max_length)       
    num = ""
    for k in range(1, max_length+1):
      if int(bit_num1[-k]) and not int(bit_num2[-k]):
        num = "1" + num
      elif not int(bit_num1[-k]) and int(bit_num2[-k]):
        num = "1" + num
      else:
        num = "0" + num
    amount += int(num, 2) % (10**9 + 7)

L = 10**9 + 7
print(amount % L)

### FIXED CODE ###

import numpy as np
N = int(input())
num_list = np.array(input().split(), dtype="int")

max_num = max(num_list)
max_bit_num = format(max_num, "b")
max_bit_num_length = len(max_bit_num)
ans = 0
radix = 1
for i in range(max_bit_num_length):
  new_num_list = (num_list >> i) & 1
  one_amount = np.count_nonzero(new_num_list == 1)
  zero_amount = len(num_list) - one_amount
  ans += (one_amount*zero_amount)*radix
  radix *= 2
print(ans%(10**9+7))
### BUGGY CODE ###

def resolve():
    a, b = map(int, input().split())
    save_result = []
    append_f = save_result.append
    append_f(a)
    while True:
        a = a - b
        if a < 0:
            abs_s = abs(a)
            append_f(abs_s)
            break
        else:
            append_f(a)

    print(min(save_result))

resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    print(min(n, n % k, abs(n % k - k)))

resolve()
### BUGGY CODE ###

import heapq
from collections import defaultdict

n, m, s = map(int, input().split())

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

### FIXED CODE ###

import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

n, m, s = map(int, input().split())

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))