Harryxun/stf_run huggingface dataset:
from collections import deque
S = list(map(str,input().split()))
Q = int(input())
Query = [list(map(str,input().split())) for _ in range(Q)]
d = deque(S)
for i in range(Q):
  if Query[i][0] == "1":
    d = d.rotate()
  elif Query[i][0] == "2":
    if Query[i][1] == "1":
      d.append(Query[i][2])
    elif Query[i][1] == "2":
      d.appendleft(Query[i][2])
ans = ''.join(d)
print(ans)

### FIXED CODE ###

from collections import deque
S = str(input())
Q = int(input())
d = deque()
reverse = 1
for i in S:
    d.append(i)
for j in range(Q):
  Query = input().split()
  if len(Query) == 1:
    reverse *= -1
  else:
    F = int(Query[1])
    C = str(Query[2])
    if reverse == 1:
      if F == 1:
        d.appendleft(C)
      elif F == 2:
        d.append(C)
    elif reverse == -1:
      if F == 1:
        d.append(C)
      elif F == 2:
        d.appendleft(C)
if reverse == -1:
    d.reverse()
ans = ''.join(d)
print(ans)
n = int(input())
l = list(map(int, input().split()))

l.sort()

ans = 0
for i+1 in l:
	ans += l[i+1]
    
if l[0] < ans:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
Ls = sorted(map(int, input().split()))
if Ls[-1] < sum(Ls) - Ls[-1]:
    print('Yes')
else:
    print('No')
#n,x=map(int,input().split())
#a=[int(i) for i in input().split()]
import string
alp=string.ascii_lowercase
di={}
for i in range(26):
    di[alp[i]]=i
s=input()
a=[]
for i in s:
    a.append(i)
l=a.pop()
if a:
    a=a[::-1]
k=int(input())
ans=''
i=0
while a:
    t=a.pop()
    d=(26-di[t])%26
    if d<=k:
        k-=d
        #ans+='a'
    else:
        #ans+=t
    i+=1
kk=k%26
#ans+=alp[(alp.index(l)+kk)%26]
print(ans)


### FIXED CODE ###

#n,x=map(int,input().split())
#a=[int(i) for i in input().split()]
import string
alp=string.ascii_lowercase
di={}
for i in range(26):
    di[alp[i]]=i
s=input()
a=[]
for i in s:
    a.append(i)
l=a.pop()
if a:
    a=a[::-1]
k=int(input())
ans=''
i=0
while a:
    t=a.pop()
    d=(26-di[t])%26
    if d<=k:
        k-=d
        ans+='a'
    else:
        ans+=t
    i+=1
kk=k%26
ans+=alp[(alp.index(l)+kk)%26]
print(ans)
import numpy as np  

li = np.array(input().split(" "), dtype=np.int)
li[0], li[1] = li[1], li[0]
li[0], li[2] = li[2], li[0]

print(li[0], li[1], li[2])

### FIXED CODE ###

import numpy as np  

li = np.array(input().split(" "), dtype=np.int)
li[0], li[1] = li[1], li[0]
li[0], li[2] = li[2], li[0]

print(li[0], li[1], li[2])
import math
# 時針の速度
# 360度/720分 = 1/2度/m
# 分針の速度
# 360度/60分 = 6度/m
# 時針と分針の度数は両者を減算したものの絶対値
# 使用するのは余弦定理

# def str_to_int(str_num):
#     int_num = int(str_num)
#     return int_num


line = input().split(' ')
# int_line = list(map(lambda str_num: int(str_num), line))
int_line = [int(str_num) for str_num in line]
# print(int_line)

# 時針の進行角度
# radian_h =　(H * 60 + M) * 0.5
# radian_m = M * 6

# 時針と分針の角度
degree = abs((int_line[2] * 60 + int_line[3]) * 0.5 - int_line[3] * 6)

# 分針と時針の末端同士の距離
distance_squared = int_line[0] ** 2 + int_line[1] ** 2 - 2 * \
    int_line[0] * int_line[1] * math.cos(math.radians(degree))

