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

n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
while True:
    day_set = set()
    for i in range(n):
        if i in day_set or B[i] >= n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] >= n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            if all(b >= n - 1 for b in B):
                print(ans)
                exit()
    if not day_set:
        print(-1)
        exit()
    else:
        ans += 1


### FIXED CODE ###

n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
stack = [i for i in range(n)]
while True:
    day_set = set()
    next_stack = []
    while stack:
        i = stack.pop()
        if i in day_set or B[i] >= n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] >= n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            next_stack += [i, j]
            if all(b >= n - 1 for b in B):
                print(ans)
                exit()

    if not day_set:
        print(-1)
        exit()
    ans += 1
    stack = next_stack
### BUGGY CODE ###

t=int(input())
l=[]
ct=0
for k in range(t):
    s=str(input())
    if(s not in l):
        l.append(s)
        ct+=1
print(ct)

### FIXED CODE ###

t=int(input())
l=[]
for k in range(t):
    s=str(input())
    l.append(s)
l= list(dict.fromkeys(l))
print(len(l))
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def build_tree(self, s):
        for idx, i in enumerate(s[1:], 1):
            for j in range(26):
                tmp = idx
                if j == i:
                    cnt = 1
                else:
                    cnt = 0
                cnt += self.bit_query(j, idx - 1) - self.bit_query(j, idx - (idx & (-idx)))
                self.tree[j][idx] = cnt

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [i - 97 for i in map(ord, list(input()))]
S = [-1] + S
Q, *query = map(str, read().split())
bit = BIT(N)
bit.build_tree(S)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        c = ord(c) - 97
        if S[b] == c:
            continue
        bit.update(c, b, 1)
        bit.update(S[b], b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [i - 97 for i in map(ord, list(input()))]
S = [-1] + S
Q, *query = map(str, read().split())
bit = BIT(N)
for idx, i in enumerate(S[1:], 1):
    bit.update(i, idx, 1)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        c = ord(c) - 97
        if S[b] == c:
            continue
        bit.update(c, b, 1)
        bit.update(S[b], b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))
### BUGGY CODE ###

import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,0]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,y):
        global m
        global i
        global f
        if d==m-1:
            p=y
            if p!=i and z[p]>=1:
                f=1
        else:
            for j in range(w[d+1][1]+1):
                s(d+1,y*(w[d+1][0]**j))

    s(0,1)
    if f==0:
        ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
m=len(b)

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())

