CodeEff/ECCO huggingface dataset:
# Original solution
import sys

INF = 1000000007

stdin = sys.stdin
def na(): return list(map(int, stdin.readline().split()))
def nal(): return list(map(int, stdin.readline().split()))
def ns(): return stdin.readline().strip()
def ni(): return int(stdin.readline())

N = ni()
x = nal()
x.insert(0, 0)

n = 1
c = 0
a = 1

for i in range(N):
    t = x[i+1] - x[i] - 1
    c = c+1
    if(t > 1):
        n = n+t-1
    elif(t == 0):
        n = n-1
        if(n == -1):
            n = 1
            a = a*c
            c = c-1

for i in range(1, c+1):
    a = a*i

print((a % INF))

# Optimized solution
import sys

INF = 1000000007

stdin = sys.stdin
def na(): return list(map(int, stdin.readline().split()))
def nal(): return list(map(int, stdin.readline().split()))
def ns(): return stdin.readline().strip()
def ni(): return int(stdin.readline())

N = ni()
x = nal()
x.insert(0, 0)

n = 1
c = 0
a = 1

for i in range(N):
    t = x[i+1] - x[i] - 1
    c = c+1
    if(t > 1):
        n = n+t-1
    elif(t == 0):
        n = n-1
        if(n == -1):
            n = 1
            a = a*c%INF
            c = c-1

for i in range(1, c+1):
    a = a*i%INF

print((a % INF))
# Original solution
N = int(eval(input()))
p_list = list(map(int, input().split()))

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat *= sum + 1
    if r_pos >= 2 * sum + 1: sum += 1
print((pat % 1000000007))

# Optimized solution
N = int(eval(input()))
p_list = list(map(int, input().split()))

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat = (pat * (sum + 1)) % 1000000007
    if r_pos >= 2 * sum + 1: sum += 1
print(pat)
# Original solution
mod = 10 ** 9 + 7

N, *X = list(map(int, open(0).read().split()))

stack = []
ans = 1
for x in X:
    stack.append(x)
    if x < 2 * len(stack) - 1:
        ans = (ans * len(stack)) % mod
        stack.pop()
    else:
        ans = (ans * len(stack)) % mod

print(ans)


# Optimized solution
mod = 10 ** 9 + 7

N, *X = list(map(int, open(0).read().split()))

s = 0
ans = 1
for x in X:
    if x < 2 * s + 1:
        ans *= (s + 1)
    else:
        s += 1
        ans *= s
    ans %= mod