distance = math.sqrt(distance_squared)

print(distance)


### FIXED CODE ###

num = input()
if num.isdecimal():
    if int(num) <= 999:
        first_class_num = int(num[-1])
        if first_class_num in {2, 4, 5, 7, 9}:
            print("hon")
        elif first_class_num in {0, 1, 6, 8}:
            print("pon")
        elif first_class_num is 3:
            print("bon")
import sys

a=sys.argv[1]
b=sys.argv[2]

print(a*b,a*2+b*2)

### FIXED CODE ###

s = input().split()
a=int(s[0])
b=int(s[1])
print(a*b,a*2+b*2)
N, K = map(int, input().split())
V = list(map(int, input().split()))
INF_MIN = -(10**10)
l = [[INF_MIN] * (K+1) for i in range(N+1)]
r = [[INF_MIN] * (K+1) for i in range(N+1)]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        l[i][0] = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[i-1]
        popV = list(sorted(V[0:i]))
        l[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            l[i][k] = l[i][k-1]
        else:
            l[i][k] = l[i][k-1] - popV[k-1]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[N-i]
        popV = list(sorted(V[N-i:N]))
        r[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            r[i][k] = r[i][k-1]
        else:
            r[i][k] = r[i][k-1] - popV[k-1]

#print(l)
#print(r)

max_val = INF_MIN
imax = min(N, K)
for i in range(imax+1):
    for k in range(K-i+1):
        for j in range(K-i-k+1):
            val = l[i][k] + r[j][K-i-k-j]
            if val > max_val:
                max_val = val
                #print(i, j, k, l[i][k], r[j][K-i-k-j])


print(max_val)


### FIXED CODE ###

N, K = map(int, input().split())
V = list(map(int, input().split()))
INF_MIN = -(10**10)
l = [[INF_MIN] * (K+1) for i in range(N+1)]
r = [[INF_MIN] * (K+1) for i in range(N+1)]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        l[i][0] = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[i-1]
        popV = list(sorted(V[0:i]))
        l[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            l[i][k] = l[i][k-1]
        else:
            l[i][k] = l[i][k-1] - popV[k-1]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[N-i]
        popV = list(sorted(V[N-i:N]))
        r[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            r[i][k] = r[i][k-1]
        else:
            r[i][k] = r[i][k-1] - popV[k-1]

#print(l)
#print(r)

max_val = INF_MIN
imax = min(N, K)
for i in range(imax+1):
    for k in range(K-i+1):
        jmax = min(N-i, K-i-k)
        for j in range(jmax+1):
            val = l[i][k] + r[j][K-i-k-j]
            if val > max_val:
                max_val = val
                #print(i, j, k, l[i][k], r[j][K-i-k-j])


print(max_val)
import sympy as sym #sympyのインポート
def Fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True) #変数xの宣言(非負の整数)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) #一般項の式
    result=Fib.subs(x,n) #xにnを代入
    result=result.evalf() #式を浮動小数点数として評価
    return int(result)
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        for w in newlist:
            ans = (ans*Fib(w))%1000000007
        print(ans)         

### FIXED CODE ###

def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1)%1000000007)
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        #print(newlist)
        for w in newlist:
            #print(Fib(w-1))
            #print(ans)
            ans = (ans*Fib(w-1))%1000000007
        print(ans)
A = input().split()
print({}{}{}.format(A[0],A[1][0],A[2])

### FIXED CODE ###

A = input().split()
print("{}{}{}".format(A[0][0],A[1][0],A[2][0]))
import math

def main():
    n = int(input())
    m = math.sqrt(n)
    m = int(m) if float.is_integer(m) else math.floor(m) - 1
    div = n // m
    # print(m, div)
    print(m-1 + div-1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def main():
    n = int(input())
    m = math.sqrt(n)
    ans = []
    for i in range(1, int(m) + 1):
        div = n / i
        if not float.is_integer(div):
            continue
        ans.append((div+i)-2)

    print(int(min(ans)))


if __name__ == '__main__':
    main()
def calc_prime(N):
    for i in range(3,N+1,2):
        x = int(math.sqrt(i))+1
        j = 0
        prime = True
        while j < len(PrimeList) and PrimeList[j] <= x:
            if i % PrimeList[j] == 0:
                prime = False
                break
            j += 1
        if prime:
            PrimeList.append(i)

calc_prime(55555)
AnsList = []
for p in PrimeList:
    if p % 5 == 1:
        AnsList.append(p)

N = int(input())
for i in range(N):
    print(AnsList[i],end=' ')
print('')

### FIXED CODE ###

import math
PrimeList = [2]

def calc_prime(N):
    for i in range(3,N+1,2):
        x = int(math.sqrt(i))+1
        j = 0
        prime = True
        while j < len(PrimeList) and PrimeList[j] <= x:
            if i % PrimeList[j] == 0:
                prime = False
                break
            j += 1
        if prime:
            PrimeList.append(i)

calc_prime(55555)
AnsList = []
for p in PrimeList:
    if p % 5 == 1:
        AnsList.append(p)

N = int(input())
for i in range(N):
    print(AnsList[i],end=' ')
print('')
import numpy as np
huga = list(map(int, input().split()))
a=huga[0]
b=huga[1]
c=huga[2]
if a>b:
  a=x
  b=a
  a=x

if a<c and b>c:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

import numpy as np
huga = list(map(int, input().split()))
a=huga[0]
b=huga[1]
c=huga[2]
if a>b:
  x=a
  a=b
  b=x
        
      
if a<c and b>c:
  print("Yes")
else:
  print("No")
N, Y = list(map(int, input().split()))
ans = []
for i_yukichi in range(N + 1):
    for j_higuchi in range(N + 1 - i_yukichi):
        k_noguchi = N - i_yukichi - j_higuchi
        if 10000 * i_yukichi + 5000 * j_higuchi + 1000 * k_noguchi == Y:
            ans.append(i_yukichi)
            ans.append(j_higuchi)
            ans.append(k_noguchi)
            break
if len(ans) != 0:
    print(ans[0], ans[1], ans[3])
else:
    print("-1 -1 -1")


### FIXED CODE ###

N, Y = list(map(int, input().split()))
ans = []
for i_yukichi in range(N + 1):
    for j_higuchi in range(N + 1 - i_yukichi):
        k_noguchi = N - i_yukichi - j_higuchi
        if 10000 * i_yukichi + 5000 * j_higuchi + 1000 * k_noguchi == Y:
            ans.append(i_yukichi)
            ans.append(j_higuchi)
            ans.append(k_noguchi)
            break
if len(ans) != 0:
    print(ans[0], ans[1], ans[2])
else:
    print("-1 -1 -1")
import sys

sys.setrecursionlimit(10000)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

x.sort(key = lambda x:x[1])
y.sort(key = lambda x:x[1])

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

p = [i for i in range(n)]

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(2147483647)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

x.sort(key = lambda x:x[1])
y.sort(key = lambda x:x[1])

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

p = [-1]*n

def root(x):
  if p[x]<0:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)
i = int(input())
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[i + 1])

### FIXED CODE ###

i = int(input())
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[i - 1])
import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