ans=len(str(n))
for i in range(1,n+1):
  if n%i==0:
    if n//i<i:
      break
    else:
      ans=min(ans,max(len(str(i)),len(str(n//i))))
print(ans)

### FIXED CODE ###

n=int(input())

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

k = int(input())
s = input()
mod = 10**9 + 7

n = 2*10**6 + 1
factorial = [1]
inverse = [1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))

def comb(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

n = len(s)
length = k + n
ans = 0
for i in range(n, length+1):
    temp = 1
    temp *= comb(i-1, n-1, mod)
    temp %= mod
    temp *= pow(25, i-n, mod)
    temp %= mod
    temp *= pow(26, length-i, mod)
    temp %= mod
    ans += temp
    ans %= mod
print(ans)

### FIXED CODE ###

k = int(input())
s = input()
mod = 10**9 + 7

n = 2*10**6 + 1
factorial = [1]
inverse = [1]
pow25 = [1]
pow26 = [1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
    pow25.append((pow25[-1]*25)%mod)
    pow26.append((pow26[-1]*26)%mod)

def comb(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

n = len(s)
length = k + n
ans = 0
for i in range(n, length+1):
    temp = 1
    temp *= comb(i-1, n-1, mod)
    temp %= mod
    temp *= pow25[i-n]
    temp %= mod
    temp *= pow26[length-i]
    temp %= mod
    ans += temp
    ans %= mod
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
lr = [[0]*2]*m
for i in range(m):
  lr[i] = list(map(int,input().split()))
valid = set(range(1,n+1))
for i in range(m):
  subleft = set(range(1,lr[i][0]))
  subright = set(range(lr[i][1]+1,n+1))
  valid.difference_update(subleft)
  valid.difference_update(subright)
print(len(valid))

### FIXED CODE ###

n,m = map(int,input().split())
lr = [[0]*2]*m
for i in range(m):
  lr[i] = list(map(int,input().split()))
maxl = 0
minr = 10**5
for i in range(m):
  maxl = max(maxl,lr[i][0])
  minr = min(minr,lr[i][1])
if maxl>minr:
  print(0)
else:
  print(minr-maxl+1)
### BUGGY CODE ###

n,k=map(int,input().split())
d=input().split()
stopcode=False
while stopcode==False:
  for i in range(len(str(n))):
    if str(n)[i] in d:
      n+=1
      break
    elif i==range(len(str(n))):
      stopcode=True
      break
    else:
      break
print(n)

### FIXED CODE ###

n,k=map(int,input().split())
d=input().split()
stopcode=False
while stopcode==False:
  for i in range(len(str(n))):
    if str(n)[i] in d:
      n+=1
      break
    elif i+1==len(str(n)):
      stopcode=True
      break
print(n)
### BUGGY CODE ###

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

amari=m % n
x=int((m-amari)/n)

ans=1
for i in range(1,x+1):
  if(m % i==0):
    ans=i
    
print(ans)


### FIXED CODE ###

import math

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

x=int(math.sqrt(m))

ans=1
for i in range(1,x+1):
  if m%i==0:
    if i*n<=m:
      ans=max(ans,i)
    if int(m/i)*n<=m:
      ans=max(ans,int(m/i))
print(ans)
### BUGGY CODE ###

import queue
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = queue.Queue()
q_c = queue.Queue()
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.put(i)
      q_c.put(j)
      g_r = 0
      g_c = 0
      
while not q_r.empty():
  r = q_r.get()
  c = q_c.get()
  
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.put(next_r)
    q_c.put(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)

def f(a, b):
    results = []
    cnt = 0
    for i in a:
        for j in b:
            cnt += 1
            results.append(i + j)
    return results
ab_results = f(a, b)
ab_results.sort(reverse=True)

results = f(c, ab_results[:k])
results.sort(reverse=True)

print("\n".join(map(str, results[:k])))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


tdiv=2**(h-1)
import numpy as np
s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    tmp=np.zeros(w)
    tmp+=s[0,:]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            tmp+=s[j+1,:]
        else:
            lis.append(tmp)
            tmp=np.zeros(w)
            tmp+=s[j+1,:]
            cnt+=1
    lis.append(tmp)
    lis = np.array(lis)
    clis=np.zeros(cnt+1)
    #print(lis,cnt)
    for ind in range(w):
        #if lis[:,ind].max()>k:
        #    cnt=10010010
        #    break
        clis+=lis[:,ind]
        if clis.max()>k:
            clis=lis[:,ind]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)
### BUGGY CODE ###

import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]<=0: continue
    cnt+=h_int[i]
    r = bisect(x, x[i]+2*D)
    h_int[i+1:r] = h_int[i+1:r]-h_int[i]

print(int(cnt))

### FIXED CODE ###

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
damage=[0]*(N+1)

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    #print(damage[i])
    damage[r]-= A*h_int
    

print(int(cnt))
### BUGGY CODE ###

n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
b = [sum(1 for x in a if x&(1<<i)) for i in range(60)]
ans = 0
for i in range(60):
  t = b[i]*(n-b[i])
  m = (1<<i)%mod
  ans = (ans + t*m%mod)%mod
print(ans)

### FIXED CODE ###

n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
b = [sum(1 for x in a if x&(1<<i)) for i in range(60)]
ans = 0
for i in range(60):
  t = b[i]*(n-b[i])
  m = (1<<i)%mod
  ans = (ans + t*m%mod)%mod
print(ans)
### BUGGY CODE ###

n = int(input())
dic ={}
for i in range(n):
    a = input()
    if dic.get(a):
        dic[a] += 1
    else:
        dic[a] = 1
res = sorted(list(filter(lambda key:dic[key]==max(dic.values()),list(dic))))
for key in res:
    print(key)

### FIXED CODE ###

n = int(input())
dic ={}
for i in range(n):
    key = input()
    if key not in dic:
        dic[key] = 1
    if key in dic:
        dic[key] += 1
max_v = max(dic.values())
res = sorted(list(filter(lambda key:dic[key]==max_v,list(dic))))
for key in res:
    print(key)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
cost = [[float("inf") for i in range(n)] for i in range(n)] 
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)    


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)
### BUGGY CODE ###

class Dice:
    def __init__(self):
        self.u=1
        self.w=2
        self.s=3
        self.e=4
        self.n=5
        self.d=6
        self.dic={"W":0,"S":1,"E":2,"N":3}
    
    def __init__(self,u,w,s,e,n,d):
        self.u=u
        self.w=w
        self.s=s
        self.e=e
        self.n=n
        self.d=d
        self.dic={"W":0,"S":1,"E":2,"N":3}

    def rot(self,way):
        if isinstance(way,str):
            way=self.dic[way]

        if(way==0):
            c=self.u
            self.u=self.e
            self.e=self.d
            self.d=self.w
            self.w=c
        elif way==1:
            c=self.u
            self.u=self.n
            self.n=self.d
            self.d=self.s
            self.s=c
        elif way==2:
            c=self.u
            self.u=self.w
            self.w=self.d
            self.d=self.e
            self.e=c

def mk_dice():
    u,s,e,w,n,d=map(int,input().split())
    return Dice(u,w,s,e,n,d)

import random
q=int(input())
dice_col=[]
ans=True
for j in range(q):
    dice_b=mk_dice()
    for dice in dice_col:
        for i in range (1000):
            dice.rot(random.randint(0,3))
            if(dice.u==dice_b.u and dice.d==dice_b.d and dice.w==dice_b.w and dice.s==dice_b.s and dice.e==dice_b.e and dice.n==dice_b.n):
                ans=False
    dice_col.append(dice_b)

if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

class Dice:
    def __init__(self):
        self.u=1
        self.w=2
        self.s=3
        self.e=4
        self.n=5
        self.d=6
        self.dic={"W":0,"S":1,"E":2,"N":3}
     
    def __init__(self,u,w,s,e,n,d):
        self.u=u
        self.w=w
        self.s=s
        self.e=e
        self.n=n
        self.d=d
        self.dic={"W":0,"S":1,"E":2,"N":3}
 
    def rot(self,way):
        if isinstance(way,str):
            way=self.dic[way]
 
        if(way==0):
            c=self.u
            self.u=self.e
            self.e=self.d
            self.d=self.w
            self.w=c
        elif way==1:
            c=self.u
            self.u=self.n
            self.n=self.d
            self.d=self.s
            self.s=c
        elif way==2:
            c=self.u
            self.u=self.w
            self.w=self.d
            self.d=self.e
            self.e=c
    def get_nums(self):   
        return {self.u,self.w,self.s,self.e,self.n,self.w,self.d}

def mk_dice():
    u,s,e,w,n,d=map(int,input().split())
    return Dice(u,w,s,e,n,d)
 
import random
q=int(input())
dice_col=[]
ans=True
for j in range(q):
    dice_b=mk_dice()
    for dice in dice_col:
        if(dice.get_nums()==dice_b.get_nums()):
            for i in range (1000):
                dice.rot(random.randint(0,2))
                if(dice.u==dice_b.u and dice.d==dice_b.d and dice.w==dice_b.w and dice.s==dice_b.s and dice.e==dice_b.e and dice.n==dice_b.n):
                    ans=False
        if ~ans:
            break
    dice_col.append(dice_b)
 
if ans:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n ,k=map(int, input().split())
H=[0]+list(map(int,input().split()))
dp=[10**10]*(n+1)
dp[1]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i+j<=n:
            dp[i+j]=min(dp[i+j], dp[i]+abs(H[i+j]-H[i]))
print(dp[n])

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
#配るDPでやってみる
#dp[i]をi番目の足場まで行くときの最小コストとする。
dp=[float('inf')]*(2*n)
dp[0]=0
dp[1]=0
for i in range(1,n+1):
    for a in range(1,min(k+1,n-i+1)):
            dp[i+a]=min(dp[i+a], dp[i]+abs(H[i+a-1]-H[i-1]))
print(dp[n])
### BUGGY CODE ###

import heapq
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

INF = float('inf')
dist = [[INF]*N for i in range(N)]
for i in range(N):
    dist[i][i] = 0

for i in range(N):
    hq = [(0,i)]
    heapq.heapify(hq)
    while hq:
        k,j = heapq.heappop(hq)
        k,l = divmod(k,L)
        for to,c in es[j]:
            if l+c > L:
                newcost = (k+1)*L + c
            else:
                newcost = k*L + l + c
            if newcost < dist[i][to]:
                dist[i][to] = newcost
                heapq.heappush(hq, (newcost, to))

for s,t in ST:
    s,t = s-1,t-1
    if dist[s][t] == INF:
        print(-1)
    else:
        print((dist[s][t]-1)//L)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    dist1[a][b] = dist1[b][a] = c
for i in range(N):
    dist1[i][i] = 0
    dist2[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist1[i][k] + dist1[k][j]
            if dist1[i][j] <= d: continue
            dist1[i][j] = d
for i in range(N):
    for j in range(N):
        if i==j: continue
        if dist1[i][j] <= L:
            dist2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist2[i][k] + dist2[k][j]
            if dist2[i][j] <= d: continue
            dist2[i][j] = d
ans = []
for s,t in ST:
    d = dist2[s-1][t-1]
    if d == INF:
        ans.append(-1)
    else:
        ans.append(d-1)
print(*ans, sep='\n')
### BUGGY CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        for j in range(n):
            dp[n-j] += np.append(np.zeros(ai,dtype=int),dp[n-j-1][:s+1-ai])
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        ans = (ans+(dp[i][s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros(3010,dtype = int)
    dp[0] = 1
    for i,ai in enumerate(a):
        ndp = dp*2
        ndp[ai:] += dp[:-ai]
        ndp %= mod
        dp = ndp
    print(dp[s])
    return

if __name__ == '__main__':
    main()