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

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

# representation matrix
A = [[10000 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

# 頂点の訪問状態
color = ['WHITE' for i in range(n)]

# 各頂点がらV\Tに伸びる辺の中で重み最小の値
d = [10000 for i in range(n)]

# MSTにおける各頂点の親と階層
p = [(-1, 0) for i in range(n)]
max_depth = 0
depth_sort = {}
depth_sort[0] = [0]
for i in range(n):
    depth_sort[i] = []


# Prim's algorithm (0-root)
d[0] = 0

while True:
    mincost = 10000
    for i in range(n):
        if color[i] != 'BLACK' and d[i] < mincost: #後者で実質GRAYに制限
            mincost = d[i]
            u = i
            break

    if mincost == 10000:
        break

    color[u] = 'BLACK'
    par, dir = p[u]

    for v in range(n):
        if color[v] != 'BLACK' and A[u][v] < d[v]:
            d[v] = A[u][v] # ここうますぎでは（前のMSTの情報をちゃんと保存してる）
            p[v] = (u, dir + 1)
            depth_sort[dir + 1].append(v)
            max_depth = max(max_depth, dir + 1)
            color[v] = 'GRAY'


# numbers of edges going from each vertices
degree = [0 for i in range(n)]
ans = []

# define directions of the edges other than that of MST
for i in range(n):
    for j in range(i + 1, n):

        if A[i][j] == 1 and p[i][0] != j and p[j][0] != i:
            degree[i] += 1
            ans.append((i, j))


# defining orientations
for dep in range(max_depth, 0, -1):
    for u in depth_sort[dep]:
        par, dir = p[u]
        if degree[u] % 2 == 0:
            degree[par] += 1
            ans.append((par, u))
        else:
            degree[u] += 1
            ans.append((u, par))


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    for pair in ans:
        c, d = pair
        c += 1
        d += 1
        print(' '.join(map(str, [c, d])))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

if m % 2 == 1:
    print(-1)
    exit()



AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].add(v)
        tree[v].add(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()

print('\n'.join(ans))
### BUGGY CODE ###

#coding: utf-8
amount = int(input())
strings = list(map(str, [input() for i in range(amount)]))
sum = 0

for i in range(len(strings)):
	# print(strings[i])
	abc = list(strings[i])
	abc.sort()
	strings[i] = ''.join(abc)
	# print(strings[i])

for j in range(len(strings)):
	for k in range(j+1,len(strings)):
		if strings[j] == strings[k]:
			sum = sum+1

print(sum)


### FIXED CODE ###

#coding: utf-8
amount = int(input())
strings = list(map(str, [input() for i in range(amount)]))
sum = 0
sum2 = 0

for i in range(len(strings)):
	# print(strings[i])
	abc = list(strings[i])
	abc.sort()
	strings[i] = ''.join(abc)
	# print(strings[i])

strings.sort()

for j in range(len(strings)-1):
	# print(j+1)
	# print(strings[j]+strings[j+1])
	if strings[j] == strings[j+1]:
		sum2 = sum2+1
	else:
		sum = sum + sum2 * (sum2+1) / 2
		sum2 = 0

sum = sum + sum2 * (sum2+1) / 2
print(int(sum))
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

x,y,z,k = inpl()
a = inpl()
b = inpl()
c = inpl()
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
q = [[-(a[0] + b[0] + c[0]), 0, 0, 0]]
heapify(q)
old = [(0,0,0)]
for i in range(k):
    k,l,m,n = heappop(q)
    print(-k)
    if l + 1 < x and not (l+1,m,n) in old:
        heappush(q,[-(a[l+1] + b[m] + c[n]), l+1, m, n])
        old.append((l+1,m,n))
    if m + 1 < y and not(l,m+1,n) in old:
        heappush(q,[-(a[l] + b[m+1] + c[n]), l, m+1, n])
        old.append((l,m+1,n))
    if n + 1 < z and not (l,m,n+1)  in old:
        heappush(q,[-(a[l] + b[m] + c[n+1]), l, m, n+1])
        old.append((l,m,n+1))
    # print(q)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

x,y,z,k = inpl()
a = inpl()
b = inpl()
c = inpl()
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
q = [[-(a[0] + b[0] + c[0]), 0, 0, 0]]
heapify(q)
old = set((0,0,0))
for i in range(k):
    k,l,m,n = heappop(q)
    print(-k)
    if l + 1 < x and not (l+1,m,n) in old:
        heappush(q,[-(a[l+1] + b[m] + c[n]), l+1, m, n])
        old.add((l+1,m,n))
    if m + 1 < y and not(l,m+1,n) in old:
        heappush(q,[-(a[l] + b[m+1] + c[n]), l, m+1, n])
        old.add((l,m+1,n))
    if n + 1 < z and not (l,m,n+1)  in old:
        heappush(q,[-(a[l] + b[m] + c[n+1]), l, m, n+1])
        old.add((l,m,n+1))
    # print(q)
### BUGGY CODE ###

R, G, B, N = map(float, input().split())
cnt = 0


def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


for r in range(0, 3000 // int(R) + 1):
    for g in range(0, 3000 // int(G) + 1):
        b = (N - R * r - G * g) / B
        # print(b)
        if b >= 0 and is_integer_num(b):
            # print(r, g, b)
            cnt += 1

print(cnt)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


def main():
    R, G, B, N = map(float, input().split())
    cnt = 0

    for r in range(0, 3000 // int(R) + 1):
        for g in range(0, 3000 // int(G) + 1):
            b = (N - R * r - G * g) / B
            # print(b)
            if b >= 0 and is_integer_num(b):
                # print(r, g, b)
                cnt += 1

    print(cnt)


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

from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = sorted([int(input()) for i in range(Q)])
time = {}
for q in querys:
    time[q] = 0

check_parsed = []
for s, f, x in sorted(check_points, key=itemgetter(2)):
    start, end = [s-x, f-x]
    for q in querys:
        if q < start:
            pass
        elif start <= q < end:
            if time[q] == 0:
                time[q] = x+1
            else:
                pass
        else:
            break

for q in querys:
    print(time[q]-1)


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

n=int(input())

dl_list=[]

for i in range(n):
    cmd=input().split()
    if cmd[0]=="insert":
        dl_list.insert(0,cmd[1])
    elif cmd[0]=="delete":
        try:
            dl_list.remove(cmd[1])
        except:
            pass
    elif cmd[0]=="deleteFirst":
        del dl_list[0]
    elif cmd[0]=="deleteLast":
        del dl_list[-1]

print(*dl_list)

### FIXED CODE ###

from collections import deque
n=int(input())
dq=deque()

for i in range(n):
    cmd=input().split()
    if cmd[0]=="insert":
        dq.appendleft(cmd[1])
    elif cmd[0]=="deleteFirst":
        dq.popleft()
    elif cmd[0]=="deleteLast":
        dq.pop()
    elif cmd[0]=="delete":
        try:
            dq.remove(cmd[1])
        except:
            pass
print(*dq)
### BUGGY CODE ###

W=input()
A=map(int,raw_input().split())
ans=0
for i in xrange(W):
    if A[i]<=0: continue
    lout = A[i]
    if 0 in A[:i]:
        for j in xrange(i-1,-1,-1):
            if A[j]==0:
                break
            elif A[j]<0:
                lout=max(0,min(lout,j-i-A[j]))
                if lout==0: break
    else:
        lout = 0
    rout = A[i]
    if 0 in A[i+1:]:
        for j in xrange(i+1,W+1):
            if A[j]==0:
                break
            elif A[j]<0:
                rout=max(0,min(rout,i-j-A[j]))
                if rout==0: break
    else:
        rout = 0
    ans+=max(lout,rout)
print ans

### FIXED CODE ###

W=input()
A=map(int,raw_input().split())
L=[0]*W
R=[0]*W
now0=-1
for i in xrange(W):
    if A[i]==0:
        now0=i
        nowx=10**6
    if now0==-1: continue
    nowx-=1
    if A[i]<0: nowx=min(nowx,-A[i])
    if A[i]>0: L[i]=min(A[i],nowx)
now0=-1
for j in xrange(W):
    i = W-j-1
    if A[i]==0:
        now0=i
        nowx=10**6
    if now0==-1: continue
    nowx-=1
    if A[i]<0: nowx=min(nowx,-A[i])
    if A[i]>0: R[i]=min(A[i],nowx)
ans=0
for i in xrange(W):
    if max(L[i],R[i])>0: ans+=max(L[i],R[i])
print ans
### BUGGY CODE ###

Ncount = int(input())
strings = []
count_flag = 0
letters_count = []
for i in range(Ncount):
  strings.append(input())
  
def letter_count(string):
  letters = {}
  for i in range(10):
    if string[i] not in letters:
      letters[string[i]] = 1
    else :
      letters[string[i]] += 1
  return letters

for i in strings:
  letters_count.append(letter_count(i))
  
for i in range(len(letters_count)):
  for j in range(i+1, len(letters_count)):
    if letters_count[i] == letters_count[j]:
      count_flag += 1

print(count_flag)

### FIXED CODE ###

Ncount = input()
strings = []
count_flag = 0
letters = {}
for i in range(int(Ncount)):
  strings.append(''.join(sorted(input())))

for i in strings:
  if i not in letters:
    letters[i] = 0
  else :
    letters[i] += 1
    count_flag += letters[i]

print(count_flag)
### BUGGY CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = int(0)
tmp = int(0)
breakPoint = int(0)

if N == 1:
  print("1")

else:
  for i in S:
    tmp = tmp + 1
    for j in range(0,tmp):
      if S[j] >= i:
        continue
      else:
        breakPoint = 1
        break
    if breakPoint == 0:
      counter = counter + 1
    else:
      breakPoint = 0
  print(counter)

### FIXED CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = int(0)
minNum = S[0]

if N == 1:
  print("1")

else:
  for i in range(N):
    if minNum >= S[i]:
      minNum = S[i]
      counter = counter + 1
    
  print(counter)
### BUGGY CODE ###

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

t = 0
for i in range(n - k + 1):
    tmp = p[i: i + k]
    if sum(tmp) >= t:
        t = sum(tmp)
        ans = tmp

cnt = 0
for i in ans:
    cnt += sum(range(1,i + 1)) / i

print(cnt)


### FIXED CODE ###

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

cnt = 0
for i in range(n):
    if i <= k - 1:
        cnt += p[i]
        tmp = cnt
        end = i + 1
    else:
        cnt = cnt - p[i - k] + p[i]
        if cnt >= tmp:
            tmp = cnt
            end = i + 1

ans = 0
L = p[end - k: end]
for i in L:
    ans += sum(range(1, i + 1)) / i

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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

    dp = [[0 for i in range(N)] for j in range(N)]

    for i in range(N):
        dp[i][i] = a[i]

    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            if a[i] - dp[i+1][j] > a[j] - dp[i][j-1]:
                dp[i][j] = a[i] - dp[i+1][j]
            else:
                dp[i][j] = a[j] - dp[i][j-1]
    # print(dp)
    print(dp[0][N-1])


main()


### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

    dp = [[0 for i in range(N)] for j in range(N)]

    for i in range(N):
        dp[i][i] = a[i]

    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            right = a[i] - dp[i+1][j]
            left = a[j] - dp[i][j-1]
            if right > left:
                dp[i][j] = right
            else:
                dp[i][j] = left
    # print(dp)
    print(dp[0][N-1])


main()
### BUGGY CODE ###

import collections
d = collections.deque()

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
for _ in range(K):
    d.append(A[_])


for i in range(K,N):
    sum_1 = sum(d)
    d.popleft()
    d.append(A[i])
    sum_2 = sum(d)
    if sum_1 < sum_2: print('Yes')
    else: print('No')

### FIXED CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
for i in range(K,N):
    a = A[i-K]
    b = A[i]
    if a<b: print('Yes')
    else: print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(n - 1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

graph = [[] for _ in range(n + 1)]

for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

def dfs(v, parent, add):
	value[v] += add
	for x in graph[v]:
		if x == parent:
			continue
		dfs(x, v, value[v])

dfs(1, 0, 0)
print(*value[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, q = map(int, input().split())

AB = [[int(x) for x in input().split()] for _ in range(n - 1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

graph = [[] for _ in range(n + 1)]
# 各ノードと連結するノードを要素に持つ配列
# e.g., graph[1] -> ノード１と連結するノードを要素に持つ
for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

# 根に点数を入れる
value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

# 根から値を流す
q = [(1, 0)]
while q:
	x, parent = q.pop() # (1, 0)
	value[x] += value[parent]
	# 連結する成分について繰り返す
	# このとき、親のノードに流さないように注意
	# ここでの操作は、自分の子のノードを加えること
	for y in graph[x]:
		if y == parent:
			continue
		q.append((y, x)) #(親,子)

res = ' '.join(map(str, value[1:]))
print(res)
### BUGGY CODE ###

n = int(input())
print(0, flush=True)
f, m = "Female", "Male"
x = 0 if input() == f else 1
high = n-1
low = 0
while high - low > 1:
    mid = (high + low) // 2
    print(mid, flush=True)
    s = input()
    if s == "Vacant":
        quit()
    if mid == x:
        if s == f:
            low = mid
        else:
            high = mid
    else:
        if s == f:
            high = mid
        else:
            low = mid
print(high, flush=True)
quit()

### FIXED CODE ###

import sys
n = int(input())
print(0, flush=True)
f, m = "Female", "Male"
s = input()
if s == "Vacant":
    quit()
x = 0 if s == f else 1
high = n-1
low = 0
while high - low > 1:
    mid = (high + low) // 2
    print(mid, flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    if mid % 2 == x:
        if s == f:
            low = mid
        else:
            high = mid
    else:
        if s == f:
            high = mid
        else:
            low = mid
print(high, flush=True)
sys.exit()
### BUGGY CODE ###

def main():
    n = int(input())
    
    l1 = l2 = l3 = 0
    for i in map(int,input().split()):
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

    dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,l2+l3)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n
                if s > 0:
                    count += dp[s-1][t][k]*s
                    
                if t > 0 :
                    count += dp[s+1][t-1][k]*t
                if k > 0 :
                    count += dp[s][t+1][k-1]*k

                count *= 1/(s+t+k)
                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()



### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

s=str(input())
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
ans=s
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans=l[i][2]+ans
			else:
				ans=ans+l[i][2]
		else:
			if l[i][1]=='2':
				ans=l[i][2]+ans
			else:
				ans=ans+l[i][2]
if c%2==1:
	ans=ans[::-1]
print(ans)





### FIXED CODE ###

from collections import deque
ans=deque()
ans.append(str(input()))
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
		else:
			if l[i][1]=='2':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
A="".join(map(str,list(ans)))
if c%2==1:
	print(A[::-1])
else:
	print(A)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nが小さいのでdfs
N, M = lr()
keys = [None] * (M+1) # 1-indexed
for i in range(M):
    a, b = lr()
    c = set(lr())
    keys[i+1] = (a, c)

def dfs(m, fee, open):
    global answer
    if m == M+1:
        if len(open) == N:
            answer = min(answer, fee)
    else:
        new_box = keys[m][1]
        if len(new_box - open) > 0:
            dfs(m+1, fee+keys[m][0], open.union(keys[m][1]))
        dfs(m+1, fee, open)

INF = 10 ** 10
answer = INF
dfs(1, 0, set())
print(-1 if answer == INF else answer)
# 38

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    b_cnt = 2 ** N #箱の数は最大12個
    INF = 10 ** 9
    dp = [INF] * b_cnt
    dp[0] = 0

    for i in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (int(x)-1) for x in list(input().split())])
        for j in range(b_cnt):
            if dp[j|c] > dp[j] + a:
                dp[j|c] = dp[j] + a

    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

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

def main():
    n = int(input())
    p = list(map(int, input().split()))
    lst = []
    for i in range(n):
        flg = True
        for j in range(i):
            if p[i] > p[j]:
                flg = False
        if flg:
            lst.append(i)

    print(len(lst))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    count = 0
    min_num = n+1
    for i in p:
        if i < min_num:
            min_num = i
            count += 1
    print(count)


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

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq
  inf=pow(10,20)*5
  #dp=[[inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  #dp[0][min(s,100*51-1)]=0
  from collections import defaultdict
  dp=defaultdict(lambda:inf)
  dp[(0,min(s,100*51-1))]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[(v,j)]=min(dp[(v,j)],dp[(v,i)]+d)
      heapq.heappush(todo,[dp[(v,j)],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[(u,i-a)]=min(dp[(u,i-a)],dp[(v,i)]+b)
        heapq.heappush(todo,[dp[(u,i-a)],u,i-a])
  print(*ans[1:],sep='\n')

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = str(input())
MOD = 1000000007

dp = [0 for i in range(13)]
dp[0] = 1
for i in range(0, len(S)):
    next_dp = [0 for i in range(13)]
    if S[len(S) - i - 1] == '?':
        for k in range(10):
            for j in range(13):
                add = k * pow(10,i) % 13
                next_dp[(j + add) % 13] += dp[j]
                next_dp[(j + add) % 13] %= MOD
    else:
        for j in range(13):
            add = int(S[len(S) - i - 1]) * pow(10,i) % 13
            next_dp[(j + add) % 13] = dp[j]
            next_dp[(j + add) % 13] %= MOD
    dp = next_dp

print(dp[5] % MOD)




### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

print(dp[5])