max_index=2**N
INF=10**15

dp={}

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    dp[sums] = mon

for j in range(M):
    for i in dp.keys():
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

dp

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

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int leng;
int main()
{
    cin >> s1;
    for(int i = s1.size() - 1; i >= 0; i--)
        s2[leng++] = s1[i];
    for(int i = 0; i < leng; i++)
    {
        if(s1[i]=='b') s2[i] = 'd';
        else if (s1[i] == 'd') s2[i] = 'b';
        else if (s1[i] == 'p') s2[i] = 'q';
        else if (s1[i] == 'q') s2[i] = 'p';
    }
    if(!strcmp(s1,s2)) puts("Yes");
    else puts("No");
    return 0;
}

### FIXED CODE ###

s=input()
d={'b':'d','d':'b','p':'q','q':'p'}
if len(s)%2!=0:
    print("No")
else:
    flag=True
    for idx in range(len(s)//2):
        if d[s[idx]]!=s[-idx-1]:
            print("No")
            flag=False
            break
    if flag:
        print("Yes")
N, K = map(int, input().split())

opes = [0] * (K+1)
for i in range(2**N):
    blue_cnt = 0
    ope_count = 0
    operating = False
    for j in range(N+1):
        bin2str = format(i, '0' + int(N) + 'b')
        if blue_cnt > K:
            break
        elif i == N:
        	if bin2str[:-1:] == 1:
              ope_count += 1
        elif operating and bin2str[j:j+1:] == 0:
            operating = False
            ope_count += 1
        elif !operating and bin2str[j:j+1:] == 1:
            operating = True
            blue_cnt += 1
        elif bin2str[j:j+1:] == 1:
            blue_cnt += 1
    if blue_cnt == K:
        opes[ope_count] += 1
for i in opes[1::]:
    print(i%100000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

nCr = {}
def combination(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = combination(n-1,r) + combination(n-1,r-1)
    return nCr[(n,r)]

N, K = map(int, input().split())
for i in range(1, K+1):
	if i <= N-K+1:
		A = combination(N-K+1, i)
		P = combination(K-1, i-1)
		B = A * P
		print(B % (10**9+7))
	else:
		print(0)
N, K = map(int, input().split());
h = list(map(int, input().split()))
for i in range(N):
  if h[i] >= K:
    ans += 1
print(ans)

### FIXED CODE ###

N, K = map(int, input().split());
h = list(map(int, input().split()))
ans = 0
for i in range(N):
  if h[i] >= K:
    ans = ans + 1
print(ans)
print("Yes"if (int(input())+int(input()))%2==0 else"No")

### FIXED CODE ###

a,b=map(int,input().split());print("Yes"if a%2==b%2==1 else"No")
print('AARBCC'[x<1200::2])

### FIXED CODE ###

print('AARBCC'[int(input())<1200::2])
N = int(input())
C = list(map(int, input().split()))

R_cnt = C.count('R')
x = C[:R_cnt].count('R')

print(R_cnt-x)

### FIXED CODE ###

N = int(input())
C = input()
 
R_cnt = C.count('R')
x = C[:R_cnt].count('R')
 
print(R_cnt-x)
asd = raw_input()
asdd = asd.split()
n = int(asdd[0])
if n == 1:
    print m+1%1000000007
    exit(0)
m = int(asdd[1])
x=(m+1)/(n-1)
print (2*((m+1)*x-x*(n-1)*(x+1)/2)+m+1)%1000000007

### FIXED CODE ###

asd = raw_input()
asdd = asd.split()
n = int(asdd[0])
m = int(asdd[1])
if n == 1:
    print (m+1)%1000000007
    exit(0)

x=(m+1)/(n-1)
print (2*((m+1)*x-x*(n-1)*(x+1)/2)+m+1)%1000000007
from sys import stdin
input = stdin.readline

a,b,n = map(int,input().split())

maxpoint = 0

for i in reversed(range(n+1)):
    tmp = int((a * i) / b)  - a * int(i/b) 
    if i % (b-1) == 0 and b > 1:
        print(tmp) 
        exit()
    maxpoint = max(tmp,maxpoint)

print(maxpoint)





### FIXED CODE ###

from sys import stdin
input = stdin.readline
 
a,b,n = map(int,input().split())
maxpoint = 0
 
if b > n  :
    tmp = int((a * n) / b)  - a * int(n/b) 
    maxpoint = max(tmp,maxpoint)
else:
    k = int(n/b)*b -1
    maxpoint =  int((a * k) / b)  - a * int(k/b) 
    if b == 1:
        maxpoint = 0
 
print(maxpoint)
N, M, C = map(int, input().split)
Blis = [int(x) for x in input().split()]
k = 0
for i in range(N):
  Alis = [int(x) for x in input().split()]
  total = o
  for j in range(M):
    total = total + Alis[j]*Blis[j]
  total = total + C
  if total > 0:
    k = k + 1
print(k)    

### FIXED CODE ###

N, M, C = map(int, input().split())
Blis = [int(x) for x in input().split()]
k = 0
for i in range(N):
  Alis = [int(x) for x in input().split()]
  total = 0
  for j in range(M):
    total = total + (Alis[j])*(Blis[j])
  total = total + C
  if total > 0:
    k = k + 1
print(k)
N, K = map(int, input().split())
l = list(map(int, input().split())
ans = 0
for i in l:
     if i >= K
         ans += 1
print(ans)
    

### FIXED CODE ###

N, K = map(int, input().split())
li = list(map(int, input().split()))
ans = 0
for i in range(N):
  if li[i] >= K:
    ans += 1
print(ans)
N,K = map(int, input().split())

a = N % K
if a == 0:
    print(0)
else:
    print(min(a, abs(a-k)))

### FIXED CODE ###

N,K = map(int, input().split())

a = N % K
if a == 0:
    print(0)
else:
    print(min(a, abs(a-K)))
import heapq
def dijkstra_heap(N,S,edge):
  d = [[float('inf')]*5001 for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*5001 for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=5000 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    u,v,a,b = map(int, input().split())
    edge[u-1].append([b,v-1,-a])
    edge[v-1].append([b,u-1,-a])
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')


### FIXED CODE ###

import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')
n = int(input())
arr = []

z=False
for x in input().split(' '):
    if x == 0:
        z = True
    arr.append(x)
if z == True:
    print(0)

else:
    ans = 1
    for x in arr:
        ans *= x
        if ans > int(1e18):
            print(-1)
    else:
        print(ans)

### FIXED CODE ###

n = int(input())
arr = []

z=False
for x in input().split(' '):
    if x == '0':
        z = True
    arr.append(int(x))
if z == True:
    print(0)

else:
    ans = 1
    for x in arr:
        ans *= x
        if ans > int(1e18):
            print(-1)
            exit(0)
    
    print(ans)
a,b=map(int,input().split())
3 5
x=a*b
y=2*a+2*b
print(x,y)
 

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
bingo = [[],[],[]]
 
for i in range(3):
  a, b, c = map(int,input().split())
  bingo[i].append(a)
  bingo[i].append(b)
  bingo[i].append(c)
  
N = int(input())
if N < 9:
  print("No")
  


### FIXED CODE ###

N = int(input())
print(int((N+1)/2))
import sys
N, B = map(int,input().split())
R = N-B
T = 1000000007
def combination(n, r):
	if r == 0 or r == n:
		return 1
	elif r == 1:
		return n
	else:
		return(combination(n-1, r-1) + combination(n-1, r))
def generating_combination(n):
	T = 1000000007
	C = [[0]*2000]*2000
	C = [1]*(n+1)
	C[0] = [0]
	for i in range(1,n+1):
		C[i] = [1]*(i+1)
		for j in range(1,i):
			C[i][j] = (C[i-1][j-1] + C[i-1][j])%T
	return(C)

C = generating_combination(2000)

i = 1
for i in range(1,B+1):
	print((C[B-1][i-1]*C[R+1][i])%T)
	i += 1

### FIXED CODE ###

import sys
N, B = map(int,input().split())
R = N-B
T = 1000000007
def combination(n, r):
	if r == 0 or r == n:
		return 1
	elif r == 1:
		return n
	else:
		return(combination(n-1, r-1) + combination(n-1, r))
def generating_combination(n):
	T = 1000000007
	C = C = [[0 for i in range(n+1)] for j in range(n+1)]
	C[0][0] = 1
	C[1][0] = 1
	C[1][1] = 1
	for i in range(2,n+1):
		C[i][0] = 1
		C[i][i] = 1
		for j in range(1,i):
			C[i][j] = (C[i-1][j-1] + C[i-1][j])%T
	return(C)

D = generating_combination(2000)
i = 1
for i in range(1,B+1):
	print((D[B-1][i-1]*D[R+1][i])%T)
	i += 1