print(ans)
# Original solution
while(1):
    [n,m]=[int(x) for x in input().split()]
    if n==0:
        break
    else:
        C=[[9999 for x in range(m+1)] for y in range (m+1)]
        T=[[9999 for x in range(m+1)] for y in range (m+1)]
        for i in range(n):
            [a,b,c,t]=[int(x) for x in input().split()]
            C[a][b]=c
            C[b][a]=c
            T[a][b]=t
            T[b][a]=t
        for i in range(1,m+1):
            C[i][i]=0
            T[i][i]=0
        for k in range(1,m+1):
            for i in range(1,m+1):
                for j in range(1,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                    if T[i][j]>T[i][k]+T[k][j]:
                        T[i][j]=T[i][k]+T[k][j]
        Q=int(input())
        for i in range(Q):
            [p,q,r]=[int(x) for x in input().split()]
            if r:
                print(T[p][q])
            else:
                print(C[p][q])

# Optimized solution
while(1):
    [n,m]=[int(x) for x in input().split()]
    if n==0:
        break
    else:
        C=[[9999 for x in range(m+1)] for y in range (m+1)]
        T=[[9999 for x in range(m+1)] for y in range (m+1)]
        for i in range(n):
            [a,b,c,t]=[int(x) for x in input().split()]
            C[a][b]=c
            C[b][a]=c
            T[a][b]=t
            T[b][a]=t
        for i in range(1,m+1):
            C[i][i]=0
            T[i][i]=0
        for k in range(1,m+1):
            for i in range(1,m+1):
                for j in range(i,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                        C[j][i]=C[i][k]+C[k][j]
                    if T[i][j]>T[i][k]+T[k][j]:
                        T[i][j]=T[i][k]+T[k][j]
                        T[j][i]=T[i][k]+T[k][j]
        Q=int(input())
        for i in range(Q):
            [p,q,r]=[int(x) for x in input().split()]
            if r:
                print(T[p][q])
            else:
                print(C[p][q])
# Original solution
from heapq import heappop as hpop
from heapq import heappush as hpush

while True:
  n, m = list(map(int, input().split()))
  
  if not n:
    break
  
  cost_edges = [[] for _ in range(m)]
  time_edges = [[] for _ in range(m)]

  for _ in range(n):
    a, b, c, t = list(map(int, input().split()))
    cost_edges[a - 1].append((c, b - 1))
    cost_edges[b - 1].append((c, a - 1))
    time_edges[a - 1].append((t, b - 1))
    time_edges[b - 1].append((t, a - 1))
  
  k = int(eval(input()))

  for _ in range(k):
    start, goal, r = list(map(int ,input().split()))
    start -= 1
    goal -= 1
    
    if r:
      edges = time_edges
    else:
      edges = cost_edges

    que = [(0, start)]
    visited = [False for _ in range(m)]
    
    while que:
      score, station = hpop(que)
      visited[station] = True
      
      if station == goal:
        print(score)
        break

      for c, to_station in edges[station]:
        if not visited[to_station]:
          hpush(que, (score + c, to_station))


# Optimized solution
from heapq import heappop as hpop
from heapq import heappush as hpush

def main():
  
  while True:
    n, m = list(map(int, input().split()))
    
    if not n:
      break
    
    cost_edges = [[] for _ in range(m)]
    time_edges = [[] for _ in range(m)]
  
    for _ in range(n):
      a, b, c, t = list(map(int, input().split()))
      cost_edges[a - 1].append((c, b - 1))
      cost_edges[b - 1].append((c, a - 1))
      time_edges[a - 1].append((t, b - 1))
      time_edges[b - 1].append((t, a - 1))
    
    k = int(eval(input()))
  
    for _ in range(k):
      start, goal, r = list(map(int ,input().split()))
      start -= 1
      goal -= 1
      
      if r:
        edges = time_edges
      else:
        edges = cost_edges
  
      que = [(0, start)]
      visited = [False for _ in range(m)]
      
      while que:
        score, station = hpop(que)
        visited[station] = True
        
        if station == goal:
          print(score)
          break
  
        for c, to_station in edges[station]:
          if not visited[to_station]:
            hpush(que, (score + c, to_station))

main()
# Original solution
def doIt():
    (n, m) = list(map(int, input().split()))
    while(0 < n + m):
        mmax = 1.0e9
        costs = [[mmax for j in range(m)] for i in range(m)]
        times = [[mmax for j in range(m)] for i in range(m)]
        for i in range(m): costs[i][i] = times[i][i] = 0
        for i in range(n):
            (a, b, cost, time) = list(map(int, input().split()))
            a -= 1
            b -= 1
            costs[a][b] = costs[b][a] = cost
            times[a][b] = times[b][a] = time
        #Warshall-Floyd Algorithm
        for k in range(m):
            for i in range(m):
                for j in range(m):
                    costs[i][j] = costs[j][i] = min(costs[i][j], costs[i][k] + costs[k][j])
                    times[i][j] = times[j][i] = min(times[i][j], times[i][k] + times[k][j])
                    #pass
        k = eval(input())
        for i in range(k):
            (p, q, r) = list(map(int, input().split()))
            p -= 1
            q -= 1
            if(r == 0): print(costs[p][q])
            else: print(times[p][q])
        (n, m) = list(map(int, input().split()))
        
doIt()

# Optimized solution
def doIt():
    (n, m) = list(map(int, input().split()))
    while(0 < n + m):
        mmax = 1.0e9
        costs = [[mmax for j in range(m)] for i in range(m)]
        times = [[mmax for j in range(m)] for i in range(m)]
        for i in range(m): costs[i][i] = times[i][i] = 0
        for i in range(n):
            (a, b, cost, time) = list(map(int, input().split()))
            a -= 1
            b -= 1
            costs[a][b] = costs[b][a] = cost
            times[a][b] = times[b][a] = time
        #Warshall-Floyd Algorithm
        for k in range(m):
            for i in range(m):
                for j in range(i+1, m):
                    costs[i][j] = costs[j][i] = min(costs[i][j], costs[i][k] + costs[k][j])
                    times[i][j] = times[j][i] = min(times[i][j], times[i][k] + times[k][j])
                    #pass
        k = eval(input())
        for i in range(k):
            (p, q, r) = list(map(int, input().split()))
            p -= 1
            q -= 1
            if(r == 0): print(costs[p][q])
            else: print(times[p][q])
        (n, m) = list(map(int, input().split()))
        
doIt()
# Original solution
import heapq
def dijkstra(graph, size, start, r):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length[r]:
                distance[vi] = distance[u] + length[r]
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    graph = collections.defaultdict(list)
    for ai, bi, cost, time in abct:
        graph[ai].append(((cost, time), bi))
        graph[bi].append(((cost, time), ai))
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = list(map(int, f.readline().split()))
        dist = dijkstra(graph, m + 1, p, r)
        print((dist[q]))

# Optimized solution
import heapq
def dijkstra(graph, size, start, r):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length[r]:
                distance[vi] = distance[u] + length[r]
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    graph = collections.defaultdict(list)
    for ai, bi, cost, time in abct:
        graph[ai].append(((cost, time), bi))
        graph[bi].append(((cost, time), ai))
        
    k = int(f.readline())
    
    dist = {}
    for i in range(k):
        p, q, r = list(map(int, f.readline().split()))
        
        if (q,r) in dist:
            p, q = q, p
        elif (p,r) not in dist:
            dist[(p,r)] = dijkstra(graph, m + 1, p, r)
        print((dist[(p,r)][q]))
# Original solution
import sys
f = sys.stdin

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    dist = [[(float('inf'),float('inf'))  for j in range(m)] for i in range(m)]    
    for ai, bi, cost, time in abct:
        dist[ai - 1][bi - 1] = (cost, time)
    for k in range(m):
        for i in range(m):
            for j in range(m):
                if dist[i][j][0] > dist[i][k][0] + dist[k][j][0]:
                    dist[i][j] = (dist[i][k][0] + dist[k][j][0], dist[i][j][1])
                if dist[i][j][1] > dist[i][k][1] + dist[k][j][1]:
                    dist[i][j] = (dist[i][j][0], dist[i][k][1] + dist[k][j][1])
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = list(map(int, f.readline().split()))
        print((dist[p - 1][q - 1][r]))

# Optimized solution
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

import sys
f = sys.stdin

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    
    d = [[[float('inf')] * m for i in range(m)], [[float('inf')] * m for i in range(m)]]
    
    for ai, bi, ci, ti in abct:
        d[0][ai - 1][bi - 1] = ci
        d[1][ai - 1][bi - 1] = ti

    warshall_floyd(d[0])
    warshall_floyd(d[1])
        
    for i in range(int(f.readline())):
        p, q, r = list(map(int, f.readline().split()))
        print((d[r][p - 1][q - 1]))
# Original solution
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

import sys
f = sys.stdin

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    
    d = [[[float('inf')] * m for i in range(m)], [[float('inf')] * m for i in range(m)]]
    
    for ai, bi, ci, ti in abct:
        d[0][ai - 1][bi - 1] = ci
        d[1][ai - 1][bi - 1] = ti

    warshall_floyd(d[0])
    warshall_floyd(d[1])
        
    for i in range(int(f.readline())):
        p, q, r = list(map(int, f.readline().split()))
        print((d[r][p - 1][q - 1]))

# Optimized solution
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

import sys
f = sys.stdin

while True:
    n, m = list(map(int, f.readline().split()))
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    
    d = [[[float('inf')] * m for i in range(m)], [[float('inf')] * m for i in range(m)]]
    
    for ai, bi, ci, ti in abct:
        d[0][ai - 1][bi - 1] = d[0][bi - 1][ai - 1] = ci
        d[1][ai - 1][bi - 1] = d[1][bi - 1][ai - 1] = ti

    warshall_floyd(d[0])
    warshall_floyd(d[1])
        
    for i in range(int(f.readline())):
        p, q, r = list(map(int, f.readline().split()))
        print((d[r][p - 1][q - 1]))
# Original solution

INF = 1000000000

def dj(s, r):
  global d, done, cost
  d = [INF] * 100
  done = [0] * 100
  d[s] = 0
  while True:
    v = -1
    for i in range(V):
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == -1:
      break
    done[v] = True
    for i in range(V):
      d[i] = min(d[i], d[v] + cost[v][i][r])

while True:
  cost = [[[INF for k in range(2)] for j in range(100)] for i in range(100)]
  E, V = list(map(int, input().split()))
  if not E:
    break
  for i in range(E):
    a, b, c, d = list(map(int, input().split()))
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = eval(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    p -= 1
    q -= 1
    dj(p, r)
    print(d[q])

# Optimized solution

INF = 1000000000

def dj(s, e, r):
  d = [INF] * 100
  done = [0] * 100
  d[s] = 0
  while True:
    v = -1
    for i in range(V):
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in range(V):
      d[i] = min(d[i], d[v] + cost[v][i][r])

while True:
  cost = [[[INF for k in range(2)] for j in range(100)] for i in range(100)]
  E, V = list(map(int, input().split()))
  if not E:
    break
  for i in range(E):
    a, b, c, d = list(map(int, input().split()))
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = eval(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    p -= 1
    q -= 1
    print(dj(p, q, r))
# Original solution

from copy import deepcopy
INF = 1000000000
def dj(s, e, r):
  d = [INF] * 100
  done = [0] * 100
  d[s] = 0
  while True:
    v = -1
    for i in VL:
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in VL:
      d[i] = min(d[i], d[v] + cost[v][i][r])

L100 = list(range(100))
costPre = [[[INF for k in range(2)] for j in L100] for i in L100]
while True:
  E, V = list(map(int, input().split()))
  cost = deepcopy(costPre)
  VL = list(range(V))
  if not E:
    break
  for i in range(E):
    a, b, c, d = list(map(int, input().split()))
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = eval(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    p -= 1
    q -= 1
    print(dj(p, q, r))

# Optimized solution

INF = 1000000000
def dj(s, e, r):
  d = infPre[:]
  done = zeroPre[:]
  d[s] = 0
  while True:
    v = -1
    for i in VL:
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in VL:
      d[i] = min(d[i], d[v] + cost[v][i][r])

L100 = list(range(100))
infPre = [INF] * 100
zeroPre = [0] * 100
while True:
  cost = [[[INF for k in range(2)] for j in L100] for i in L100]
  E, V = list(map(int, input().split()))
  VL = list(range(V))
  if not E:
    break
  for i in range(E):
    a, b, c, d = list(map(int, input().split()))
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = eval(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    p -= 1
    q -= 1
    print(dj(p, q, r))
# Original solution

INF = 1000000000
def dj(s, e, r):
  d = infPre[:]
  done = zeroPre[:]
  d[s] = 0
  while True:
    v = -1
    for i in VL:
      if not done[i] and (v == -1 or d[i] < d[v]):
        v = i
    if v == e:
      return d[e]
    done[v] = True
    for i in VL:
      d[i] = min(d[i], d[v] + cost[v][i][r])

L100 = list(range(100))
infPre = [INF] * 100
zeroPre = [0] * 100
while True:
  cost = [[[INF for k in range(2)] for j in L100] for i in L100]
  E, V = list(map(int, input().split()))
  VL = list(range(V))
  if not E:
    break
  for i in range(E):
    a, b, c, d = list(map(int, input().split()))
    a -= 1
    b -= 1
    cost[a][b][0] = cost[b][a][0] = c
    cost[a][b][1] = cost[b][a][1] = d
  k = eval(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    p -= 1
    q -= 1
    print(dj(p, q, r))

# Optimized solution

def solve():
  INF = 1000000000
  L100 = range(100)
  infPre = [INF] * 100
  zeroPre = [0] * 100
  while True:
    cost = [[[INF for k in range(2)] for j in L100] for i in L100]
    E, V = list(map(int, input().split()))
    VL = range(V)
    if not E:
      break
    for i in range(E):
      a, b, c, d = list(map(int, input().split()))
      a -= 1
      b -= 1
      cost[a][b][0] = cost[b][a][0] = c
      cost[a][b][1] = cost[b][a][1] = d
    k = eval(input())
    for i in range(k):
      p, q, r = list(map(int, input().split()))
      p -= 1
      q -= 1
    
      d = infPre[:]
      done = zeroPre[:]
      d[p] = 0
      while True:
        v = -1
        for i in VL:
          if not done[i] and (v == -1 or d[i] < d[v]):
            v = i
        if v == q:
          print(d[q])
          break
        done[v] = True
        for i in VL:
          d[i] = min(d[i], d[v] + cost[v][i][r])

solve()
# Original solution
from itertools import product
INF = 1 << 29
while True:
    n, m = list(map(int, input().split())) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in range(n+1)]
    T = [[INF] * (m + 1) for _ in range(n+1)]
    for _ in range(n):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(range(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        print(A[r][p][q])

# Optimized solution
from itertools import product
INF = 1 << 29
while True:
    n, m = list(map(int, input().split())) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in range(m + 1)]
    T = [[INF] * (m + 1) for _ in range(m + 1)]
    for _ in range(n):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(range(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        print(A[r][p][q])
# Original solution
from itertools import product
INF = 1 << 20
while True:
    n, m = list(map(int, input().split())) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in range(m + 1)]
    T = [[INF] * (m + 1) for _ in range(m + 1)]
    for _ in range(n):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k, i, j in product(range(m + 1), repeat = 3):
        C[i][j] = min(C[i][j], C[i][k] + C[k][j])
        T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        print(A[r][p][q])

# Optimized solution
INF = 1 << 20
while True:
    n, m = list(map(int, input().split())) 
    if n | m == 0:
        break
    C = [[INF] * (m + 1) for _ in range(m + 1)]
    T = [[INF] * (m + 1) for _ in range(m + 1)]
    for _ in range(n):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    for k in range(m + 1):
        for i in range(m + 1):
            for j in range(m + 1):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
                T[i][j] = min(T[i][j], T[i][k] + T[k][j])    
    A = (C, T)
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        print(A[r][p][q])
# Original solution
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, G):
    visited = [False] * (M + 1)
    visited[0] = True
    d = [-1] * (M + 1)
    pq = [(0,s)]
    while not all(visited):
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        visited[cur] = True
        d[cur] = cost
        for nex in [i for i in range(1, M + 1) if G[cur][i] != -1]:
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return d
            
while True:
    N, M = list(map(int, input().split()))
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in range(M + 1)]
    T = [[-1] * (M + 1) for _ in range(M + 1)]
    for _ in range(N):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[False] * (M + 1) for  _ in range(2)]
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        if not checked[r][p]:
            A[r][p] = dijkstra(p, A[r])
            checked[r][p] = True
        print(A[r][p][q])

# Optimized solution
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    visited[0] = True
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        if cur == t:
            return cost
        visited[cur] = True
        for nex in range(1, M + 1):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return -1
            
while True:
    N, M = list(map(int, input().split()))
    if N | M == 0:
        break
    C = [[INF] * (M + 1) for _ in range(M + 1)]
    T = [[INF] * (M + 1) for _ in range(M + 1)]
    for _ in range(N):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[[False] * (M + 1) for  _ in range(M + 1)] for _ in range(2)]
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        if not checked[r][p][q]:
            A[r][p][q] = dijkstra(p, q, A[r])
            checked[r][p][q] = True
        print(A[r][p][q])