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

def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*2*n 
  for i,c in enumerate(input()[:-1],n):
    data[i]=2**(c-97)
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:
      l,r=int(a)+n-1,int(b)+n
      s=0
      while l<r:
        if l&1:
          s|=data[l]
          l+=1
        if r&1:
          r-=1
          s|=data[r]
        l//=2
        r//=2
      print(sum(1for i in range(26)if s&2**i))
    else:
      i=int(a)+n-1
      data[i]=2**(b[0]-97)
      i//=2
      while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if N % 2 == 0:
    
    for i in list(range(1, N, 2)):
        if 1 <= A.count(i) <= 2:
            ans = ans*A.count(i)
        else:
            ans = 0
            break
else:
    if A.count(0) == 1:
        
        for i in list(range(0, N, 2)):
            if 1 <= A.count(i) <=2:
                ans = ans*A.count(i)
            else:
                ans = 0
                break
    else:
        ans = 0

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if N % 2 == 0:
    if len(A) != 2*len(set(A)):
        ans = 0
else:
    if A.count(0) == 1:
        A.remove(0)
        if len(A) != 2*len(set(A)):
            ans = 0
    else:
        ans = 0
if ans == 0:
    print(0)
else:
    print((2**(N//2))%(10**9+7))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
data = input()
data = data.split()
x = int(data[0])
y = int(data[1])

def gcd(n,m):
    k = max(n,m)
    for i in range(k):
        if n%(k-i) == 0 and m%(k-i) == 0:
            return k-i

print(gcd(x,y))

### FIXED CODE ###

# -*- coding:utf-8 -*-
def gcd(n,m):
    if n < m:
        tmp = m
        m = n
        n = tmp
    while m > 0:
        r = n % m
        n = m
        m = r
    return n
    
x, y = map(int,input().split())
print(gcd(x,y))
### BUGGY CODE ###


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

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    # check(1, data, max_length, num, 0, data[0], 0)
    # check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print((ans_num * 3) % 998244353)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
### BUGGY CODE ###

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

def cf(x1,x2):
    cf =[]
    cf.append(1)
    for i in range(2, min(x1,x2)+1):
        if x1 %i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

ans = 1
temp = cf(a,b)
for i in temp:
    if is_prime(i):
        ans += 1

print (ans)



### FIXED CODE ###

#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

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

from math import gcd
k = int(input())
 
sum = 0
for x1 in range(1,k+1):
  for x2 in range(1,k+1):
    for x3 in range(1,k+1):
        ans = gcd(x3,gcd(x1,x2))
        sum += ans
 
print(sum)


### FIXED CODE ###

import fractions
k = int(input())

l = [[-1 for _ in range(k+1)] for _ in range(k+1)]

for i in range(1,k+1):
  for j in range(1,k+1):
     if l[i][j] == -1:
        ans = fractions.gcd(i,j)
        l[i][j] = ans
        l[i][i] = ans
sum = 0
#1種類
for i in range(1,k+1):
  sum += i
#２種類
for i in range(1,k):
  for j in range(i+1,k+1):
    sum += l[i][j]*6

#3種類
for i in range(1,k-1):
  for j in range(i+1,k):
    for m in range(j+1,k+1):
      sum += l[l[i][j]][m]*6

print(sum)
### BUGGY CODE ###

n = int(input())
s = input()

a = ['SS','SW','WS','WW']

for j in range(len(a)):
    for i in range(1,n-1):
        if s[i]=='x':
            if a[j][i]==a[j][i-1]:
                a[j]+='W'
            else:
                a[j]+='S'
        else:
            if a[j][i]==a[j][i-1]:
                a[j]+='S'
            else:
                a[j]+='W'
    flag = 0
    if (s[-1] == 'x' and a[j][-1]=='S') or (s[-1] == 'o' and a[j][-1]=='W'):
        if a[j][-2] != a[j][0]:
            flag += 1
    else:
        if a[j][-2] == a[j][0]:
            flag += 1
    if (s[0] == 'x' and a[j][0]=='S') or (s[0] == 'o' and a[j][0]=='W'):
        if a[j][-1] != a[j][1]:
            flag += 1
    else:
        if a[j][-1] == a[j][1]:
            flag += 1
    if flag == 2:
        print(a[j])
        exit()

print(-1)


### FIXED CODE ###

n = int(input())
s = input()

a = ['SS','SW','WS','WW']

for j in range(len(a)):
    for i in range(1,n-1):
        if s[i]=='x':
            if a[j][i]==a[j][i-1]:
                a[j]+='W'
            else:
                a[j]+='S'
        else:
            if a[j][i]==a[j][i-1]:
                a[j]+='S'
            else:
                a[j]+='W'
    flag = 0
    if (s[-1] == 'x' and a[j][-1]=='S') or (s[-1] == 'o' and a[j][-1]=='W'):
        if a[j][-2] != a[j][0]:
            flag += 1
    else:
        if a[j][-2] == a[j][0]:
            flag += 1
    if (s[0] == 'x' and a[j][0]=='S') or (s[0] == 'o' and a[j][0]=='W'):
        if a[j][-1] != a[j][1]:
            flag += 1
    else:
        if a[j][-1] == a[j][1]:
            flag += 1
    if flag == 2:
        print(a[j])
        exit()

print(-1)
### BUGGY CODE ###

S = input()

dp = [[0 for _ in range(4)]for _ in range(len(S)+1)]
dp[0][0] = 1

for ind,i in enumerate(S):
    if(i!='?'):
        dp[ind+1][0] = dp[ind][0]
        dp[ind+1][1] = dp[ind][1]
        dp[ind+1][2] = dp[ind][2]
        dp[ind+1][3] = dp[ind][3]
        if(i=='A'):
            dp[ind+1][1] += dp[ind][0]
        elif(i=='B'):
            dp[ind+1][2] += dp[ind][1]
        elif(i=='C'):
            dp[ind+1][3] += dp[ind][2]
    else:
        dp[ind+1][0] = dp[ind][0]*3
        dp[ind+1][1] = dp[ind][1]*3 + dp[ind][0]
        dp[ind+1][2] = dp[ind][2]*3 + dp[ind][1]
        dp[ind+1][3] = dp[ind][3]*3 + dp[ind][2]


print(dp[-1][3]%(10**9+7))


### FIXED CODE ###

S = input()

MOD = 10**9+7
dp = [[0 for _ in range(4)]for _ in range(len(S)+1)]
dp[0][0] = 1

for ind,i in enumerate(S):
    if(i=='A'):
        dp[ind+1][0] = dp[ind][0]
        dp[ind+1][1] = dp[ind][1] + dp[ind][0]
        dp[ind+1][2] = dp[ind][2]
        dp[ind+1][3] = dp[ind][3]
    elif(i=='B'):
        dp[ind+1][0] = dp[ind][0]
        dp[ind+1][1] = dp[ind][1]
        dp[ind+1][2] = dp[ind][2] + dp[ind][1]
        dp[ind+1][3] = dp[ind][3]
    elif(i=='C'):
        dp[ind+1][0] = dp[ind][0]
        dp[ind+1][1] = dp[ind][1]
        dp[ind+1][2] = dp[ind][2]
        dp[ind+1][3] = dp[ind][3] + dp[ind][2]
    else:
        dp[ind+1][0] = dp[ind][0]*3
        dp[ind+1][1] = dp[ind][1]*3 + dp[ind][0]
        dp[ind+1][2] = dp[ind][2]*3 + dp[ind][1]
        dp[ind+1][3] = dp[ind][3]*3 + dp[ind][2]
        
    dp[ind+1][0]%=MOD
    dp[ind+1][1]%=MOD
    dp[ind+1][2]%=MOD
    dp[ind+1][3]%=MOD

print(dp[-1][3]%MOD)
### BUGGY CODE ###

N,M=map(int,input().split())
n = N
import math
sq = math.sqrt(M)
while n<M :
    if M%n == 0:
        g = M//n
        print(g)
        exit()
    else:
        n += 1
print(1)



### FIXED CODE ###

N,M=map(int,input().split())
import math
s = math.sqrt(M)
sq = math.floor(s)
l = []
for i in range(1,sq+1):
    if M%i == 0:
        l.append(i)
        l.append(M//i)
ans = 1
for r in l:
    n = M//r
    if n >= N:
        ans = max(ans,r)
print(ans)
### BUGGY CODE ###

from queue import Queue
INF = 99999999999999999


H, W = map(int, input().split())
S = [input() for x in range(H)]


def m_distance(si, sj):
    if (S[si][sj] == '#'):
        return -INF
    
    q = Queue()
    q.put((si, sj, 0))
    done = [[False] * W for x in range(H)]

    m = 0
    unit = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while not q.empty():
        i, j, w = q.get()
        done[i][j] = True
        

        for u in unit:
            nexti = i + u[0]
            nextj = j + u[1]
            if nexti >= 0 and nexti < H and nextj >= 0 and nextj < W and S[nexti][nextj] == '.' and (not done[nexti][nextj]):
                q.put((nexti, nextj, w+1))
                m = max(m, w+1)

    return m

m = 0
for i in range(H):
    for j in range(W):
        m = max(m, m_distance(i, j))
print(m)

### FIXED CODE ###

from queue import Queue
INF = 999999


H, W = map(int, input().split())
S = [input() for x in range(H)]

m = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '#':
            continue
        
        q = Queue()
        q.put((si, sj, 0))
        done = [None] * H
        for i in range(H):
            done[i] = [False] * W
        done[si][sj] = True

        unit = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while not q.empty():
            i, j, w = q.get()

            for u in unit:
                nexti = i + u[0]
                nextj = j + u[1]
                if nexti >= 0 and nexti < H and nextj >= 0 and nextj < W and S[nexti][nextj] == '.' and (not done[nexti][nextj]):
                    q.put((nexti, nextj, w+1))
                    m = max(m, w + 1)
                    done[nexti][nextj] = True
print(m)
### BUGGY CODE ###

s=input()
n=len(s)

dp=[[0]*13 for i in range(n)]
m=[0]*(n-1)+[1]
for i in range(n-1):
    m[-i-2]=m[-i-1]*10%13

if s[0]!='?':
    a=int(s[0])*m[0]%13
    dp[0][a]=1
else:
    for k in range(10):
        a=k*m[0]%13
        dp[0][a]=1

for i in range(1,n):
    if s[i]!='?':
        for j in range(13):
            dp[i][j]=dp[i-1][(j-int(s[i])*m[i])%13]
    else:
        for k in range(10):
            for j in range(13):
                dp[i][j]+=dp[i-1][(j-k*m[i])%13]
print(dp[n-1][5]%(10**9+7))

### FIXED CODE ###

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

N = int(input())
dp = [0 for i in range(N)]
dp[0] = ''.join(sorted(list(input())))
ans = 0
for i in range(1, N):
    dp[i] = ''.join(sorted(list(input())))
    for j in range(i):
        if dp[j] == dp[i]:
            ans += 1
print(ans)

### FIXED CODE ###

n=int(input())
S=[''.join(sorted(input())) for i in range(n)]
c=0
dict={}
for s in S:
  if s in dict:
    c+=dict[s]
    dict[s]+=1
  else:
    dict[s]=1
print(c)
### BUGGY CODE ###


import itertools
import math
import copy

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


pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    sticks = sorted(sticks)
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        min_cost_connect = connect(copied_sticks, A, B, C)
        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost

sticks = []
for _ in range(N):
    sticks.append(int(input()))

min_cost = connect(sticks, C, B, A)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)



### FIXED CODE ###


import itertools
import math
import copy

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

pattern = [list(itertools.combinations(range(x), 3)) for x in range(3, N+1)]

def stretch_shortening(sticks, A, B, C):
    min_cost = 1e10
    
    for i1, i2, i3 in pattern[len(sticks) - 3]:
        cost = abs(sticks[i1] - A) + abs(sticks[i2] - B) + abs(sticks[i3] - C)
        if min_cost > cost:
            min_cost = cost
    return min_cost

temp_set = set()
def connect(sticks, A, B, C):
    
    min_cost = stretch_shortening(sticks, A, B, C) + (N - len(sticks)) * 10
    
    if len(sticks) <= 3:
        return min_cost
    
    for i1, i2 in itertools.combinations(range(len(sticks)), 2):
        if sticks[i1] + sticks[i2] > sticks[-1] and sticks[-1] >= C:
            continue
        if sticks[i1] <= 10 or sticks[i2] <= 10:
            continue
        
        copied_sticks = copy.copy(sticks)
        copied_sticks[i1] += copied_sticks[i2]
        copied_sticks.pop(i2)
        copied_sticks = sorted(copied_sticks)
        
        len_set = len(temp_set)
        temp_set.add(''.join(["{:05d}".format(x) for x in copied_sticks]))
        if len_set == len(temp_set):
            continue
        
        min_cost_connect = connect(copied_sticks, A, B, C)

        if min_cost_connect < min_cost:
            min_cost = min_cost_connect
    
    return min_cost

sticks = []
for _ in range(N):
    sticks.append(int(input()))
sticks = sorted(sticks)

min_cost = connect(sticks, C, B, A) #, 1e10)
#min_cost = stretch_shortening(sticks, A, B, C)
#print(pattern)

print(min_cost)
### BUGGY CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

sub = -1000000000
for i in range(len(a)):
    for j in range(len(b)):
        if j >= i:
            sub = max(sub,b[j]-a[i])
print(sub)




### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
### BUGGY CODE ###

n,c,k=map(int,input().split())
a=sorted([int(input()) for _ in range(n)],reverse=True)
cnt=0
while len(a) > 0:
    b=a.pop()
    cnt+=1
    if len(a)==0:
        break
    for i in range(c-1):
        if a[-1]<=b+k:
            a.pop()
            if len(a)==0:
                break
        
print(cnt)
    

### FIXED CODE ###

n,c,k=map(int,input().split())
a=sorted([int(input()) for _ in range(n)],reverse=True)
cnt=0
cnt2=1
while len(a) > 0:
    b=a.pop()
    cnt+=1
    if len(a)==0:
        break
    cnt2=1
    while cnt2<c:
        if a[-1]<=b+k:
            a.pop()
            cnt2+=1
            if len(a)==0:
                cnt2=1
                break
        else:
            cnt2=1
            break
print(cnt)
### BUGGY CODE ###

def main():
    n = int(input())
    alis = sorted(map(int, input().split()))
    adic = {}
    for num in alis:
        if num in adic:
            adic[num] += 1
        else:
            adic[num] = 1
    
    anslis = []

    q = int(input())
    bclis = []
    for i in range(q):
        b, c = map(int,input().split())
        if b in adic:
            kazu = adic[b]
            adic[b] = 0
            if c in adic:
                adic[c] += kazu
            else:
                adic[c] = kazu
        ans = 0
        for key in adic:
            ans += adic[key] * key
        print(ans)
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    alis = sorted(map(int, input().split()))
    total = sum(alis)
    adic = {}
    for num in alis:
        if num in adic:
            adic[num] += 1
        else:
            adic[num] = 1
    
    anslis = []

    q = int(input())
    bclis = []
    for i in range(q):
        b, c = map(int,input().split())
        if b in adic:
            kazu = adic[b]
            adic[b] = 0
            total -= b * kazu
            if c in adic:
                adic[c] += kazu
            else:
                adic[c] = kazu
            total += c * kazu
        print(total)
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
fare_sum = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_sum += a
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


mintime = [[TIME_MAX] * (fare_sum + 1) for _ in range(N)]


def search():
    q = [(0, 0, S)]
    while q:
        t, loc, silvers = heapq.heappop(q)
        silvers = min(silvers, fare_sum)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], fare_sum)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > fare_sum:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))
### BUGGY CODE ###

l = raw_input().split()
#l=input[0].split()

n = int(l[0])
a = [2147483647]*50000
change = 1

for i in range(0,int(l[1])):
	l = raw_input().split()
#	l=input[i+1].split()
	if int(l[0])==0:
		a[int(l[1])]=int(l[2])
		change = 1
	elif change==l[1]+l[2]:
		change = l[1]+l[2]
		print m
	else:
		m = min(a[int(l[1]):int(l[2])+1])
		print m

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())
 
    a = [init] * n
    b = [init] * ((n // 100) + 1)
 
    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])
 
 
main()