Skip to content

Instantly share code, notes, and snippets.

@FanwangM

FanwangM/CP_GFJSP.py

Last active January 11, 2024 20:24
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save FanwangM/d832d417bdaf9b5f84dfcff0a5c8122c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save FanwangM/d832d417bdaf9b5f84dfcff0a5c8122c to your computer and use it in GitHub Desktop.
Download ZIP
CP_GFJSP
Raw
CP_GFJSP.py
from itertools import product
from collections import OrderedDict
from ortools.linear_solver import pywraplp
from ortools.sat.python import cp_model
import numpy as np
from utils import get_m_value, parse_data
# n_opt, n_mach, operation_data, machine_data = parse_data("gfjsp_10_10_1.txt")
n_opt, n_mach, operation_data, machine_data = parse_data("gfjsp_10_5_1.txt")
operation_data["0"]["h"] = 0
operation_data["1"]["h"] = 0
operation_data["2"]["h"] = 0
operation_data["3"]["h"] = 20
infinity = 1.0e6
# declae the CP-SAT model
model = cp_model.CpModel()
solver = cp_model.CpSolver()
# define the parameters
# minimum lag between the starting time of operation i and the ending time of operation j
para_lmin = np.full((n_opt, n_opt), dtype=object, fill_value=-np.inf)
# maximum lag between the starting time of operation i and the ending time of operation j
para_lmax = np.full((n_opt, n_opt), dtype=object, fill_value=np.inf)
# processing time of operation i in machine m
# para_p = np.full((n_opt, n_mach), dtype=object, fill_value=np.inf)
para_p = np.full((n_mach, n_opt), dtype=object, fill_value=np.inf)
# the shape of h in the original file is (n_machine) while the shape of para_h in the
# paper is (n_opt, n_mach)
# maximum holding time of operation i in machine m
para_h = np.empty((n_opt, n_mach), dtype=object)
# para_h = np.empty(n_mach, dtype=object)
# mapping of operation i to machine m
# 20 for the furnaces, 0 for Cutting, Pressing, and Forging
# 0: Cutting; 1: Pressing; 2: Forging; 3: Furnace
holding_time_dict = {
"0": 0,
"1": 0,
"2": 0,
"3": 20,
}
# weight of operation i in machine m
# para_w = np.empty((n_opt, n_mach), dtype=object)
para_w = np.full((n_mach, n_opt), dtype=object, fill_value=np.inf)
# input/output delay time between two consecutive operations in mahcine m
para_delta = np.empty((n_mach), dtype=object)
# setup time of machine m when processing operation i before j
# para_a = np.full((n_opt, n_opt, n_mach), dtype=object, fill_value=np.inf)
para_a = np.full((n_mach, n_opt, n_opt), dtype=object, fill_value=np.inf)
# capacity of machine
para_mach_capacity = np.empty((n_mach), dtype=object)
for m in range(n_mach):
# capacity of machine is a set of constant numbers
para_mach_capacity[m] = machine_data[str(m)]["c"]
# input/output delay time between two consecutive operations in mahcine m
# delta(m): loading and unloading time of machine m (=1 for all machines)
para_delta[m] = 1
# set up time of machine m when processing operation i before j
# a(i,j,m): setup time of machine m when processing operation i before j (aijm = -inf if there
# is no setups)
for idx_setup, setup_data in enumerate(machine_data[str(m)]["setup_data"][0]):
para_a[m, int(setup_data[0]), int(setup_data[1])] = setup_data[2]
# maximum holding time of operation i in machine m
para_h[:, m] = holding_time_dict[str(machine_data[str(m)]["t"])]
# lag time
for i in range(n_opt):
for idx_lag, lag_data in enumerate(operation_data[str(i)]["lag"]):
# minimum lag between the starting time of operation i and the ending time of operation j
para_lmin[i, int(lag_data[0])] = lag_data[1]
# maximum lag between the starting time of operation i and the ending time of operation j
para_lmax[i, int(lag_data[0])] = lag_data[2]
for idx_pw, pw_data in enumerate(operation_data[str(i)]["pw"]):
# operation_data[str(1)]["pw"]
# # the shape of para_p in the original file is the transpose of the shape of para_p
# para_p[i, int(pw_data[0])] = pw_data[1]
# # the shape of para_w in the original file is the transpose of the shape of para_w
# para_w[i, int(pw_data[0])] = pw_data[2]
# the shape of para_p in the original file is the transpose of the shape of para_p
para_p[int(pw_data[0]), i] = pw_data[1]
# the shape of para_w in the original file is the transpose of the shape of para_w
para_w[int(pw_data[0]), i] = pw_data[2]
# reformat the shape of para_p and para_w
para_p = para_p.T
para_w = para_w.T
# # reshape the shape of para_a
# para_a = np.einsum("mij->ijm", para_a)
# the big M value
big_m = get_m_value(para_p=para_p, para_h=para_h, para_lmin=para_lmin, para_a=para_a)
# big_m = 1.0e4
para_p_horizon = np.copy(para_p)
para_p_horizon[para_p_horizon == np.inf] = 0
para_h_horizon = np.copy(para_h)
para_h_horizon[para_h_horizon == np.inf] = 0
para_lmax_horizon = np.copy(para_lmax)
para_lmax_horizon[para_lmax_horizon == np.inf] = 0
horizon = (
np.sum(para_p_horizon, axis=1)
+ np.sum(para_h_horizon, axis=1)
+ np.sum(para_lmax_horizon, axis=1)
)
horizon = int(np.sum(horizon)) + 1
print(f"horizon: {horizon}")
# replace infinities with infinity from the solver
para_lmin[para_lmin == -np.inf] = -infinity
para_lmin[para_lmin == np.inf] = infinity
para_lmax[para_lmax == np.inf] = infinity
para_lmax[para_lmax == -np.inf] = -infinity
para_p[para_p == np.inf] = infinity
para_p[para_p == -np.inf] = -infinity
para_w[para_w == np.inf] = infinity
para_w[para_w == -np.inf] = -infinity
para_a[para_a == np.inf] = infinity
para_a[para_a == -np.inf] = -infinity
# =====================================================
# convert all the numpy arrays with integers data type
para_lmin = para_lmin.astype(int)
para_lmax = para_lmax.astype(int)
para_p = para_p.astype(int)
para_w = para_w.astype(int)
para_a = para_a.astype(int)
para_delta = para_delta.astype(int)
para_mach_capacity = para_mach_capacity.astype(int)
# take only part of the data for testing
n_opt_selected = 8
n_opt = n_opt_selected
para_lmin = para_lmin[:n_opt_selected, :n_opt_selected]
para_lmax = para_lmax[:n_opt_selected, :n_opt_selected]
para_p = para_p[:n_opt_selected, :]
para_h = para_h[:n_opt_selected, :]
para_w = para_w[:n_opt_selected, :]
para_a = para_a[:n_opt_selected, :n_opt_selected, :]
# create variables
# scaler = 1.0e4
# horizon *= scaler
# if operation i is processed by machine m
var_y = np.empty((n_opt, n_mach), dtype=object)
for i, m in product(range(n_opt), range(n_mach)):
var_y[i, m] = model.NewBoolVar(f"y_{i}_{m}")
# if operation i is processed before operation j
var_x = np.empty((n_opt, n_opt), dtype=object)
for i, j in product(range(n_opt), range(n_opt)):
var_x[i, j] = model.NewBoolVar(f"x_{i}_{j}")
# if operation i is processed before operation j on machine m
var_z = np.empty((n_opt, n_opt, n_mach), dtype=object)
for i, j, m in product(range(n_opt), range(n_opt), range(n_mach)):
var_z[i, j, m] = model.NewBoolVar(f"z_{i}_{j}_{m}")
# starting time of operation i
var_s = np.empty((n_opt), dtype=object)
for i in range(n_opt):
var_s[i] = model.NewIntVar(0, horizon, f"s_{i}")
# completion time of operation i
var_c = np.empty((n_opt), dtype=object)
for i in range(n_opt):
var_c[i] = model.NewIntVar(0, horizon, f"c_{i}")
# make span
var_c_max = model.NewIntVar(0, horizon, "C_max")
# define the variables in table of section 3
for i in range(n_opt):
# eq. (3)
# !!!!!!!!! expr = [para_p[i, m] * var_y[i, m] for i in range(n_mach)]
expr = [para_p[i, m] * var_y[i, m] for m in range(n_mach)]
model.Add(var_c[i] >= var_s[i] + sum(expr))
# eq. (4)
# !!!!!!!!!! expr = [(para_p[i, m] + para_h[i, m]) * var_y[i, m] for i in range(n_mach)]
expr = [(para_p[i, m] + para_h[i, m]) * var_y[i, m] for m in range(n_mach)]
model.Add(var_c[i] <= var_s[i] + sum(expr))
# eq. (5)
# !!!!!!!!!!!!!!
# for m in range(n_mach):
# # sum of y_im = 1
# model.Add(sum([var_y[i, m] for i in range(n_opt)]) == 1)
for i in range(n_opt):
# sum of y_im = 1
model.Add(sum([var_y[i, m] for m in range(n_mach)]) == 1)
for i, j in product(range(n_opt), range(n_opt)):
# eq. (6)
# minimum lag between the starting time of operation i and the ending time of operation j
model.Add(var_s[j] >= var_c[i] + para_lmin[i, j])
# eq. (7)
# maximum lag between the starting time of operation i and the ending time of operation j
model.Add(var_s[j] <= var_c[i] + para_lmax[i, j])
# TODO: remove this
# setting all the variables to 0 for now
para_a[:, :, :] = 0
# eq. (22) and (23)
# this new version reimplements the constraints in eq. (22) and (23) in the paper
# https://developers.google.com/optimization/cp/channeling
for i, j, m in product(np.arange(n_opt), np.arange(n_opt), np.arange(n_mach)):
# https://github.com/d-krupke/cpsat-primer
# model.Add(x + z == 10).OnlyEnforceIf([b2, b3.Not()])
# eq. (22)
# left part of the implication
bool_b1 = model.NewBoolVar(f"bool_b1_{i}_{j}_{m}")
model.Add(var_y[i, m] + var_y[j, m] == 2).OnlyEnforceIf(bool_b1)
model.Add(var_y[i, m] + var_y[j, m] != 2).OnlyEnforceIf(bool_b1.Not())
# model.AddBoolAnd(var_y[i, m], var_y[j, m]).OnlyEnforceIf(bool_b1)
# model.AddAtMostOne([var_y[i, m], var_y[j, m]]).OnlyEnforceIf(bool_b1.Not())
# right part of the implication
bool_b2 = model.NewBoolVar(f"bool_b2_{i}_{j}_{m}")
bool_a1 = model.NewBoolVar(f"bool_a1_{i}_{j}_{m}")
bool_a2 = model.NewBoolVar(f"bool_a2_{i}_{j}_{m}")
model.Add(var_s[j] >= var_c[i] + para_a[m, i, j]).OnlyEnforceIf(bool_a1)
model.Add(var_s[j] < var_c[i] + para_a[m, i, j]).OnlyEnforceIf(bool_a1.Not())
model.Add(var_s[i] >= var_c[j] + para_a[m, j, i]).OnlyEnforceIf(bool_a2)
model.Add(var_s[i] < var_c[j] + para_a[m, j, i]).OnlyEnforceIf(bool_a2.Not())
# model.AddBoolOr(bool_a1, bool_a2).OnlyEnforceIf(bool_b2)
# model.AddBoolAnd(bool_a1.Not(), bool_a2.Not()).OnlyEnforceIf(bool_b2.Not())
model.Add(bool_a1 + bool_a2 == 1).OnlyEnforceIf(bool_b2)
model.Add(bool_a1 + bool_a2 != 1).OnlyEnforceIf(bool_b2.Not())
# the implication
model.AddImplication(bool_b1, bool_b2)
# # eq. (23)
# # left part of the implication is the same as eq. (22), so we can reuse bool_b1
# # right part of the implication
# bool_b3 = model.NewBoolVar(f"bool_b3_{i}_{j}_{m}")
# max_eq23_first = model.NewIntVar(0, horizon, f"max_eq23_{i}_{j}_{m}_first")
# model.AddMaxEquality(max_eq23_first, [0, var_c[i] - var_s[i] - var_c[j] + var_s[j]])
# max_eq23_second = model.NewIntVar(0, horizon, f"max_eq23_{i}_{j}_{m}_second")
# model.AddMaxEquality(
# max_eq23_second, [0, var_c[j] - var_s[j] - var_c[i] + var_s[i]]
# )
# # define the intermediate variable for var_s[j] >= var_s[i] + max_eq23_first + para_delta[m]
# bool_a3 = model.NewBoolVar(f"bool_a3_{i}_{j}_{m}")
# model.Add(var_s[j] >= var_s[i] + max_eq23_first + para_delta[m]).OnlyEnforceIf(
# bool_a3
# )
# model.Add(var_s[j] < var_s[i] + max_eq23_first + para_delta[m]).OnlyEnforceIf(
# bool_a3.Not()
# )
# # define the intermediate variable for var_s[i] >= var_s[j] + max_eq23_second + para_delta[m]
# bool_a4 = model.NewBoolVar(f"bool_a4_{i}_{j}_{m}")
# model.Add(var_s[i] >= var_s[j] + max_eq23_second + para_delta[m]).OnlyEnforceIf(
# bool_a4
# )
# model.Add(var_s[i] < var_s[j] + max_eq23_second + para_delta[m]).OnlyEnforceIf(
# bool_a4.Not()
# )
# model.AddBoolOr(bool_a3, bool_a4).OnlyEnforceIf(bool_b3)
# model.AddBoolAnd(bool_a3.Not(), bool_a4.Not()).OnlyEnforceIf(bool_b3.Not())
# # the implication
# model.AddImplication(bool_b1, bool_b3)
# https://developers.google.com/optimization/cp/channeling
# TODO: num_t can be a huge number, leading to memory error
# sum_time = sum(para_p) + sum(para_h) + sum(para_a) # this is wrong
sum_time = horizon
# num_t = int(np.sum(sum_time) / 1.0e4)
num_t = int(sum_time / 1.0e0)
var_u = np.empty((n_opt, n_mach, num_t), dtype=object)
for i, m, t in product(range(n_opt), range(n_mach), range(num_t)):
var_u[i, m, t] = model.NewIntVar(0, np.max(para_w), f"u_{i}_{m}_{t}")
# eq. (25)
for idx_m, m in enumerate(np.arange(n_mach)):
for idx_t, t in enumerate(np.arange(num_t)):
constr_25 = 0
for idx_i, i in enumerate(np.arange(n_opt)):
# constr_25 += var_y[idx_i, idx_m] * var_u[idx_i, idx_m, idx_t]
# xy = model.NewIntVar(0, 8*5, 'xy')
# model.AddMultiplicationEquality(xy, [x, y])
yu = model.NewIntVar(0, np.max(para_w), f"yu_{idx_i}_{idx_m}_{idx_t}")
model.AddMultiplicationEquality(
yu, [var_y[idx_i, idx_m], var_u[idx_i, idx_m, idx_t]]
)
constr_25 += yu
model.Add(constr_25 <= para_mach_capacity[idx_m])
# eq. (24)
for idx_m, m in enumerate(np.arange(n_mach)):
for idx_i, i in enumerate(np.arange(n_opt)):
for idx_t, t in enumerate(np.arange(num_t)):
bool_list = []
bool_x7 = model.NewBoolVar(f"bool_x7_{i}_{idx_t}")
model.Add(var_s[i] <= t).OnlyEnforceIf(bool_x7)
bool_list.append(bool_x7)
bool_x8 = model.NewBoolVar(f"bool_x8_{i}_{idx_t}")
model.Add(var_c[i] >= t).OnlyEnforceIf(bool_x8)
bool_list.append(bool_x8)
bool_x9_and = model.NewBoolVar(f"bool_x9_{i}_{idx_t}")
# model.AddBoolAnd(bool_x9_and == 1).OnlyEnforceIf([bool_x7, bool_x8])
# when bool_x7 and bool_x8 are both true, var_u is is w_im
model.Add(var_u[idx_i, idx_m, idx_t] == para_w[idx_i, idx_m]).OnlyEnforceIf(
bool_x9_and
)
model.Add(var_u[idx_i, idx_m, idx_t] == 0).OnlyEnforceIf(bool_x9_and.Not())
# solve the model
status = solver.Solve(model)
# cp_model.OPTIMAL: 4
# cp_model.FEASIBLE: 2
# cp_model.INFEASIBLE: 3
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"the optimal makespan is {solver.ObjectiveValue()}")
else:
print(f"status is {status}")
print(f"{solver.SufficientAssumptionsForInfeasibility()}")
solver.ObjectiveValue()
# [VarX[_].solution_value() for _ in range(X.shape[0])]
if status == cp_model.INFEASIBLE:
# print infeasible boolean variables index
print(
"SufficientAssumptionsForInfeasibility = "
f"{solver.SufficientAssumptionsForInfeasibility()}"
)
# print infeasible boolean variables
infeasibles = solver.SufficientAssumptionsForInfeasibility()
for i in infeasibles:
print("Infeasible constraint: %d" % model.GetBoolVarFromProtoIndex(i))
Raw
gfjsp_10_5_1.txt
94 6
1440 0 inf 1 0 5 1 1 1 0 inf
1440 0 inf 3 3 274 363 4 274 363 5 274 363 1 2 0 5
1440 0 inf 1 1 5 1 1 3 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 4 0 5
1440 0 inf 1 2 10 1 1 5 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 6 0 5
1440 0 inf 1 2 10 1 1 7 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 8 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 10 0 inf
1440 0 inf 3 3 324 977 4 324 977 5 324 977 1 11 0 5
1440 0 inf 1 1 5 1 1 12 0 10
1440 0 inf 3 3 81 977 4 81 977 5 81 977 1 13 0 5
1440 0 inf 1 2 10 1 1 14 0 10
1440 0 inf 3 3 81 977 4 81 977 5 81 977 1 15 0 5
1440 0 inf 1 2 10 1 1 16 0 10
1440 0 inf 3 3 81 977 4 81 977 5 81 977 1 17 0 5
1440 0 inf 1 2 10 1 1 18 0 10
1440 0 inf 3 3 81 977 4 81 977 5 81 977 1 19 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 21 0 inf
1440 0 inf 3 3 274 363 4 274 363 5 274 363 1 22 0 5
1440 0 inf 1 1 5 1 1 23 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 24 0 5
1440 0 inf 1 2 10 1 1 25 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 26 0 5
1440 0 inf 1 2 10 1 1 27 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 28 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 30 0 inf
1440 0 inf 3 3 281 786 4 281 786 5 281 786 1 31 0 5
1440 0 inf 1 1 5 1 1 32 0 10
1440 0 inf 3 3 70 786 4 70 786 5 70 786 1 33 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 35 0 inf
1440 0 inf 3 3 189 962 4 189 962 5 189 962 1 36 0 5
1440 0 inf 1 1 5 1 1 37 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 38 0 5
1440 0 inf 1 2 10 1 1 39 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 40 0 5
1440 0 inf 1 2 10 1 1 41 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 42 0 5
1440 0 inf 1 2 10 1 1 43 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 44 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 46 0 inf
1440 0 inf 3 3 189 962 4 189 962 5 189 962 1 47 0 5
1440 0 inf 1 1 5 1 1 48 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 49 0 5
1440 0 inf 1 2 10 1 1 50 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 51 0 5
1440 0 inf 1 2 10 1 1 52 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 53 0 5
1440 0 inf 1 2 10 1 1 54 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 55 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 57 0 inf
1440 0 inf 3 3 189 962 4 189 962 5 189 962 1 58 0 5
1440 0 inf 1 1 5 1 1 59 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 60 0 5
1440 0 inf 1 2 10 1 1 61 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 62 0 5
1440 0 inf 1 2 10 1 1 63 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 64 0 5
1440 0 inf 1 2 10 1 1 65 0 10
1440 0 inf 3 3 47 962 4 47 962 5 47 962 1 66 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 68 0 inf
1440 0 inf 3 3 274 363 4 274 363 5 274 363 1 69 0 5
1440 0 inf 1 1 5 1 1 70 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 71 0 5
1440 0 inf 1 2 10 1 1 72 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 73 0 5
1440 0 inf 1 2 10 1 1 74 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 75 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 77 0 inf
1440 0 inf 3 3 274 363 4 274 363 5 274 363 1 78 0 5
1440 0 inf 1 1 5 1 1 79 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 80 0 5
1440 0 inf 1 2 10 1 1 81 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 82 0 5
1440 0 inf 1 2 10 1 1 83 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 84 0 5
1440 0 inf 1 2 10 1 0
1440 0 inf 1 0 5 1 1 86 0 inf
1440 0 inf 3 3 274 363 4 274 363 5 274 363 1 87 0 5
1440 0 inf 1 1 5 1 1 88 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 89 0 5
1440 0 inf 1 2 10 1 1 90 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 91 0 5
1440 0 inf 1 2 10 1 1 92 0 10
1440 0 inf 3 3 68 363 4 68 363 5 68 363 1 93 0 5
1440 0 inf 1 2 10 1 0
1 0 90 0 9 5 0 20 5 0 29 5 0 34 5 0 45 5 0 56 5 0 67 5 0 76 5 0 85 5 9 0 5 9 20 5 9 29 5 9 34 5 9 45 5 9 56 5 9 67 5 9 76 5 9 85 5 20 0 5 20 9 5 20 29 5 20 34 5 20 45 5 20 56 5 20 67 5 20 76 5 20 85 5 29 0 5 29 9 5 29 20 5 29 34 5 29 45 5 29 56 5 29 67 5 29 76 5 29 85 5 34 0 5 34 9 5 34 20 5 34 29 5 34 45 5 34 56 5 34 67 5 34 76 5 34 85 5 45 0 5 45 9 5 45 20 5 45 29 5 45 34 5 45 56 5 45 67 5 45 76 5 45 85 5 56 0 5 56 9 5 56 20 5 56 29 5 56 34 5 56 45 5 56 67 5 56 76 5 56 85 5 67 0 5 67 9 5 67 20 5 67 29 5 67 34 5 67 45 5 67 56 5 67 76 5 67 85 5 76 0 5 76 9 5 76 20 5 76 29 5 76 34 5 76 45 5 76 56 5 76 67 5 76 85 5 85 0 5 85 9 5 85 20 5 85 29 5 85 34 5 85 45 5 85 56 5 85 67 5 85 76 5
1 1 90 2 11 5 2 22 5 2 31 5 2 36 5 2 47 5 2 58 5 2 69 5 2 78 5 2 87 5 11 2 5 11 22 5 11 31 5 11 36 5 11 47 5 11 58 5 11 69 5 11 78 5 11 87 5 22 2 5 22 11 5 22 31 5 22 36 5 22 47 5 22 58 5 22 69 5 22 78 5 22 87 5 31 2 5 31 11 5 31 22 5 31 36 5 31 47 5 31 58 5 31 69 5 31 78 5 31 87 5 36 2 5 36 11 5 36 22 5 36 31 5 36 47 5 36 58 5 36 69 5 36 78 5 36 87 5 47 2 5 47 11 5 47 22 5 47 31 5 47 36 5 47 58 5 47 69 5 47 78 5 47 87 5 58 2 5 58 11 5 58 22 5 58 31 5 58 36 5 58 47 5 58 69 5 58 78 5 58 87 5 69 2 5 69 11 5 69 22 5 69 31 5 69 36 5 69 47 5 69 58 5 69 78 5 69 87 5 78 2 5 78 11 5 78 22 5 78 31 5 78 36 5 78 47 5 78 58 5 78 69 5 78 87 5 87 2 5 87 11 5 87 22 5 87 31 5 87 36 5 87 47 5 87 58 5 87 69 5 87 78 5
1 2 992 4 6 -inf 4 8 -inf 4 13 15 4 15 15 4 17 15 4 19 15 4 24 -inf 4 26 15 4 28 15 4 33 15 4 38 15 4 40 15 4 42 15 4 44 15 4 49 15 4 51 15 4 53 15 4 55 15 4 60 15 4 62 15 4 64 15 4 66 15 4 71 -inf 4 73 15 4 75 15 4 80 -inf 4 82 15 4 84 15 4 89 -inf 4 91 15 4 93 15 6 4 -inf 6 8 -inf 6 13 15 6 15 15 6 17 15 6 19 15 6 24 15 6 26 -inf 6 28 15 6 33 15 6 38 15 6 40 15 6 42 15 6 44 15 6 49 15 6 51 15 6 53 15 6 55 15 6 60 15 6 62 15 6 64 15 6 66 15 6 71 15 6 73 -inf 6 75 15 6 80 15 6 82 -inf 6 84 15 6 89 15 6 91 -inf 6 93 15 8 4 -inf 8 6 -inf 8 13 15 8 15 15 8 17 15 8 19 15 8 24 15 8 26 15 8 28 -inf 8 33 15 8 38 15 8 40 15 8 42 15 8 44 15 8 49 15 8 51 15 8 53 15 8 55 15 8 60 15 8 62 15 8 64 15 8 66 15 8 71 15 8 73 15 8 75 -inf 8 80 15 8 82 15 8 84 -inf 8 89 15 8 91 15 8 93 -inf 13 4 15 13 6 15 13 8 15 13 15 -inf 13 17 -inf 13 19 -inf 13 24 15 13 26 15 13 28 15 13 33 15 13 38 15 13 40 15 13 42 15 13 44 15 13 49 15 13 51 15 13 53 15 13 55 15 13 60 15 13 62 15 13 64 15 13 66 15 13 71 15 13 73 15 13 75 15 13 80 15 13 82 15 13 84 15 13 89 15 13 91 15 13 93 15 15 4 15 15 6 15 15 8 15 15 13 -inf 15 17 -inf 15 19 -inf 15 24 15 15 26 15 15 28 15 15 33 15 15 38 15 15 40 15 15 42 15 15 44 15 15 49 15 15 51 15 15 53 15 15 55 15 15 60 15 15 62 15 15 64 15 15 66 15 15 71 15 15 73 15 15 75 15 15 80 15 15 82 15 15 84 15 15 89 15 15 91 15 15 93 15 17 4 15 17 6 15 17 8 15 17 13 -inf 17 15 -inf 17 19 -inf 17 24 15 17 26 15 17 28 15 17 33 15 17 38 15 17 40 15 17 42 15 17 44 15 17 49 15 17 51 15 17 53 15 17 55 15 17 60 15 17 62 15 17 64 15 17 66 15 17 71 15 17 73 15 17 75 15 17 80 15 17 82 15 17 84 15 17 89 15 17 91 15 17 93 15 19 4 15 19 6 15 19 8 15 19 13 -inf 19 15 -inf 19 17 -inf 19 24 15 19 26 15 19 28 15 19 33 15 19 38 15 19 40 15 19 42 15 19 44 15 19 49 15 19 51 15 19 53 15 19 55 15 19 60 15 19 62 15 19 64 15 19 66 15 19 71 15 19 73 15 19 75 15 19 80 15 19 82 15 19 84 15 19 89 15 19 91 15 19 93 15 24 4 -inf 24 6 15 24 8 15 24 13 15 24 15 15 24 17 15 24 19 15 24 26 -inf 24 28 -inf 24 33 15 24 38 15 24 40 15 24 42 15 24 44 15 24 49 15 24 51 15 24 53 15 24 55 15 24 60 15 24 62 15 24 64 15 24 66 15 24 71 -inf 24 73 15 24 75 15 24 80 -inf 24 82 15 24 84 15 24 89 -inf 24 91 15 24 93 15 26 4 15 26 6 -inf 26 8 15 26 13 15 26 15 15 26 17 15 26 19 15 26 24 -inf 26 28 -inf 26 33 15 26 38 15 26 40 15 26 42 15 26 44 15 26 49 15 26 51 15 26 53 15 26 55 15 26 60 15 26 62 15 26 64 15 26 66 15 26 71 15 26 73 -inf 26 75 15 26 80 15 26 82 -inf 26 84 15 26 89 15 26 91 -inf 26 93 15 28 4 15 28 6 15 28 8 -inf 28 13 15 28 15 15 28 17 15 28 19 15 28 24 -inf 28 26 -inf 28 33 15 28 38 15 28 40 15 28 42 15 28 44 15 28 49 15 28 51 15 28 53 15 28 55 15 28 60 15 28 62 15 28 64 15 28 66 15 28 71 15 28 73 15 28 75 -inf 28 80 15 28 82 15 28 84 -inf 28 89 15 28 91 15 28 93 -inf 33 4 15 33 6 15 33 8 15 33 13 15 33 15 15 33 17 15 33 19 15 33 24 15 33 26 15 33 28 15 33 38 15 33 40 15 33 42 15 33 44 15 33 49 15 33 51 15 33 53 15 33 55 15 33 60 15 33 62 15 33 64 15 33 66 15 33 71 15 33 73 15 33 75 15 33 80 15 33 82 15 33 84 15 33 89 15 33 91 15 33 93 15 38 4 15 38 6 15 38 8 15 38 13 15 38 15 15 38 17 15 38 19 15 38 24 15 38 26 15 38 28 15 38 33 15 38 40 -inf 38 42 -inf 38 44 -inf 38 49 -inf 38 51 15 38 53 15 38 55 15 38 60 -inf 38 62 15 38 64 15 38 66 15 38 71 15 38 73 15 38 75 15 38 80 15 38 82 15 38 84 15 38 89 15 38 91 15 38 93 15 40 4 15 40 6 15 40 8 15 40 13 15 40 15 15 40 17 15 40 19 15 40 24 15 40 26 15 40 28 15 40 33 15 40 38 -inf 40 42 -inf 40 44 -inf 40 49 15 40 51 -inf 40 53 15 40 55 15 40 60 15 40 62 -inf 40 64 15 40 66 15 40 71 15 40 73 15 40 75 15 40 80 15 40 82 15 40 84 15 40 89 15 40 91 15 40 93 15 42 4 15 42 6 15 42 8 15 42 13 15 42 15 15 42 17 15 42 19 15 42 24 15 42 26 15 42 28 15 42 33 15 42 38 -inf 42 40 -inf 42 44 -inf 42 49 15 42 51 15 42 53 -inf 42 55 15 42 60 15 42 62 15 42 64 -inf 42 66 15 42 71 15 42 73 15 42 75 15 42 80 15 42 82 15 42 84 15 42 89 15 42 91 15 42 93 15 44 4 15 44 6 15 44 8 15 44 13 15 44 15 15 44 17 15 44 19 15 44 24 15 44 26 15 44 28 15 44 33 15 44 38 -inf 44 40 -inf 44 42 -inf 44 49 15 44 51 15 44 53 15 44 55 -inf 44 60 15 44 62 15 44 64 15 44 66 -inf 44 71 15 44 73 15 44 75 15 44 80 15 44 82 15 44 84 15 44 89 15 44 91 15 44 93 15 49 4 15 49 6 15 49 8 15 49 13 15 49 15 15 49 17 15 49 19 15 49 24 15 49 26 15 49 28 15 49 33 15 49 38 -inf 49 40 15 49 42 15 49 44 15 49 51 -inf 49 53 -inf 49 55 -inf 49 60 -inf 49 62 15 49 64 15 49 66 15 49 71 15 49 73 15 49 75 15 49 80 15 49 82 15 49 84 15 49 89 15 49 91 15 49 93 15 51 4 15 51 6 15 51 8 15 51 13 15 51 15 15 51 17 15 51 19 15 51 24 15 51 26 15 51 28 15 51 33 15 51 38 15 51 40 -inf 51 42 15 51 44 15 51 49 -inf 51 53 -inf 51 55 -inf 51 60 15 51 62 -inf 51 64 15 51 66 15 51 71 15 51 73 15 51 75 15 51 80 15 51 82 15 51 84 15 51 89 15 51 91 15 51 93 15 53 4 15 53 6 15 53 8 15 53 13 15 53 15 15 53 17 15 53 19 15 53 24 15 53 26 15 53 28 15 53 33 15 53 38 15 53 40 15 53 42 -inf 53 44 15 53 49 -inf 53 51 -inf 53 55 -inf 53 60 15 53 62 15 53 64 -inf 53 66 15 53 71 15 53 73 15 53 75 15 53 80 15 53 82 15 53 84 15 53 89 15 53 91 15 53 93 15 55 4 15 55 6 15 55 8 15 55 13 15 55 15 15 55 17 15 55 19 15 55 24 15 55 26 15 55 28 15 55 33 15 55 38 15 55 40 15 55 42 15 55 44 -inf 55 49 -inf 55 51 -inf 55 53 -inf 55 60 15 55 62 15 55 64 15 55 66 -inf 55 71 15 55 73 15 55 75 15 55 80 15 55 82 15 55 84 15 55 89 15 55 91 15 55 93 15 60 4 15 60 6 15 60 8 15 60 13 15 60 15 15 60 17 15 60 19 15 60 24 15 60 26 15 60 28 15 60 33 15 60 38 -inf 60 40 15 60 42 15 60 44 15 60 49 -inf 60 51 15 60 53 15 60 55 15 60 62 -inf 60 64 -inf 60 66 -inf 60 71 15 60 73 15 60 75 15 60 80 15 60 82 15 60 84 15 60 89 15 60 91 15 60 93 15 62 4 15 62 6 15 62 8 15 62 13 15 62 15 15 62 17 15 62 19 15 62 24 15 62 26 15 62 28 15 62 33 15 62 38 15 62 40 -inf 62 42 15 62 44 15 62 49 15 62 51 -inf 62 53 15 62 55 15 62 60 -inf 62 64 -inf 62 66 -inf 62 71 15 62 73 15 62 75 15 62 80 15 62 82 15 62 84 15 62 89 15 62 91 15 62 93 15 64 4 15 64 6 15 64 8 15 64 13 15 64 15 15 64 17 15 64 19 15 64 24 15 64 26 15 64 28 15 64 33 15 64 38 15 64 40 15 64 42 -inf 64 44 15 64 49 15 64 51 15 64 53 -inf 64 55 15 64 60 -inf 64 62 -inf 64 66 -inf 64 71 15 64 73 15 64 75 15 64 80 15 64 82 15 64 84 15 64 89 15 64 91 15 64 93 15 66 4 15 66 6 15 66 8 15 66 13 15 66 15 15 66 17 15 66 19 15 66 24 15 66 26 15 66 28 15 66 33 15 66 38 15 66 40 15 66 42 15 66 44 -inf 66 49 15 66 51 15 66 53 15 66 55 -inf 66 60 -inf 66 62 -inf 66 64 -inf 66 71 15 66 73 15 66 75 15 66 80 15 66 82 15 66 84 15 66 89 15 66 91 15 66 93 15 71 4 -inf 71 6 15 71 8 15 71 13 15 71 15 15 71 17 15 71 19 15 71 24 -inf 71 26 15 71 28 15 71 33 15 71 38 15 71 40 15 71 42 15 71 44 15 71 49 15 71 51 15 71 53 15 71 55 15 71 60 15 71 62 15 71 64 15 71 66 15 71 73 -inf 71 75 -inf 71 80 -inf 71 82 15 71 84 15 71 89 -inf 71 91 15 71 93 15 73 4 15 73 6 -inf 73 8 15 73 13 15 73 15 15 73 17 15 73 19 15 73 24 15 73 26 -inf 73 28 15 73 33 15 73 38 15 73 40 15 73 42 15 73 44 15 73 49 15 73 51 15 73 53 15 73 55 15 73 60 15 73 62 15 73 64 15 73 66 15 73 71 -inf 73 75 -inf 73 80 15 73 82 -inf 73 84 15 73 89 15 73 91 -inf 73 93 15 75 4 15 75 6 15 75 8 -inf 75 13 15 75 15 15 75 17 15 75 19 15 75 24 15 75 26 15 75 28 -inf 75 33 15 75 38 15 75 40 15 75 42 15 75 44 15 75 49 15 75 51 15 75 53 15 75 55 15 75 60 15 75 62 15 75 64 15 75 66 15 75 71 -inf 75 73 -inf 75 80 15 75 82 15 75 84 -inf 75 89 15 75 91 15 75 93 -inf 80 4 -inf 80 6 15 80 8 15 80 13 15 80 15 15 80 17 15 80 19 15 80 24 -inf 80 26 15 80 28 15 80 33 15 80 38 15 80 40 15 80 42 15 80 44 15 80 49 15 80 51 15 80 53 15 80 55 15 80 60 15 80 62 15 80 64 15 80 66 15 80 71 -inf 80 73 15 80 75 15 80 82 -inf 80 84 -inf 80 89 -inf 80 91 15 80 93 15 82 4 15 82 6 -inf 82 8 15 82 13 15 82 15 15 82 17 15 82 19 15 82 24 15 82 26 -inf 82 28 15 82 33 15 82 38 15 82 40 15 82 42 15 82 44 15 82 49 15 82 51 15 82 53 15 82 55 15 82 60 15 82 62 15 82 64 15 82 66 15 82 71 15 82 73 -inf 82 75 15 82 80 -inf 82 84 -inf 82 89 15 82 91 -inf 82 93 15 84 4 15 84 6 15 84 8 -inf 84 13 15 84 15 15 84 17 15 84 19 15 84 24 15 84 26 15 84 28 -inf 84 33 15 84 38 15 84 40 15 84 42 15 84 44 15 84 49 15 84 51 15 84 53 15 84 55 15 84 60 15 84 62 15 84 64 15 84 66 15 84 71 15 84 73 15 84 75 -inf 84 80 -inf 84 82 -inf 84 89 15 84 91 15 84 93 -inf 89 4 -inf 89 6 15 89 8 15 89 13 15 89 15 15 89 17 15 89 19 15 89 24 -inf 89 26 15 89 28 15 89 33 15 89 38 15 89 40 15 89 42 15 89 44 15 89 49 15 89 51 15 89 53 15 89 55 15 89 60 15 89 62 15 89 64 15 89 66 15 89 71 -inf 89 73 15 89 75 15 89 80 -inf 89 82 15 89 84 15 89 91 -inf 89 93 -inf 91 4 15 91 6 -inf 91 8 15 91 13 15 91 15 15 91 17 15 91 19 15 91 24 15 91 26 -inf 91 28 15 91 33 15 91 38 15 91 40 15 91 42 15 91 44 15 91 49 15 91 51 15 91 53 15 91 55 15 91 60 15 91 62 15 91 64 15 91 66 15 91 71 15 91 73 -inf 91 75 15 91 80 15 91 82 -inf 91 84 15 91 89 -inf 91 93 -inf 93 4 15 93 6 15 93 8 -inf 93 13 15 93 15 15 93 17 15 93 19 15 93 24 15 93 26 15 93 28 -inf 93 33 15 93 38 15 93 40 15 93 42 15 93 44 15 93 49 15 93 51 15 93 53 15 93 55 15 93 60 15 93 62 15 93 64 15 93 66 15 93 71 15 93 73 15 93 75 -inf 93 80 15 93 82 15 93 84 -inf 93 89 -inf 93 91 -inf
5000 3 1722 1 3 -inf 1 5 -inf 1 7 -inf 1 10 30 1 12 30 1 14 30 1 16 30 1 18 30 1 21 -inf 1 23 -inf 1 25 -inf 1 27 -inf 1 30 30 1 32 30 1 35 30 1 37 30 1 39 30 1 41 30 1 43 30 1 46 30 1 48 30 1 50 30 1 52 30 1 54 30 1 57 30 1 59 30 1 61 30 1 63 30 1 65 30 1 68 -inf 1 70 -inf 1 72 -inf 1 74 -inf 1 77 -inf 1 79 -inf 1 81 -inf 1 83 -inf 1 86 -inf 1 88 -inf 1 90 -inf 1 92 -inf 3 1 -inf 3 5 -inf 3 7 -inf 3 10 30 3 12 30 3 14 30 3 16 30 3 18 30 3 21 -inf 3 23 -inf 3 25 -inf 3 27 -inf 3 30 30 3 32 30 3 35 30 3 37 30 3 39 30 3 41 30 3 43 30 3 46 30 3 48 30 3 50 30 3 52 30 3 54 30 3 57 30 3 59 30 3 61 30 3 63 30 3 65 30 3 68 -inf 3 70 -inf 3 72 -inf 3 74 -inf 3 77 -inf 3 79 -inf 3 81 -inf 3 83 -inf 3 86 -inf 3 88 -inf 3 90 -inf 3 92 -inf 5 1 -inf 5 3 -inf 5 7 -inf 5 10 30 5 12 30 5 14 30 5 16 30 5 18 30 5 21 -inf 5 23 -inf 5 25 -inf 5 27 -inf 5 30 30 5 32 30 5 35 30 5 37 30 5 39 30 5 41 30 5 43 30 5 46 30 5 48 30 5 50 30 5 52 30 5 54 30 5 57 30 5 59 30 5 61 30 5 63 30 5 65 30 5 68 -inf 5 70 -inf 5 72 -inf 5 74 -inf 5 77 -inf 5 79 -inf 5 81 -inf 5 83 -inf 5 86 -inf 5 88 -inf 5 90 -inf 5 92 -inf 7 1 -inf 7 3 -inf 7 5 -inf 7 10 30 7 12 30 7 14 30 7 16 30 7 18 30 7 21 -inf 7 23 -inf 7 25 -inf 7 27 -inf 7 30 30 7 32 30 7 35 30 7 37 30 7 39 30 7 41 30 7 43 30 7 46 30 7 48 30 7 50 30 7 52 30 7 54 30 7 57 30 7 59 30 7 61 30 7 63 30 7 65 30 7 68 -inf 7 70 -inf 7 72 -inf 7 74 -inf 7 77 -inf 7 79 -inf 7 81 -inf 7 83 -inf 7 86 -inf 7 88 -inf 7 90 -inf 7 92 -inf 10 1 30 10 3 30 10 5 30 10 7 30 10 12 -inf 10 14 -inf 10 16 -inf 10 18 -inf 10 21 30 10 23 30 10 25 30 10 27 30 10 30 30 10 32 30 10 35 30 10 37 30 10 39 30 10 41 30 10 43 30 10 46 30 10 48 30 10 50 30 10 52 30 10 54 30 10 57 30 10 59 30 10 61 30 10 63 30 10 65 30 10 68 30 10 70 30 10 72 30 10 74 30 10 77 30 10 79 30 10 81 30 10 83 30 10 86 30 10 88 30 10 90 30 10 92 30 12 1 30 12 3 30 12 5 30 12 7 30 12 10 -inf 12 14 -inf 12 16 -inf 12 18 -inf 12 21 30 12 23 30 12 25 30 12 27 30 12 30 30 12 32 30 12 35 30 12 37 30 12 39 30 12 41 30 12 43 30 12 46 30 12 48 30 12 50 30 12 52 30 12 54 30 12 57 30 12 59 30 12 61 30 12 63 30 12 65 30 12 68 30 12 70 30 12 72 30 12 74 30 12 77 30 12 79 30 12 81 30 12 83 30 12 86 30 12 88 30 12 90 30 12 92 30 14 1 30 14 3 30 14 5 30 14 7 30 14 10 -inf 14 12 -inf 14 16 -inf 14 18 -inf 14 21 30 14 23 30 14 25 30 14 27 30 14 30 30 14 32 30 14 35 30 14 37 30 14 39 30 14 41 30 14 43 30 14 46 30 14 48 30 14 50 30 14 52 30 14 54 30 14 57 30 14 59 30 14 61 30 14 63 30 14 65 30 14 68 30 14 70 30 14 72 30 14 74 30 14 77 30 14 79 30 14 81 30 14 83 30 14 86 30 14 88 30 14 90 30 14 92 30 16 1 30 16 3 30 16 5 30 16 7 30 16 10 -inf 16 12 -inf 16 14 -inf 16 18 -inf 16 21 30 16 23 30 16 25 30 16 27 30 16 30 30 16 32 30 16 35 30 16 37 30 16 39 30 16 41 30 16 43 30 16 46 30 16 48 30 16 50 30 16 52 30 16 54 30 16 57 30 16 59 30 16 61 30 16 63 30 16 65 30 16 68 30 16 70 30 16 72 30 16 74 30 16 77 30 16 79 30 16 81 30 16 83 30 16 86 30 16 88 30 16 90 30 16 92 30 18 1 30 18 3 30 18 5 30 18 7 30 18 10 -inf 18 12 -inf 18 14 -inf 18 16 -inf 18 21 30 18 23 30 18 25 30 18 27 30 18 30 30 18 32 30 18 35 30 18 37 30 18 39 30 18 41 30 18 43 30 18 46 30 18 48 30 18 50 30 18 52 30 18 54 30 18 57 30 18 59 30 18 61 30 18 63 30 18 65 30 18 68 30 18 70 30 18 72 30 18 74 30 18 77 30 18 79 30 18 81 30 18 83 30 18 86 30 18 88 30 18 90 30 18 92 30 21 1 -inf 21 3 -inf 21 5 -inf 21 7 -inf 21 10 30 21 12 30 21 14 30 21 16 30 21 18 30 21 23 -inf 21 25 -inf 21 27 -inf 21 30 30 21 32 30 21 35 30 21 37 30 21 39 30 21 41 30 21 43 30 21 46 30 21 48 30 21 50 30 21 52 30 21 54 30 21 57 30 21 59 30 21 61 30 21 63 30 21 65 30 21 68 -inf 21 70 -inf 21 72 -inf 21 74 -inf 21 77 -inf 21 79 -inf 21 81 -inf 21 83 -inf 21 86 -inf 21 88 -inf 21 90 -inf 21 92 -inf 23 1 -inf 23 3 -inf 23 5 -inf 23 7 -inf 23 10 30 23 12 30 23 14 30 23 16 30 23 18 30 23 21 -inf 23 25 -inf 23 27 -inf 23 30 30 23 32 30 23 35 30 23 37 30 23 39 30 23 41 30 23 43 30 23 46 30 23 48 30 23 50 30 23 52 30 23 54 30 23 57 30 23 59 30 23 61 30 23 63 30 23 65 30 23 68 -inf 23 70 -inf 23 72 -inf 23 74 -inf 23 77 -inf 23 79 -inf 23 81 -inf 23 83 -inf 23 86 -inf 23 88 -inf 23 90 -inf 23 92 -inf 25 1 -inf 25 3 -inf 25 5 -inf 25 7 -inf 25 10 30 25 12 30 25 14 30 25 16 30 25 18 30 25 21 -inf 25 23 -inf 25 27 -inf 25 30 30 25 32 30 25 35 30 25 37 30 25 39 30 25 41 30 25 43 30 25 46 30 25 48 30 25 50 30 25 52 30 25 54 30 25 57 30 25 59 30 25 61 30 25 63 30 25 65 30 25 68 -inf 25 70 -inf 25 72 -inf 25 74 -inf 25 77 -inf 25 79 -inf 25 81 -inf 25 83 -inf 25 86 -inf 25 88 -inf 25 90 -inf 25 92 -inf 27 1 -inf 27 3 -inf 27 5 -inf 27 7 -inf 27 10 30 27 12 30 27 14 30 27 16 30 27 18 30 27 21 -inf 27 23 -inf 27 25 -inf 27 30 30 27 32 30 27 35 30 27 37 30 27 39 30 27 41 30 27 43 30 27 46 30 27 48 30 27 50 30 27 52 30 27 54 30 27 57 30 27 59 30 27 61 30 27 63 30 27 65 30 27 68 -inf 27 70 -inf 27 72 -inf 27 74 -inf 27 77 -inf 27 79 -inf 27 81 -inf 27 83 -inf 27 86 -inf 27 88 -inf 27 90 -inf 27 92 -inf 30 1 30 30 3 30 30 5 30 30 7 30 30 10 30 30 12 30 30 14 30 30 16 30 30 18 30 30 21 30 30 23 30 30 25 30 30 27 30 30 32 -inf 30 35 -inf 30 37 -inf 30 39 -inf 30 41 -inf 30 43 -inf 30 46 -inf 30 48 -inf 30 50 -inf 30 52 -inf 30 54 -inf 30 57 -inf 30 59 -inf 30 61 -inf 30 63 -inf 30 65 -inf 30 68 30 30 70 30 30 72 30 30 74 30 30 77 30 30 79 30 30 81 30 30 83 30 30 86 30 30 88 30 30 90 30 30 92 30 32 1 30 32 3 30 32 5 30 32 7 30 32 10 30 32 12 30 32 14 30 32 16 30 32 18 30 32 21 30 32 23 30 32 25 30 32 27 30 32 30 -inf 32 35 -inf 32 37 -inf 32 39 -inf 32 41 -inf 32 43 -inf 32 46 -inf 32 48 -inf 32 50 -inf 32 52 -inf 32 54 -inf 32 57 -inf 32 59 -inf 32 61 -inf 32 63 -inf 32 65 -inf 32 68 30 32 70 30 32 72 30 32 74 30 32 77 30 32 79 30 32 81 30 32 83 30 32 86 30 32 88 30 32 90 30 32 92 30 35 1 30 35 3 30 35 5 30 35 7 30 35 10 30 35 12 30 35 14 30 35 16 30 35 18 30 35 21 30 35 23 30 35 25 30 35 27 30 35 30 -inf 35 32 -inf 35 37 -inf 35 39 -inf 35 41 -inf 35 43 -inf 35 46 -inf 35 48 -inf 35 50 -inf 35 52 -inf 35 54 -inf 35 57 -inf 35 59 -inf 35 61 -inf 35 63 -inf 35 65 -inf 35 68 30 35 70 30 35 72 30 35 74 30 35 77 30 35 79 30 35 81 30 35 83 30 35 86 30 35 88 30 35 90 30 35 92 30 37 1 30 37 3 30 37 5 30 37 7 30 37 10 30 37 12 30 37 14 30 37 16 30 37 18 30 37 21 30 37 23 30 37 25 30 37 27 30 37 30 -inf 37 32 -inf 37 35 -inf 37 39 -inf 37 41 -inf 37 43 -inf 37 46 -inf 37 48 -inf 37 50 -inf 37 52 -inf 37 54 -inf 37 57 -inf 37 59 -inf 37 61 -inf 37 63 -inf 37 65 -inf 37 68 30 37 70 30 37 72 30 37 74 30 37 77 30 37 79 30 37 81 30 37 83 30 37 86 30 37 88 30 37 90 30 37 92 30 39 1 30 39 3 30 39 5 30 39 7 30 39 10 30 39 12 30 39 14 30 39 16 30 39 18 30 39 21 30 39 23 30 39 25 30 39 27 30 39 30 -inf 39 32 -inf 39 35 -inf 39 37 -inf 39 41 -inf 39 43 -inf 39 46 -inf 39 48 -inf 39 50 -inf 39 52 -inf 39 54 -inf 39 57 -inf 39 59 -inf 39 61 -inf 39 63 -inf 39 65 -inf 39 68 30 39 70 30 39 72 30 39 74 30 39 77 30 39 79 30 39 81 30 39 83 30 39 86 30 39 88 30 39 90 30 39 92 30 41 1 30 41 3 30 41 5 30 41 7 30 41 10 30 41 12 30 41 14 30 41 16 30 41 18 30 41 21 30 41 23 30 41 25 30 41 27 30 41 30 -inf 41 32 -inf 41 35 -inf 41 37 -inf 41 39 -inf 41 43 -inf 41 46 -inf 41 48 -inf 41 50 -inf 41 52 -inf 41 54 -inf 41 57 -inf 41 59 -inf 41 61 -inf 41 63 -inf 41 65 -inf 41 68 30 41 70 30 41 72 30 41 74 30 41 77 30 41 79 30 41 81 30 41 83 30 41 86 30 41 88 30 41 90 30 41 92 30 43 1 30 43 3 30 43 5 30 43 7 30 43 10 30 43 12 30 43 14 30 43 16 30 43 18 30 43 21 30 43 23 30 43 25 30 43 27 30 43 30 -inf 43 32 -inf 43 35 -inf 43 37 -inf 43 39 -inf 43 41 -inf 43 46 -inf 43 48 -inf 43 50 -inf 43 52 -inf 43 54 -inf 43 57 -inf 43 59 -inf 43 61 -inf 43 63 -inf 43 65 -inf 43 68 30 43 70 30 43 72 30 43 74 30 43 77 30 43 79 30 43 81 30 43 83 30 43 86 30 43 88 30 43 90 30 43 92 30 46 1 30 46 3 30 46 5 30 46 7 30 46 10 30 46 12 30 46 14 30 46 16 30 46 18 30 46 21 30 46 23 30 46 25 30 46 27 30 46 30 -inf 46 32 -inf 46 35 -inf 46 37 -inf 46 39 -inf 46 41 -inf 46 43 -inf 46 48 -inf 46 50 -inf 46 52 -inf 46 54 -inf 46 57 -inf 46 59 -inf 46 61 -inf 46 63 -inf 46 65 -inf 46 68 30 46 70 30 46 72 30 46 74 30 46 77 30 46 79 30 46 81 30 46 83 30 46 86 30 46 88 30 46 90 30 46 92 30 48 1 30 48 3 30 48 5 30 48 7 30 48 10 30 48 12 30 48 14 30 48 16 30 48 18 30 48 21 30 48 23 30 48 25 30 48 27 30 48 30 -inf 48 32 -inf 48 35 -inf 48 37 -inf 48 39 -inf 48 41 -inf 48 43 -inf 48 46 -inf 48 50 -inf 48 52 -inf 48 54 -inf 48 57 -inf 48 59 -inf 48 61 -inf 48 63 -inf 48 65 -inf 48 68 30 48 70 30 48 72 30 48 74 30 48 77 30 48 79 30 48 81 30 48 83 30 48 86 30 48 88 30 48 90 30 48 92 30 50 1 30 50 3 30 50 5 30 50 7 30 50 10 30 50 12 30 50 14 30 50 16 30 50 18 30 50 21 30 50 23 30 50 25 30 50 27 30 50 30 -inf 50 32 -inf 50 35 -inf 50 37 -inf 50 39 -inf 50 41 -inf 50 43 -inf 50 46 -inf 50 48 -inf 50 52 -inf 50 54 -inf 50 57 -inf 50 59 -inf 50 61 -inf 50 63 -inf 50 65 -inf 50 68 30 50 70 30 50 72 30 50 74 30 50 77 30 50 79 30 50 81 30 50 83 30 50 86 30 50 88 30 50 90 30 50 92 30 52 1 30 52 3 30 52 5 30 52 7 30 52 10 30 52 12 30 52 14 30 52 16 30 52 18 30 52 21 30 52 23 30 52 25 30 52 27 30 52 30 -inf 52 32 -inf 52 35 -inf 52 37 -inf 52 39 -inf 52 41 -inf 52 43 -inf 52 46 -inf 52 48 -inf 52 50 -inf 52 54 -inf 52 57 -inf 52 59 -inf 52 61 -inf 52 63 -inf 52 65 -inf 52 68 30 52 70 30 52 72 30 52 74 30 52 77 30 52 79 30 52 81 30 52 83 30 52 86 30 52 88 30 52 90 30 52 92 30 54 1 30 54 3 30 54 5 30 54 7 30 54 10 30 54 12 30 54 14 30 54 16 30 54 18 30 54 21 30 54 23 30 54 25 30 54 27 30 54 30 -inf 54 32 -inf 54 35 -inf 54 37 -inf 54 39 -inf 54 41 -inf 54 43 -inf 54 46 -inf 54 48 -inf 54 50 -inf 54 52 -inf 54 57 -inf 54 59 -inf 54 61 -inf 54 63 -inf 54 65 -inf 54 68 30 54 70 30 54 72 30 54 74 30 54 77 30 54 79 30 54 81 30 54 83 30 54 86 30 54 88 30 54 90 30 54 92 30 57 1 30 57 3 30 57 5 30 57 7 30 57 10 30 57 12 30 57 14 30 57 16 30 57 18 30 57 21 30 57 23 30 57 25 30 57 27 30 57 30 -inf 57 32 -inf 57 35 -inf 57 37 -inf 57 39 -inf 57 41 -inf 57 43 -inf 57 46 -inf 57 48 -inf 57 50 -inf 57 52 -inf 57 54 -inf 57 59 -inf 57 61 -inf 57 63 -inf 57 65 -inf 57 68 30 57 70 30 57 72 30 57 74 30 57 77 30 57 79 30 57 81 30 57 83 30 57 86 30 57 88 30 57 90 30 57 92 30 59 1 30 59 3 30 59 5 30 59 7 30 59 10 30 59 12 30 59 14 30 59 16 30 59 18 30 59 21 30 59 23 30 59 25 30 59 27 30 59 30 -inf 59 32 -inf 59 35 -inf 59 37 -inf 59 39 -inf 59 41 -inf 59 43 -inf 59 46 -inf 59 48 -inf 59 50 -inf 59 52 -inf 59 54 -inf 59 57 -inf 59 61 -inf 59 63 -inf 59 65 -inf 59 68 30 59 70 30 59 72 30 59 74 30 59 77 30 59 79 30 59 81 30 59 83 30 59 86 30 59 88 30 59 90 30 59 92 30 61 1 30 61 3 30 61 5 30 61 7 30 61 10 30 61 12 30 61 14 30 61 16 30 61 18 30 61 21 30 61 23 30 61 25 30 61 27 30 61 30 -inf 61 32 -inf 61 35 -inf 61 37 -inf 61 39 -inf 61 41 -inf 61 43 -inf 61 46 -inf 61 48 -inf 61 50 -inf 61 52 -inf 61 54 -inf 61 57 -inf 61 59 -inf 61 63 -inf 61 65 -inf 61 68 30 61 70 30 61 72 30 61 74 30 61 77 30 61 79 30 61 81 30 61 83 30 61 86 30 61 88 30 61 90 30 61 92 30 63 1 30 63 3 30 63 5 30 63 7 30 63 10 30 63 12 30 63 14 30 63 16 30 63 18 30 63 21 30 63 23 30 63 25 30 63 27 30 63 30 -inf 63 32 -inf 63 35 -inf 63 37 -inf 63 39 -inf 63 41 -inf 63 43 -inf 63 46 -inf 63 48 -inf 63 50 -inf 63 52 -inf 63 54 -inf 63 57 -inf 63 59 -inf 63 61 -inf 63 65 -inf 63 68 30 63 70 30 63 72 30 63 74 30 63 77 30 63 79 30 63 81 30 63 83 30 63 86 30 63 88 30 63 90 30 63 92 30 65 1 30 65 3 30 65 5 30 65 7 30 65 10 30 65 12 30 65 14 30 65 16 30 65 18 30 65 21 30 65 23 30 65 25 30 65 27 30 65 30 -inf 65 32 -inf 65 35 -inf 65 37 -inf 65 39 -inf 65 41 -inf 65 43 -inf 65 46 -inf 65 48 -inf 65 50 -inf 65 52 -inf 65 54 -inf 65 57 -inf 65 59 -inf 65 61 -inf 65 63 -inf 65 68 30 65 70 30 65 72 30 65 74 30 65 77 30 65 79 30 65 81 30 65 83 30 65 86 30 65 88 30 65 90 30 65 92 30 68 1 -inf 68 3 -inf 68 5 -inf 68 7 -inf 68 10 30 68 12 30 68 14 30 68 16 30 68 18 30 68 21 -inf 68 23 -inf 68 25 -inf 68 27 -inf 68 30 30 68 32 30 68 35 30 68 37 30 68 39 30 68 41 30 68 43 30 68 46 30 68 48 30 68 50 30 68 52 30 68 54 30 68 57 30 68 59 30 68 61 30 68 63 30 68 65 30 68 70 -inf 68 72 -inf 68 74 -inf 68 77 -inf 68 79 -inf 68 81 -inf 68 83 -inf 68 86 -inf 68 88 -inf 68 90 -inf 68 92 -inf 70 1 -inf 70 3 -inf 70 5 -inf 70 7 -inf 70 10 30 70 12 30 70 14 30 70 16 30 70 18 30 70 21 -inf 70 23 -inf 70 25 -inf 70 27 -inf 70 30 30 70 32 30 70 35 30 70 37 30 70 39 30 70 41 30 70 43 30 70 46 30 70 48 30 70 50 30 70 52 30 70 54 30 70 57 30 70 59 30 70 61 30 70 63 30 70 65 30 70 68 -inf 70 72 -inf 70 74 -inf 70 77 -inf 70 79 -inf 70 81 -inf 70 83 -inf 70 86 -inf 70 88 -inf 70 90 -inf 70 92 -inf 72 1 -inf 72 3 -inf 72 5 -inf 72 7 -inf 72 10 30 72 12 30 72 14 30 72 16 30 72 18 30 72 21 -inf 72 23 -inf 72 25 -inf 72 27 -inf 72 30 30 72 32 30 72 35 30 72 37 30 72 39 30 72 41 30 72 43 30 72 46 30 72 48 30 72 50 30 72 52 30 72 54 30 72 57 30 72 59 30 72 61 30 72 63 30 72 65 30 72 68 -inf 72 70 -inf 72 74 -inf 72 77 -inf 72 79 -inf 72 81 -inf 72 83 -inf 72 86 -inf 72 88 -inf 72 90 -inf 72 92 -inf 74 1 -inf 74 3 -inf 74 5 -inf 74 7 -inf 74 10 30 74 12 30 74 14 30 74 16 30 74 18 30 74 21 -inf 74 23 -inf 74 25 -inf 74 27 -inf 74 30 30 74 32 30 74 35 30 74 37 30 74 39 30 74 41 30 74 43 30 74 46 30 74 48 30 74 50 30 74 52 30 74 54 30 74 57 30 74 59 30 74 61 30 74 63 30 74 65 30 74 68 -inf 74 70 -inf 74 72 -inf 74 77 -inf 74 79 -inf 74 81 -inf 74 83 -inf 74 86 -inf 74 88 -inf 74 90 -inf 74 92 -inf 77 1 -inf 77 3 -inf 77 5 -inf 77 7 -inf 77 10 30 77 12 30 77 14 30 77 16 30 77 18 30 77 21 -inf 77 23 -inf 77 25 -inf 77 27 -inf 77 30 30 77 32 30 77 35 30 77 37 30 77 39 30 77 41 30 77 43 30 77 46 30 77 48 30 77 50 30 77 52 30 77 54 30 77 57 30 77 59 30 77 61 30 77 63 30 77 65 30 77 68 -inf 77 70 -inf 77 72 -inf 77 74 -inf 77 79 -inf 77 81 -inf 77 83 -inf 77 86 -inf 77 88 -inf 77 90 -inf 77 92 -inf 79 1 -inf 79 3 -inf 79 5 -inf 79 7 -inf 79 10 30 79 12 30 79 14 30 79 16 30 79 18 30 79 21 -inf 79 23 -inf 79 25 -inf 79 27 -inf 79 30 30 79 32 30 79 35 30 79 37 30 79 39 30 79 41 30 79 43 30 79 46 30 79 48 30 79 50 30 79 52 30 79 54 30 79 57 30 79 59 30 79 61 30 79 63 30 79 65 30 79 68 -inf 79 70 -inf 79 72 -inf 79 74 -inf 79 77 -inf 79 81 -inf 79 83 -inf 79 86 -inf 79 88 -inf 79 90 -inf 79 92 -inf 81 1 -inf 81 3 -inf 81 5 -inf 81 7 -inf 81 10 30 81 12 30 81 14 30 81 16 30 81 18 30 81 21 -inf 81 23 -inf 81 25 -inf 81 27 -inf 81 30 30 81 32 30 81 35 30 81 37 30 81 39 30 81 41 30 81 43 30 81 46 30 81 48 30 81 50 30 81 52 30 81 54 30 81 57 30 81 59 30 81 61 30 81 63 30 81 65 30 81 68 -inf 81 70 -inf 81 72 -inf 81 74 -inf 81 77 -inf 81 79 -inf 81 83 -inf 81 86 -inf 81 88 -inf 81 90 -inf 81 92 -inf 83 1 -inf 83 3 -inf 83 5 -inf 83 7 -inf 83 10 30 83 12 30 83 14 30 83 16 30 83 18 30 83 21 -inf 83 23 -inf 83 25 -inf 83 27 -inf 83 30 30 83 32 30 83 35 30 83 37 30 83 39 30 83 41 30 83 43 30 83 46 30 83 48 30 83 50 30 83 52 30 83 54 30 83 57 30 83 59 30 83 61 30 83 63 30 83 65 30 83 68 -inf 83 70 -inf 83 72 -inf 83 74 -inf 83 77 -inf 83 79 -inf 83 81 -inf 83 86 -inf 83 88 -inf 83 90 -inf 83 92 -inf 86 1 -inf 86 3 -inf 86 5 -inf 86 7 -inf 86 10 30 86 12 30 86 14 30 86 16 30 86 18 30 86 21 -inf 86 23 -inf 86 25 -inf 86 27 -inf 86 30 30 86 32 30 86 35 30 86 37 30 86 39 30 86 41 30 86 43 30 86 46 30 86 48 30 86 50 30 86 52 30 86 54 30 86 57 30 86 59 30 86 61 30 86 63 30 86 65 30 86 68 -inf 86 70 -inf 86 72 -inf 86 74 -inf 86 77 -inf 86 79 -inf 86 81 -inf 86 83 -inf 86 88 -inf 86 90 -inf 86 92 -inf 88 1 -inf 88 3 -inf 88 5 -inf 88 7 -inf 88 10 30 88 12 30 88 14 30 88 16 30 88 18 30 88 21 -inf 88 23 -inf 88 25 -inf 88 27 -inf 88 30 30 88 32 30 88 35 30 88 37 30 88 39 30 88 41 30 88 43 30 88 46 30 88 48 30 88 50 30 88 52 30 88 54 30 88 57 30 88 59 30 88 61 30 88 63 30 88 65 30 88 68 -inf 88 70 -inf 88 72 -inf 88 74 -inf 88 77 -inf 88 79 -inf 88 81 -inf 88 83 -inf 88 86 -inf 88 90 -inf 88 92 -inf 90 1 -inf 90 3 -inf 90 5 -inf 90 7 -inf 90 10 30 90 12 30 90 14 30 90 16 30 90 18 30 90 21 -inf 90 23 -inf 90 25 -inf 90 27 -inf 90 30 30 90 32 30 90 35 30 90 37 30 90 39 30 90 41 30 90 43 30 90 46 30 90 48 30 90 50 30 90 52 30 90 54 30 90 57 30 90 59 30 90 61 30 90 63 30 90 65 30 90 68 -inf 90 70 -inf 90 72 -inf 90 74 -inf 90 77 -inf 90 79 -inf 90 81 -inf 90 83 -inf 90 86 -inf 90 88 -inf 90 92 -inf 92 1 -inf 92 3 -inf 92 5 -inf 92 7 -inf 92 10 30 92 12 30 92 14 30 92 16 30 92 18 30 92 21 -inf 92 23 -inf 92 25 -inf 92 27 -inf 92 30 30 92 32 30 92 35 30 92 37 30 92 39 30 92 41 30 92 43 30 92 46 30 92 48 30 92 50 30 92 52 30 92 54 30 92 57 30 92 59 30 92 61 30 92 63 30 92 65 30 92 68 -inf 92 70 -inf 92 72 -inf 92 74 -inf 92 77 -inf 92 79 -inf 92 81 -inf 92 83 -inf 92 86 -inf 92 88 -inf 92 90 -inf
5000 3 1722 1 3 -inf 1 5 -inf 1 7 -inf 1 10 30 1 12 30 1 14 30 1 16 30 1 18 30 1 21 -inf 1 23 -inf 1 25 -inf 1 27 -inf 1 30 30 1 32 30 1 35 30 1 37 30 1 39 30 1 41 30 1 43 30 1 46 30 1 48 30 1 50 30 1 52 30 1 54 30 1 57 30 1 59 30 1 61 30 1 63 30 1 65 30 1 68 -inf 1 70 -inf 1 72 -inf 1 74 -inf 1 77 -inf 1 79 -inf 1 81 -inf 1 83 -inf 1 86 -inf 1 88 -inf 1 90 -inf 1 92 -inf 3 1 -inf 3 5 -inf 3 7 -inf 3 10 30 3 12 30 3 14 30 3 16 30 3 18 30 3 21 -inf 3 23 -inf 3 25 -inf 3 27 -inf 3 30 30 3 32 30 3 35 30 3 37 30 3 39 30 3 41 30 3 43 30 3 46 30 3 48 30 3 50 30 3 52 30 3 54 30 3 57 30 3 59 30 3 61 30 3 63 30 3 65 30 3 68 -inf 3 70 -inf 3 72 -inf 3 74 -inf 3 77 -inf 3 79 -inf 3 81 -inf 3 83 -inf 3 86 -inf 3 88 -inf 3 90 -inf 3 92 -inf 5 1 -inf 5 3 -inf 5 7 -inf 5 10 30 5 12 30 5 14 30 5 16 30 5 18 30 5 21 -inf 5 23 -inf 5 25 -inf 5 27 -inf 5 30 30 5 32 30 5 35 30 5 37 30 5 39 30 5 41 30 5 43 30 5 46 30 5 48 30 5 50 30 5 52 30 5 54 30 5 57 30 5 59 30 5 61 30 5 63 30 5 65 30 5 68 -inf 5 70 -inf 5 72 -inf 5 74 -inf 5 77 -inf 5 79 -inf 5 81 -inf 5 83 -inf 5 86 -inf 5 88 -inf 5 90 -inf 5 92 -inf 7 1 -inf 7 3 -inf 7 5 -inf 7 10 30 7 12 30 7 14 30 7 16 30 7 18 30 7 21 -inf 7 23 -inf 7 25 -inf 7 27 -inf 7 30 30 7 32 30 7 35 30 7 37 30 7 39 30 7 41 30 7 43 30 7 46 30 7 48 30 7 50 30 7 52 30 7 54 30 7 57 30 7 59 30 7 61 30 7 63 30 7 65 30 7 68 -inf 7 70 -inf 7 72 -inf 7 74 -inf 7 77 -inf 7 79 -inf 7 81 -inf 7 83 -inf 7 86 -inf 7 88 -inf 7 90 -inf 7 92 -inf 10 1 30 10 3 30 10 5 30 10 7 30 10 12 -inf 10 14 -inf 10 16 -inf 10 18 -inf 10 21 30 10 23 30 10 25 30 10 27 30 10 30 30 10 32 30 10 35 30 10 37 30 10 39 30 10 41 30 10 43 30 10 46 30 10 48 30 10 50 30 10 52 30 10 54 30 10 57 30 10 59 30 10 61 30 10 63 30 10 65 30 10 68 30 10 70 30 10 72 30 10 74 30 10 77 30 10 79 30 10 81 30 10 83 30 10 86 30 10 88 30 10 90 30 10 92 30 12 1 30 12 3 30 12 5 30 12 7 30 12 10 -inf 12 14 -inf 12 16 -inf 12 18 -inf 12 21 30 12 23 30 12 25 30 12 27 30 12 30 30 12 32 30 12 35 30 12 37 30 12 39 30 12 41 30 12 43 30 12 46 30 12 48 30 12 50 30 12 52 30 12 54 30 12 57 30 12 59 30 12 61 30 12 63 30 12 65 30 12 68 30 12 70 30 12 72 30 12 74 30 12 77 30 12 79 30 12 81 30 12 83 30 12 86 30 12 88 30 12 90 30 12 92 30 14 1 30 14 3 30 14 5 30 14 7 30 14 10 -inf 14 12 -inf 14 16 -inf 14 18 -inf 14 21 30 14 23 30 14 25 30 14 27 30 14 30 30 14 32 30 14 35 30 14 37 30 14 39 30 14 41 30 14 43 30 14 46 30 14 48 30 14 50 30 14 52 30 14 54 30 14 57 30 14 59 30 14 61 30 14 63 30 14 65 30 14 68 30 14 70 30 14 72 30 14 74 30 14 77 30 14 79 30 14 81 30 14 83 30 14 86 30 14 88 30 14 90 30 14 92 30 16 1 30 16 3 30 16 5 30 16 7 30 16 10 -inf 16 12 -inf 16 14 -inf 16 18 -inf 16 21 30 16 23 30 16 25 30 16 27 30 16 30 30 16 32 30 16 35 30 16 37 30 16 39 30 16 41 30 16 43 30 16 46 30 16 48 30 16 50 30 16 52 30 16 54 30 16 57 30 16 59 30 16 61 30 16 63 30 16 65 30 16 68 30 16 70 30 16 72 30 16 74 30 16 77 30 16 79 30 16 81 30 16 83 30 16 86 30 16 88 30 16 90 30 16 92 30 18 1 30 18 3 30 18 5 30 18 7 30 18 10 -inf 18 12 -inf 18 14 -inf 18 16 -inf 18 21 30 18 23 30 18 25 30 18 27 30 18 30 30 18 32 30 18 35 30 18 37 30 18 39 30 18 41 30 18 43 30 18 46 30 18 48 30 18 50 30 18 52 30 18 54 30 18 57 30 18 59 30 18 61 30 18 63 30 18 65 30 18 68 30 18 70 30 18 72 30 18 74 30 18 77 30 18 79 30 18 81 30 18 83 30 18 86 30 18 88 30 18 90 30 18 92 30 21 1 -inf 21 3 -inf 21 5 -inf 21 7 -inf 21 10 30 21 12 30 21 14 30 21 16 30 21 18 30 21 23 -inf 21 25 -inf 21 27 -inf 21 30 30 21 32 30 21 35 30 21 37 30 21 39 30 21 41 30 21 43 30 21 46 30 21 48 30 21 50 30 21 52 30 21 54 30 21 57 30 21 59 30 21 61 30 21 63 30 21 65 30 21 68 -inf 21 70 -inf 21 72 -inf 21 74 -inf 21 77 -inf 21 79 -inf 21 81 -inf 21 83 -inf 21 86 -inf 21 88 -inf 21 90 -inf 21 92 -inf 23 1 -inf 23 3 -inf 23 5 -inf 23 7 -inf 23 10 30 23 12 30 23 14 30 23 16 30 23 18 30 23 21 -inf 23 25 -inf 23 27 -inf 23 30 30 23 32 30 23 35 30 23 37 30 23 39 30 23 41 30 23 43 30 23 46 30 23 48 30 23 50 30 23 52 30 23 54 30 23 57 30 23 59 30 23 61 30 23 63 30 23 65 30 23 68 -inf 23 70 -inf 23 72 -inf 23 74 -inf 23 77 -inf 23 79 -inf 23 81 -inf 23 83 -inf 23 86 -inf 23 88 -inf 23 90 -inf 23 92 -inf 25 1 -inf 25 3 -inf 25 5 -inf 25 7 -inf 25 10 30 25 12 30 25 14 30 25 16 30 25 18 30 25 21 -inf 25 23 -inf 25 27 -inf 25 30 30 25 32 30 25 35 30 25 37 30 25 39 30 25 41 30 25 43 30 25 46 30 25 48 30 25 50 30 25 52 30 25 54 30 25 57 30 25 59 30 25 61 30 25 63 30 25 65 30 25 68 -inf 25 70 -inf 25 72 -inf 25 74 -inf 25 77 -inf 25 79 -inf 25 81 -inf 25 83 -inf 25 86 -inf 25 88 -inf 25 90 -inf 25 92 -inf 27 1 -inf 27 3 -inf 27 5 -inf 27 7 -inf 27 10 30 27 12 30 27 14 30 27 16 30 27 18 30 27 21 -inf 27 23 -inf 27 25 -inf 27 30 30 27 32 30 27 35 30 27 37 30 27 39 30 27 41 30 27 43 30 27 46 30 27 48 30 27 50 30 27 52 30 27 54 30 27 57 30 27 59 30 27 61 30 27 63 30 27 65 30 27 68 -inf 27 70 -inf 27 72 -inf 27 74 -inf 27 77 -inf 27 79 -inf 27 81 -inf 27 83 -inf 27 86 -inf 27 88 -inf 27 90 -inf 27 92 -inf 30 1 30 30 3 30 30 5 30 30 7 30 30 10 30 30 12 30 30 14 30 30 16 30 30 18 30 30 21 30 30 23 30 30 25 30 30 27 30 30 32 -inf 30 35 -inf 30 37 -inf 30 39 -inf 30 41 -inf 30 43 -inf 30 46 -inf 30 48 -inf 30 50 -inf 30 52 -inf 30 54 -inf 30 57 -inf 30 59 -inf 30 61 -inf 30 63 -inf 30 65 -inf 30 68 30 30 70 30 30 72 30 30 74 30 30 77 30 30 79 30 30 81 30 30 83 30 30 86 30 30 88 30 30 90 30 30 92 30 32 1 30 32 3 30 32 5 30 32 7 30 32 10 30 32 12 30 32 14 30 32 16 30 32 18 30 32 21 30 32 23 30 32 25 30 32 27 30 32 30 -inf 32 35 -inf 32 37 -inf 32 39 -inf 32 41 -inf 32 43 -inf 32 46 -inf 32 48 -inf 32 50 -inf 32 52 -inf 32 54 -inf 32 57 -inf 32 59 -inf 32 61 -inf 32 63 -inf 32 65 -inf 32 68 30 32 70 30 32 72 30 32 74 30 32 77 30 32 79 30 32 81 30 32 83 30 32 86 30 32 88 30 32 90 30 32 92 30 35 1 30 35 3 30 35 5 30 35 7 30 35 10 30 35 12 30 35 14 30 35 16 30 35 18 30 35 21 30 35 23 30 35 25 30 35 27 30 35 30 -inf 35 32 -inf 35 37 -inf 35 39 -inf 35 41 -inf 35 43 -inf 35 46 -inf 35 48 -inf 35 50 -inf 35 52 -inf 35 54 -inf 35 57 -inf 35 59 -inf 35 61 -inf 35 63 -inf 35 65 -inf 35 68 30 35 70 30 35 72 30 35 74 30 35 77 30 35 79 30 35 81 30 35 83 30 35 86 30 35 88 30 35 90 30 35 92 30 37 1 30 37 3 30 37 5 30 37 7 30 37 10 30 37 12 30 37 14 30 37 16 30 37 18 30 37 21 30 37 23 30 37 25 30 37 27 30 37 30 -inf 37 32 -inf 37 35 -inf 37 39 -inf 37 41 -inf 37 43 -inf 37 46 -inf 37 48 -inf 37 50 -inf 37 52 -inf 37 54 -inf 37 57 -inf 37 59 -inf 37 61 -inf 37 63 -inf 37 65 -inf 37 68 30 37 70 30 37 72 30 37 74 30 37 77 30 37 79 30 37 81 30 37 83 30 37 86 30 37 88 30 37 90 30 37 92 30 39 1 30 39 3 30 39 5 30 39 7 30 39 10 30 39 12 30 39 14 30 39 16 30 39 18 30 39 21 30 39 23 30 39 25 30 39 27 30 39 30 -inf 39 32 -inf 39 35 -inf 39 37 -inf 39 41 -inf 39 43 -inf 39 46 -inf 39 48 -inf 39 50 -inf 39 52 -inf 39 54 -inf 39 57 -inf 39 59 -inf 39 61 -inf 39 63 -inf 39 65 -inf 39 68 30 39 70 30 39 72 30 39 74 30 39 77 30 39 79 30 39 81 30 39 83 30 39 86 30 39 88 30 39 90 30 39 92 30 41 1 30 41 3 30 41 5 30 41 7 30 41 10 30 41 12 30 41 14 30 41 16 30 41 18 30 41 21 30 41 23 30 41 25 30 41 27 30 41 30 -inf 41 32 -inf 41 35 -inf 41 37 -inf 41 39 -inf 41 43 -inf 41 46 -inf 41 48 -inf 41 50 -inf 41 52 -inf 41 54 -inf 41 57 -inf 41 59 -inf 41 61 -inf 41 63 -inf 41 65 -inf 41 68 30 41 70 30 41 72 30 41 74 30 41 77 30 41 79 30 41 81 30 41 83 30 41 86 30 41 88 30 41 90 30 41 92 30 43 1 30 43 3 30 43 5 30 43 7 30 43 10 30 43 12 30 43 14 30 43 16 30 43 18 30 43 21 30 43 23 30 43 25 30 43 27 30 43 30 -inf 43 32 -inf 43 35 -inf 43 37 -inf 43 39 -inf 43 41 -inf 43 46 -inf 43 48 -inf 43 50 -inf 43 52 -inf 43 54 -inf 43 57 -inf 43 59 -inf 43 61 -inf 43 63 -inf 43 65 -inf 43 68 30 43 70 30 43 72 30 43 74 30 43 77 30 43 79 30 43 81 30 43 83 30 43 86 30 43 88 30 43 90 30 43 92 30 46 1 30 46 3 30 46 5 30 46 7 30 46 10 30 46 12 30 46 14 30 46 16 30 46 18 30 46 21 30 46 23 30 46 25 30 46 27 30 46 30 -inf 46 32 -inf 46 35 -inf 46 37 -inf 46 39 -inf 46 41 -inf 46 43 -inf 46 48 -inf 46 50 -inf 46 52 -inf 46 54 -inf 46 57 -inf 46 59 -inf 46 61 -inf 46 63 -inf 46 65 -inf 46 68 30 46 70 30 46 72 30 46 74 30 46 77 30 46 79 30 46 81 30 46 83 30 46 86 30 46 88 30 46 90 30 46 92 30 48 1 30 48 3 30 48 5 30 48 7 30 48 10 30 48 12 30 48 14 30 48 16 30 48 18 30 48 21 30 48 23 30 48 25 30 48 27 30 48 30 -inf 48 32 -inf 48 35 -inf 48 37 -inf 48 39 -inf 48 41 -inf 48 43 -inf 48 46 -inf 48 50 -inf 48 52 -inf 48 54 -inf 48 57 -inf 48 59 -inf 48 61 -inf 48 63 -inf 48 65 -inf 48 68 30 48 70 30 48 72 30 48 74 30 48 77 30 48 79 30 48 81 30 48 83 30 48 86 30 48 88 30 48 90 30 48 92 30 50 1 30 50 3 30 50 5 30 50 7 30 50 10 30 50 12 30 50 14 30 50 16 30 50 18 30 50 21 30 50 23 30 50 25 30 50 27 30 50 30 -inf 50 32 -inf 50 35 -inf 50 37 -inf 50 39 -inf 50 41 -inf 50 43 -inf 50 46 -inf 50 48 -inf 50 52 -inf 50 54 -inf 50 57 -inf 50 59 -inf 50 61 -inf 50 63 -inf 50 65 -inf 50 68 30 50 70 30 50 72 30 50 74 30 50 77 30 50 79 30 50 81 30 50 83 30 50 86 30 50 88 30 50 90 30 50 92 30 52 1 30 52 3 30 52 5 30 52 7 30 52 10 30 52 12 30 52 14 30 52 16 30 52 18 30 52 21 30 52 23 30 52 25 30 52 27 30 52 30 -inf 52 32 -inf 52 35 -inf 52 37 -inf 52 39 -inf 52 41 -inf 52 43 -inf 52 46 -inf 52 48 -inf 52 50 -inf 52 54 -inf 52 57 -inf 52 59 -inf 52 61 -inf 52 63 -inf 52 65 -inf 52 68 30 52 70 30 52 72 30 52 74 30 52 77 30 52 79 30 52 81 30 52 83 30 52 86 30 52 88 30 52 90 30 52 92 30 54 1 30 54 3 30 54 5 30 54 7 30 54 10 30 54 12 30 54 14 30 54 16 30 54 18 30 54 21 30 54 23 30 54 25 30 54 27 30 54 30 -inf 54 32 -inf 54 35 -inf 54 37 -inf 54 39 -inf 54 41 -inf 54 43 -inf 54 46 -inf 54 48 -inf 54 50 -inf 54 52 -inf 54 57 -inf 54 59 -inf 54 61 -inf 54 63 -inf 54 65 -inf 54 68 30 54 70 30 54 72 30 54 74 30 54 77 30 54 79 30 54 81 30 54 83 30 54 86 30 54 88 30 54 90 30 54 92 30 57 1 30 57 3 30 57 5 30 57 7 30 57 10 30 57 12 30 57 14 30 57 16 30 57 18 30 57 21 30 57 23 30 57 25 30 57 27 30 57 30 -inf 57 32 -inf 57 35 -inf 57 37 -inf 57 39 -inf 57 41 -inf 57 43 -inf 57 46 -inf 57 48 -inf 57 50 -inf 57 52 -inf 57 54 -inf 57 59 -inf 57 61 -inf 57 63 -inf 57 65 -inf 57 68 30 57 70 30 57 72 30 57 74 30 57 77 30 57 79 30 57 81 30 57 83 30 57 86 30 57 88 30 57 90 30 57 92 30 59 1 30 59 3 30 59 5 30 59 7 30 59 10 30 59 12 30 59 14 30 59 16 30 59 18 30 59 21 30 59 23 30 59 25 30 59 27 30 59 30 -inf 59 32 -inf 59 35 -inf 59 37 -inf 59 39 -inf 59 41 -inf 59 43 -inf 59 46 -inf 59 48 -inf 59 50 -inf 59 52 -inf 59 54 -inf 59 57 -inf 59 61 -inf 59 63 -inf 59 65 -inf 59 68 30 59 70 30 59 72 30 59 74 30 59 77 30 59 79 30 59 81 30 59 83 30 59 86 30 59 88 30 59 90 30 59 92 30 61 1 30 61 3 30 61 5 30 61 7 30 61 10 30 61 12 30 61 14 30 61 16 30 61 18 30 61 21 30 61 23 30 61 25 30 61 27 30 61 30 -inf 61 32 -inf 61 35 -inf 61 37 -inf 61 39 -inf 61 41 -inf 61 43 -inf 61 46 -inf 61 48 -inf 61 50 -inf 61 52 -inf 61 54 -inf 61 57 -inf 61 59 -inf 61 63 -inf 61 65 -inf 61 68 30 61 70 30 61 72 30 61 74 30 61 77 30 61 79 30 61 81 30 61 83 30 61 86 30 61 88 30 61 90 30 61 92 30 63 1 30 63 3 30 63 5 30 63 7 30 63 10 30 63 12 30 63 14 30 63 16 30 63 18 30 63 21 30 63 23 30 63 25 30 63 27 30 63 30 -inf 63 32 -inf 63 35 -inf 63 37 -inf 63 39 -inf 63 41 -inf 63 43 -inf 63 46 -inf 63 48 -inf 63 50 -inf 63 52 -inf 63 54 -inf 63 57 -inf 63 59 -inf 63 61 -inf 63 65 -inf 63 68 30 63 70 30 63 72 30 63 74 30 63 77 30 63 79 30 63 81 30 63 83 30 63 86 30 63 88 30 63 90 30 63 92 30 65 1 30 65 3 30 65 5 30 65 7 30 65 10 30 65 12 30 65 14 30 65 16 30 65 18 30 65 21 30 65 23 30 65 25 30 65 27 30 65 30 -inf 65 32 -inf 65 35 -inf 65 37 -inf 65 39 -inf 65 41 -inf 65 43 -inf 65 46 -inf 65 48 -inf 65 50 -inf 65 52 -inf 65 54 -inf 65 57 -inf 65 59 -inf 65 61 -inf 65 63 -inf 65 68 30 65 70 30 65 72 30 65 74 30 65 77 30 65 79 30 65 81 30 65 83 30 65 86 30 65 88 30 65 90 30 65 92 30 68 1 -inf 68 3 -inf 68 5 -inf 68 7 -inf 68 10 30 68 12 30 68 14 30 68 16 30 68 18 30 68 21 -inf 68 23 -inf 68 25 -inf 68 27 -inf 68 30 30 68 32 30 68 35 30 68 37 30 68 39 30 68 41 30 68 43 30 68 46 30 68 48 30 68 50 30 68 52 30 68 54 30 68 57 30 68 59 30 68 61 30 68 63 30 68 65 30 68 70 -inf 68 72 -inf 68 74 -inf 68 77 -inf 68 79 -inf 68 81 -inf 68 83 -inf 68 86 -inf 68 88 -inf 68 90 -inf 68 92 -inf 70 1 -inf 70 3 -inf 70 5 -inf 70 7 -inf 70 10 30 70 12 30 70 14 30 70 16 30 70 18 30 70 21 -inf 70 23 -inf 70 25 -inf 70 27 -inf 70 30 30 70 32 30 70 35 30 70 37 30 70 39 30 70 41 30 70 43 30 70 46 30 70 48 30 70 50 30 70 52 30 70 54 30 70 57 30 70 59 30 70 61 30 70 63 30 70 65 30 70 68 -inf 70 72 -inf 70 74 -inf 70 77 -inf 70 79 -inf 70 81 -inf 70 83 -inf 70 86 -inf 70 88 -inf 70 90 -inf 70 92 -inf 72 1 -inf 72 3 -inf 72 5 -inf 72 7 -inf 72 10 30 72 12 30 72 14 30 72 16 30 72 18 30 72 21 -inf 72 23 -inf 72 25 -inf 72 27 -inf 72 30 30 72 32 30 72 35 30 72 37 30 72 39 30 72 41 30 72 43 30 72 46 30 72 48 30 72 50 30 72 52 30 72 54 30 72 57 30 72 59 30 72 61 30 72 63 30 72 65 30 72 68 -inf 72 70 -inf 72 74 -inf 72 77 -inf 72 79 -inf 72 81 -inf 72 83 -inf 72 86 -inf 72 88 -inf 72 90 -inf 72 92 -inf 74 1 -inf 74 3 -inf 74 5 -inf 74 7 -inf 74 10 30 74 12 30 74 14 30 74 16 30 74 18 30 74 21 -inf 74 23 -inf 74 25 -inf 74 27 -inf 74 30 30 74 32 30 74 35 30 74 37 30 74 39 30 74 41 30 74 43 30 74 46 30 74 48 30 74 50 30 74 52 30 74 54 30 74 57 30 74 59 30 74 61 30 74 63 30 74 65 30 74 68 -inf 74 70 -inf 74 72 -inf 74 77 -inf 74 79 -inf 74 81 -inf 74 83 -inf 74 86 -inf 74 88 -inf 74 90 -inf 74 92 -inf 77 1 -inf 77 3 -inf 77 5 -inf 77 7 -inf 77 10 30 77 12 30 77 14 30 77 16 30 77 18 30 77 21 -inf 77 23 -inf 77 25 -inf 77 27 -inf 77 30 30 77 32 30 77 35 30 77 37 30 77 39 30 77 41 30 77 43 30 77 46 30 77 48 30 77 50 30 77 52 30 77 54 30 77 57 30 77 59 30 77 61 30 77 63 30 77 65 30 77 68 -inf 77 70 -inf 77 72 -inf 77 74 -inf 77 79 -inf 77 81 -inf 77 83 -inf 77 86 -inf 77 88 -inf 77 90 -inf 77 92 -inf 79 1 -inf 79 3 -inf 79 5 -inf 79 7 -inf 79 10 30 79 12 30 79 14 30 79 16 30 79 18 30 79 21 -inf 79 23 -inf 79 25 -inf 79 27 -inf 79 30 30 79 32 30 79 35 30 79 37 30 79 39 30 79 41 30 79 43 30 79 46 30 79 48 30 79 50 30 79 52 30 79 54 30 79 57 30 79 59 30 79 61 30 79 63 30 79 65 30 79 68 -inf 79 70 -inf 79 72 -inf 79 74 -inf 79 77 -inf 79 81 -inf 79 83 -inf 79 86 -inf 79 88 -inf 79 90 -inf 79 92 -inf 81 1 -inf 81 3 -inf 81 5 -inf 81 7 -inf 81 10 30 81 12 30 81 14 30 81 16 30 81 18 30 81 21 -inf 81 23 -inf 81 25 -inf 81 27 -inf 81 30 30 81 32 30 81 35 30 81 37 30 81 39 30 81 41 30 81 43 30 81 46 30 81 48 30 81 50 30 81 52 30 81 54 30 81 57 30 81 59 30 81 61 30 81 63 30 81 65 30 81 68 -inf 81 70 -inf 81 72 -inf 81 74 -inf 81 77 -inf 81 79 -inf 81 83 -inf 81 86 -inf 81 88 -inf 81 90 -inf 81 92 -inf 83 1 -inf 83 3 -inf 83 5 -inf 83 7 -inf 83 10 30 83 12 30 83 14 30 83 16 30 83 18 30 83 21 -inf 83 23 -inf 83 25 -inf 83 27 -inf 83 30 30 83 32 30 83 35 30 83 37 30 83 39 30 83 41 30 83 43 30 83 46 30 83 48 30 83 50 30 83 52 30 83 54 30 83 57 30 83 59 30 83 61 30 83 63 30 83 65 30 83 68 -inf 83 70 -inf 83 72 -inf 83 74 -inf 83 77 -inf 83 79 -inf 83 81 -inf 83 86 -inf 83 88 -inf 83 90 -inf 83 92 -inf 86 1 -inf 86 3 -inf 86 5 -inf 86 7 -inf 86 10 30 86 12 30 86 14 30 86 16 30 86 18 30 86 21 -inf 86 23 -inf 86 25 -inf 86 27 -inf 86 30 30 86 32 30 86 35 30 86 37 30 86 39 30 86 41 30 86 43 30 86 46 30 86 48 30 86 50 30 86 52 30 86 54 30 86 57 30 86 59 30 86 61 30 86 63 30 86 65 30 86 68 -inf 86 70 -inf 86 72 -inf 86 74 -inf 86 77 -inf 86 79 -inf 86 81 -inf 86 83 -inf 86 88 -inf 86 90 -inf 86 92 -inf 88 1 -inf 88 3 -inf 88 5 -inf 88 7 -inf 88 10 30 88 12 30 88 14 30 88 16 30 88 18 30 88 21 -inf 88 23 -inf 88 25 -inf 88 27 -inf 88 30 30 88 32 30 88 35 30 88 37 30 88 39 30 88 41 30 88 43 30 88 46 30 88 48 30 88 50 30 88 52 30 88 54 30 88 57 30 88 59 30 88 61 30 88 63 30 88 65 30 88 68 -inf 88 70 -inf 88 72 -inf 88 74 -inf 88 77 -inf 88 79 -inf 88 81 -inf 88 83 -inf 88 86 -inf 88 90 -inf 88 92 -inf 90 1 -inf 90 3 -inf 90 5 -inf 90 7 -inf 90 10 30 90 12 30 90 14 30 90 16 30 90 18 30 90 21 -inf 90 23 -inf 90 25 -inf 90 27 -inf 90 30 30 90 32 30 90 35 30 90 37 30 90 39 30 90 41 30 90 43 30 90 46 30 90 48 30 90 50 30 90 52 30 90 54 30 90 57 30 90 59 30 90 61 30 90 63 30 90 65 30 90 68 -inf 90 70 -inf 90 72 -inf 90 74 -inf 90 77 -inf 90 79 -inf 90 81 -inf 90 83 -inf 90 86 -inf 90 88 -inf 90 92 -inf 92 1 -inf 92 3 -inf 92 5 -inf 92 7 -inf 92 10 30 92 12 30 92 14 30 92 16 30 92 18 30 92 21 -inf 92 23 -inf 92 25 -inf 92 27 -inf 92 30 30 92 32 30 92 35 30 92 37 30 92 39 30 92 41 30 92 43 30 92 46 30 92 48 30 92 50 30 92 52 30 92 54 30 92 57 30 92 59 30 92 61 30 92 63 30 92 65 30 92 68 -inf 92 70 -inf 92 72 -inf 92 74 -inf 92 77 -inf 92 79 -inf 92 81 -inf 92 83 -inf 92 86 -inf 92 88 -inf 92 90 -inf
5000 3 1722 1 3 -inf 1 5 -inf 1 7 -inf 1 10 30 1 12 30 1 14 30 1 16 30 1 18 30 1 21 -inf 1 23 -inf 1 25 -inf 1 27 -inf 1 30 30 1 32 30 1 35 30 1 37 30 1 39 30 1 41 30 1 43 30 1 46 30 1 48 30 1 50 30 1 52 30 1 54 30 1 57 30 1 59 30 1 61 30 1 63 30 1 65 30 1 68 -inf 1 70 -inf 1 72 -inf 1 74 -inf 1 77 -inf 1 79 -inf 1 81 -inf 1 83 -inf 1 86 -inf 1 88 -inf 1 90 -inf 1 92 -inf 3 1 -inf 3 5 -inf 3 7 -inf 3 10 30 3 12 30 3 14 30 3 16 30 3 18 30 3 21 -inf 3 23 -inf 3 25 -inf 3 27 -inf 3 30 30 3 32 30 3 35 30 3 37 30 3 39 30 3 41 30 3 43 30 3 46 30 3 48 30 3 50 30 3 52 30 3 54 30 3 57 30 3 59 30 3 61 30 3 63 30 3 65 30 3 68 -inf 3 70 -inf 3 72 -inf 3 74 -inf 3 77 -inf 3 79 -inf 3 81 -inf 3 83 -inf 3 86 -inf 3 88 -inf 3 90 -inf 3 92 -inf 5 1 -inf 5 3 -inf 5 7 -inf 5 10 30 5 12 30 5 14 30 5 16 30 5 18 30 5 21 -inf 5 23 -inf 5 25 -inf 5 27 -inf 5 30 30 5 32 30 5 35 30 5 37 30 5 39 30 5 41 30 5 43 30 5 46 30 5 48 30 5 50 30 5 52 30 5 54 30 5 57 30 5 59 30 5 61 30 5 63 30 5 65 30 5 68 -inf 5 70 -inf 5 72 -inf 5 74 -inf 5 77 -inf 5 79 -inf 5 81 -inf 5 83 -inf 5 86 -inf 5 88 -inf 5 90 -inf 5 92 -inf 7 1 -inf 7 3 -inf 7 5 -inf 7 10 30 7 12 30 7 14 30 7 16 30 7 18 30 7 21 -inf 7 23 -inf 7 25 -inf 7 27 -inf 7 30 30 7 32 30 7 35 30 7 37 30 7 39 30 7 41 30 7 43 30 7 46 30 7 48 30 7 50 30 7 52 30 7 54 30 7 57 30 7 59 30 7 61 30 7 63 30 7 65 30 7 68 -inf 7 70 -inf 7 72 -inf 7 74 -inf 7 77 -inf 7 79 -inf 7 81 -inf 7 83 -inf 7 86 -inf 7 88 -inf 7 90 -inf 7 92 -inf 10 1 30 10 3 30 10 5 30 10 7 30 10 12 -inf 10 14 -inf 10 16 -inf 10 18 -inf 10 21 30 10 23 30 10 25 30 10 27 30 10 30 30 10 32 30 10 35 30 10 37 30 10 39 30 10 41 30 10 43 30 10 46 30 10 48 30 10 50 30 10 52 30 10 54 30 10 57 30 10 59 30 10 61 30 10 63 30 10 65 30 10 68 30 10 70 30 10 72 30 10 74 30 10 77 30 10 79 30 10 81 30 10 83 30 10 86 30 10 88 30 10 90 30 10 92 30 12 1 30 12 3 30 12 5 30 12 7 30 12 10 -inf 12 14 -inf 12 16 -inf 12 18 -inf 12 21 30 12 23 30 12 25 30 12 27 30 12 30 30 12 32 30 12 35 30 12 37 30 12 39 30 12 41 30 12 43 30 12 46 30 12 48 30 12 50 30 12 52 30 12 54 30 12 57 30 12 59 30 12 61 30 12 63 30 12 65 30 12 68 30 12 70 30 12 72 30 12 74 30 12 77 30 12 79 30 12 81 30 12 83 30 12 86 30 12 88 30 12 90 30 12 92 30 14 1 30 14 3 30 14 5 30 14 7 30 14 10 -inf 14 12 -inf 14 16 -inf 14 18 -inf 14 21 30 14 23 30 14 25 30 14 27 30 14 30 30 14 32 30 14 35 30 14 37 30 14 39 30 14 41 30 14 43 30 14 46 30 14 48 30 14 50 30 14 52 30 14 54 30 14 57 30 14 59 30 14 61 30 14 63 30 14 65 30 14 68 30 14 70 30 14 72 30 14 74 30 14 77 30 14 79 30 14 81 30 14 83 30 14 86 30 14 88 30 14 90 30 14 92 30 16 1 30 16 3 30 16 5 30 16 7 30 16 10 -inf 16 12 -inf 16 14 -inf 16 18 -inf 16 21 30 16 23 30 16 25 30 16 27 30 16 30 30 16 32 30 16 35 30 16 37 30 16 39 30 16 41 30 16 43 30 16 46 30 16 48 30 16 50 30 16 52 30 16 54 30 16 57 30 16 59 30 16 61 30 16 63 30 16 65 30 16 68 30 16 70 30 16 72 30 16 74 30 16 77 30 16 79 30 16 81 30 16 83 30 16 86 30 16 88 30 16 90 30 16 92 30 18 1 30 18 3 30 18 5 30 18 7 30 18 10 -inf 18 12 -inf 18 14 -inf 18 16 -inf 18 21 30 18 23 30 18 25 30 18 27 30 18 30 30 18 32 30 18 35 30 18 37 30 18 39 30 18 41 30 18 43 30 18 46 30 18 48 30 18 50 30 18 52 30 18 54 30 18 57 30 18 59 30 18 61 30 18 63 30 18 65 30 18 68 30 18 70 30 18 72 30 18 74 30 18 77 30 18 79 30 18 81 30 18 83 30 18 86 30 18 88 30 18 90 30 18 92 30 21 1 -inf 21 3 -inf 21 5 -inf 21 7 -inf 21 10 30 21 12 30 21 14 30 21 16 30 21 18 30 21 23 -inf 21 25 -inf 21 27 -inf 21 30 30 21 32 30 21 35 30 21 37 30 21 39 30 21 41 30 21 43 30 21 46 30 21 48 30 21 50 30 21 52 30 21 54 30 21 57 30 21 59 30 21 61 30 21 63 30 21 65 30 21 68 -inf 21 70 -inf 21 72 -inf 21 74 -inf 21 77 -inf 21 79 -inf 21 81 -inf 21 83 -inf 21 86 -inf 21 88 -inf 21 90 -inf 21 92 -inf 23 1 -inf 23 3 -inf 23 5 -inf 23 7 -inf 23 10 30 23 12 30 23 14 30 23 16 30 23 18 30 23 21 -inf 23 25 -inf 23 27 -inf 23 30 30 23 32 30 23 35 30 23 37 30 23 39 30 23 41 30 23 43 30 23 46 30 23 48 30 23 50 30 23 52 30 23 54 30 23 57 30 23 59 30 23 61 30 23 63 30 23 65 30 23 68 -inf 23 70 -inf 23 72 -inf 23 74 -inf 23 77 -inf 23 79 -inf 23 81 -inf 23 83 -inf 23 86 -inf 23 88 -inf 23 90 -inf 23 92 -inf 25 1 -inf 25 3 -inf 25 5 -inf 25 7 -inf 25 10 30 25 12 30 25 14 30 25 16 30 25 18 30 25 21 -inf 25 23 -inf 25 27 -inf 25 30 30 25 32 30 25 35 30 25 37 30 25 39 30 25 41 30 25 43 30 25 46 30 25 48 30 25 50 30 25 52 30 25 54 30 25 57 30 25 59 30 25 61 30 25 63 30 25 65 30 25 68 -inf 25 70 -inf 25 72 -inf 25 74 -inf 25 77 -inf 25 79 -inf 25 81 -inf 25 83 -inf 25 86 -inf 25 88 -inf 25 90 -inf 25 92 -inf 27 1 -inf 27 3 -inf 27 5 -inf 27 7 -inf 27 10 30 27 12 30 27 14 30 27 16 30 27 18 30 27 21 -inf 27 23 -inf 27 25 -inf 27 30 30 27 32 30 27 35 30 27 37 30 27 39 30 27 41 30 27 43 30 27 46 30 27 48 30 27 50 30 27 52 30 27 54 30 27 57 30 27 59 30 27 61 30 27 63 30 27 65 30 27 68 -inf 27 70 -inf 27 72 -inf 27 74 -inf 27 77 -inf 27 79 -inf 27 81 -inf 27 83 -inf 27 86 -inf 27 88 -inf 27 90 -inf 27 92 -inf 30 1 30 30 3 30 30 5 30 30 7 30 30 10 30 30 12 30 30 14 30 30 16 30 30 18 30 30 21 30 30 23 30 30 25 30 30 27 30 30 32 -inf 30 35 -inf 30 37 -inf 30 39 -inf 30 41 -inf 30 43 -inf 30 46 -inf 30 48 -inf 30 50 -inf 30 52 -inf 30 54 -inf 30 57 -inf 30 59 -inf 30 61 -inf 30 63 -inf 30 65 -inf 30 68 30 30 70 30 30 72 30 30 74 30 30 77 30 30 79 30 30 81 30 30 83 30 30 86 30 30 88 30 30 90 30 30 92 30 32 1 30 32 3 30 32 5 30 32 7 30 32 10 30 32 12 30 32 14 30 32 16 30 32 18 30 32 21 30 32 23 30 32 25 30 32 27 30 32 30 -inf 32 35 -inf 32 37 -inf 32 39 -inf 32 41 -inf 32 43 -inf 32 46 -inf 32 48 -inf 32 50 -inf 32 52 -inf 32 54 -inf 32 57 -inf 32 59 -inf 32 61 -inf 32 63 -inf 32 65 -inf 32 68 30 32 70 30 32 72 30 32 74 30 32 77 30 32 79 30 32 81 30 32 83 30 32 86 30 32 88 30 32 90 30 32 92 30 35 1 30 35 3 30 35 5 30 35 7 30 35 10 30 35 12 30 35 14 30 35 16 30 35 18 30 35 21 30 35 23 30 35 25 30 35 27 30 35 30 -inf 35 32 -inf 35 37 -inf 35 39 -inf 35 41 -inf 35 43 -inf 35 46 -inf 35 48 -inf 35 50 -inf 35 52 -inf 35 54 -inf 35 57 -inf 35 59 -inf 35 61 -inf 35 63 -inf 35 65 -inf 35 68 30 35 70 30 35 72 30 35 74 30 35 77 30 35 79 30 35 81 30 35 83 30 35 86 30 35 88 30 35 90 30 35 92 30 37 1 30 37 3 30 37 5 30 37 7 30 37 10 30 37 12 30 37 14 30 37 16 30 37 18 30 37 21 30 37 23 30 37 25 30 37 27 30 37 30 -inf 37 32 -inf 37 35 -inf 37 39 -inf 37 41 -inf 37 43 -inf 37 46 -inf 37 48 -inf 37 50 -inf 37 52 -inf 37 54 -inf 37 57 -inf 37 59 -inf 37 61 -inf 37 63 -inf 37 65 -inf 37 68 30 37 70 30 37 72 30 37 74 30 37 77 30 37 79 30 37 81 30 37 83 30 37 86 30 37 88 30 37 90 30 37 92 30 39 1 30 39 3 30 39 5 30 39 7 30 39 10 30 39 12 30 39 14 30 39 16 30 39 18 30 39 21 30 39 23 30 39 25 30 39 27 30 39 30 -inf 39 32 -inf 39 35 -inf 39 37 -inf 39 41 -inf 39 43 -inf 39 46 -inf 39 48 -inf 39 50 -inf 39 52 -inf 39 54 -inf 39 57 -inf 39 59 -inf 39 61 -inf 39 63 -inf 39 65 -inf 39 68 30 39 70 30 39 72 30 39 74 30 39 77 30 39 79 30 39 81 30 39 83 30 39 86 30 39 88 30 39 90 30 39 92 30 41 1 30 41 3 30 41 5 30 41 7 30 41 10 30 41 12 30 41 14 30 41 16 30 41 18 30 41 21 30 41 23 30 41 25 30 41 27 30 41 30 -inf 41 32 -inf 41 35 -inf 41 37 -inf 41 39 -inf 41 43 -inf 41 46 -inf 41 48 -inf 41 50 -inf 41 52 -inf 41 54 -inf 41 57 -inf 41 59 -inf 41 61 -inf 41 63 -inf 41 65 -inf 41 68 30 41 70 30 41 72 30 41 74 30 41 77 30 41 79 30 41 81 30 41 83 30 41 86 30 41 88 30 41 90 30 41 92 30 43 1 30 43 3 30 43 5 30 43 7 30 43 10 30 43 12 30 43 14 30 43 16 30 43 18 30 43 21 30 43 23 30 43 25 30 43 27 30 43 30 -inf 43 32 -inf 43 35 -inf 43 37 -inf 43 39 -inf 43 41 -inf 43 46 -inf 43 48 -inf 43 50 -inf 43 52 -inf 43 54 -inf 43 57 -inf 43 59 -inf 43 61 -inf 43 63 -inf 43 65 -inf 43 68 30 43 70 30 43 72 30 43 74 30 43 77 30 43 79 30 43 81 30 43 83 30 43 86 30 43 88 30 43 90 30 43 92 30 46 1 30 46 3 30 46 5 30 46 7 30 46 10 30 46 12 30 46 14 30 46 16 30 46 18 30 46 21 30 46 23 30 46 25 30 46 27 30 46 30 -inf 46 32 -inf 46 35 -inf 46 37 -inf 46 39 -inf 46 41 -inf 46 43 -inf 46 48 -inf 46 50 -inf 46 52 -inf 46 54 -inf 46 57 -inf 46 59 -inf 46 61 -inf 46 63 -inf 46 65 -inf 46 68 30 46 70 30 46 72 30 46 74 30 46 77 30 46 79 30 46 81 30 46 83 30 46 86 30 46 88 30 46 90 30 46 92 30 48 1 30 48 3 30 48 5 30 48 7 30 48 10 30 48 12 30 48 14 30 48 16 30 48 18 30 48 21 30 48 23 30 48 25 30 48 27 30 48 30 -inf 48 32 -inf 48 35 -inf 48 37 -inf 48 39 -inf 48 41 -inf 48 43 -inf 48 46 -inf 48 50 -inf 48 52 -inf 48 54 -inf 48 57 -inf 48 59 -inf 48 61 -inf 48 63 -inf 48 65 -inf 48 68 30 48 70 30 48 72 30 48 74 30 48 77 30 48 79 30 48 81 30 48 83 30 48 86 30 48 88 30 48 90 30 48 92 30 50 1 30 50 3 30 50 5 30 50 7 30 50 10 30 50 12 30 50 14 30 50 16 30 50 18 30 50 21 30 50 23 30 50 25 30 50 27 30 50 30 -inf 50 32 -inf 50 35 -inf 50 37 -inf 50 39 -inf 50 41 -inf 50 43 -inf 50 46 -inf 50 48 -inf 50 52 -inf 50 54 -inf 50 57 -inf 50 59 -inf 50 61 -inf 50 63 -inf 50 65 -inf 50 68 30 50 70 30 50 72 30 50 74 30 50 77 30 50 79 30 50 81 30 50 83 30 50 86 30 50 88 30 50 90 30 50 92 30 52 1 30 52 3 30 52 5 30 52 7 30 52 10 30 52 12 30 52 14 30 52 16 30 52 18 30 52 21 30 52 23 30 52 25 30 52 27 30 52 30 -inf 52 32 -inf 52 35 -inf 52 37 -inf 52 39 -inf 52 41 -inf 52 43 -inf 52 46 -inf 52 48 -inf 52 50 -inf 52 54 -inf 52 57 -inf 52 59 -inf 52 61 -inf 52 63 -inf 52 65 -inf 52 68 30 52 70 30 52 72 30 52 74 30 52 77 30 52 79 30 52 81 30 52 83 30 52 86 30 52 88 30 52 90 30 52 92 30 54 1 30 54 3 30 54 5 30 54 7 30 54 10 30 54 12 30 54 14 30 54 16 30 54 18 30 54 21 30 54 23 30 54 25 30 54 27 30 54 30 -inf 54 32 -inf 54 35 -inf 54 37 -inf 54 39 -inf 54 41 -inf 54 43 -inf 54 46 -inf 54 48 -inf 54 50 -inf 54 52 -inf 54 57 -inf 54 59 -inf 54 61 -inf 54 63 -inf 54 65 -inf 54 68 30 54 70 30 54 72 30 54 74 30 54 77 30 54 79 30 54 81 30 54 83 30 54 86 30 54 88 30 54 90 30 54 92 30 57 1 30 57 3 30 57 5 30 57 7 30 57 10 30 57 12 30 57 14 30 57 16 30 57 18 30 57 21 30 57 23 30 57 25 30 57 27 30 57 30 -inf 57 32 -inf 57 35 -inf 57 37 -inf 57 39 -inf 57 41 -inf 57 43 -inf 57 46 -inf 57 48 -inf 57 50 -inf 57 52 -inf 57 54 -inf 57 59 -inf 57 61 -inf 57 63 -inf 57 65 -inf 57 68 30 57 70 30 57 72 30 57 74 30 57 77 30 57 79 30 57 81 30 57 83 30 57 86 30 57 88 30 57 90 30 57 92 30 59 1 30 59 3 30 59 5 30 59 7 30 59 10 30 59 12 30 59 14 30 59 16 30 59 18 30 59 21 30 59 23 30 59 25 30 59 27 30 59 30 -inf 59 32 -inf 59 35 -inf 59 37 -inf 59 39 -inf 59 41 -inf 59 43 -inf 59 46 -inf 59 48 -inf 59 50 -inf 59 52 -inf 59 54 -inf 59 57 -inf 59 61 -inf 59 63 -inf 59 65 -inf 59 68 30 59 70 30 59 72 30 59 74 30 59 77 30 59 79 30 59 81 30 59 83 30 59 86 30 59 88 30 59 90 30 59 92 30 61 1 30 61 3 30 61 5 30 61 7 30 61 10 30 61 12 30 61 14 30 61 16 30 61 18 30 61 21 30 61 23 30 61 25 30 61 27 30 61 30 -inf 61 32 -inf 61 35 -inf 61 37 -inf 61 39 -inf 61 41 -inf 61 43 -inf 61 46 -inf 61 48 -inf 61 50 -inf 61 52 -inf 61 54 -inf 61 57 -inf 61 59 -inf 61 63 -inf 61 65 -inf 61 68 30 61 70 30 61 72 30 61 74 30 61 77 30 61 79 30 61 81 30 61 83 30 61 86 30 61 88 30 61 90 30 61 92 30 63 1 30 63 3 30 63 5 30 63 7 30 63 10 30 63 12 30 63 14 30 63 16 30 63 18 30 63 21 30 63 23 30 63 25 30 63 27 30 63 30 -inf 63 32 -inf 63 35 -inf 63 37 -inf 63 39 -inf 63 41 -inf 63 43 -inf 63 46 -inf 63 48 -inf 63 50 -inf 63 52 -inf 63 54 -inf 63 57 -inf 63 59 -inf 63 61 -inf 63 65 -inf 63 68 30 63 70 30 63 72 30 63 74 30 63 77 30 63 79 30 63 81 30 63 83 30 63 86 30 63 88 30 63 90 30 63 92 30 65 1 30 65 3 30 65 5 30 65 7 30 65 10 30 65 12 30 65 14 30 65 16 30 65 18 30 65 21 30 65 23 30 65 25 30 65 27 30 65 30 -inf 65 32 -inf 65 35 -inf 65 37 -inf 65 39 -inf 65 41 -inf 65 43 -inf 65 46 -inf 65 48 -inf 65 50 -inf 65 52 -inf 65 54 -inf 65 57 -inf 65 59 -inf 65 61 -inf 65 63 -inf 65 68 30 65 70 30 65 72 30 65 74 30 65 77 30 65 79 30 65 81 30 65 83 30 65 86 30 65 88 30 65 90 30 65 92 30 68 1 -inf 68 3 -inf 68 5 -inf 68 7 -inf 68 10 30 68 12 30 68 14 30 68 16 30 68 18 30 68 21 -inf 68 23 -inf 68 25 -inf 68 27 -inf 68 30 30 68 32 30 68 35 30 68 37 30 68 39 30 68 41 30 68 43 30 68 46 30 68 48 30 68 50 30 68 52 30 68 54 30 68 57 30 68 59 30 68 61 30 68 63 30 68 65 30 68 70 -inf 68 72 -inf 68 74 -inf 68 77 -inf 68 79 -inf 68 81 -inf 68 83 -inf 68 86 -inf 68 88 -inf 68 90 -inf 68 92 -inf 70 1 -inf 70 3 -inf 70 5 -inf 70 7 -inf 70 10 30 70 12 30 70 14 30 70 16 30 70 18 30 70 21 -inf 70 23 -inf 70 25 -inf 70 27 -inf 70 30 30 70 32 30 70 35 30 70 37 30 70 39 30 70 41 30 70 43 30 70 46 30 70 48 30 70 50 30 70 52 30 70 54 30 70 57 30 70 59 30 70 61 30 70 63 30 70 65 30 70 68 -inf 70 72 -inf 70 74 -inf 70 77 -inf 70 79 -inf 70 81 -inf 70 83 -inf 70 86 -inf 70 88 -inf 70 90 -inf 70 92 -inf 72 1 -inf 72 3 -inf 72 5 -inf 72 7 -inf 72 10 30 72 12 30 72 14 30 72 16 30 72 18 30 72 21 -inf 72 23 -inf 72 25 -inf 72 27 -inf 72 30 30 72 32 30 72 35 30 72 37 30 72 39 30 72 41 30 72 43 30 72 46 30 72 48 30 72 50 30 72 52 30 72 54 30 72 57 30 72 59 30 72 61 30 72 63 30 72 65 30 72 68 -inf 72 70 -inf 72 74 -inf 72 77 -inf 72 79 -inf 72 81 -inf 72 83 -inf 72 86 -inf 72 88 -inf 72 90 -inf 72 92 -inf 74 1 -inf 74 3 -inf 74 5 -inf 74 7 -inf 74 10 30 74 12 30 74 14 30 74 16 30 74 18 30 74 21 -inf 74 23 -inf 74 25 -inf 74 27 -inf 74 30 30 74 32 30 74 35 30 74 37 30 74 39 30 74 41 30 74 43 30 74 46 30 74 48 30 74 50 30 74 52 30 74 54 30 74 57 30 74 59 30 74 61 30 74 63 30 74 65 30 74 68 -inf 74 70 -inf 74 72 -inf 74 77 -inf 74 79 -inf 74 81 -inf 74 83 -inf 74 86 -inf 74 88 -inf 74 90 -inf 74 92 -inf 77 1 -inf 77 3 -inf 77 5 -inf 77 7 -inf 77 10 30 77 12 30 77 14 30 77 16 30 77 18 30 77 21 -inf 77 23 -inf 77 25 -inf 77 27 -inf 77 30 30 77 32 30 77 35 30 77 37 30 77 39 30 77 41 30 77 43 30 77 46 30 77 48 30 77 50 30 77 52 30 77 54 30 77 57 30 77 59 30 77 61 30 77 63 30 77 65 30 77 68 -inf 77 70 -inf 77 72 -inf 77 74 -inf 77 79 -inf 77 81 -inf 77 83 -inf 77 86 -inf 77 88 -inf 77 90 -inf 77 92 -inf 79 1 -inf 79 3 -inf 79 5 -inf 79 7 -inf 79 10 30 79 12 30 79 14 30 79 16 30 79 18 30 79 21 -inf 79 23 -inf 79 25 -inf 79 27 -inf 79 30 30 79 32 30 79 35 30 79 37 30 79 39 30 79 41 30 79 43 30 79 46 30 79 48 30 79 50 30 79 52 30 79 54 30 79 57 30 79 59 30 79 61 30 79 63 30 79 65 30 79 68 -inf 79 70 -inf 79 72 -inf 79 74 -inf 79 77 -inf 79 81 -inf 79 83 -inf 79 86 -inf 79 88 -inf 79 90 -inf 79 92 -inf 81 1 -inf 81 3 -inf 81 5 -inf 81 7 -inf 81 10 30 81 12 30 81 14 30 81 16 30 81 18 30 81 21 -inf 81 23 -inf 81 25 -inf 81 27 -inf 81 30 30 81 32 30 81 35 30 81 37 30 81 39 30 81 41 30 81 43 30 81 46 30 81 48 30 81 50 30 81 52 30 81 54 30 81 57 30 81 59 30 81 61 30 81 63 30 81 65 30 81 68 -inf 81 70 -inf 81 72 -inf 81 74 -inf 81 77 -inf 81 79 -inf 81 83 -inf 81 86 -inf 81 88 -inf 81 90 -inf 81 92 -inf 83 1 -inf 83 3 -inf 83 5 -inf 83 7 -inf 83 10 30 83 12 30 83 14 30 83 16 30 83 18 30 83 21 -inf 83 23 -inf 83 25 -inf 83 27 -inf 83 30 30 83 32 30 83 35 30 83 37 30 83 39 30 83 41 30 83 43 30 83 46 30 83 48 30 83 50 30 83 52 30 83 54 30 83 57 30 83 59 30 83 61 30 83 63 30 83 65 30 83 68 -inf 83 70 -inf 83 72 -inf 83 74 -inf 83 77 -inf 83 79 -inf 83 81 -inf 83 86 -inf 83 88 -inf 83 90 -inf 83 92 -inf 86 1 -inf 86 3 -inf 86 5 -inf 86 7 -inf 86 10 30 86 12 30 86 14 30 86 16 30 86 18 30 86 21 -inf 86 23 -inf 86 25 -inf 86 27 -inf 86 30 30 86 32 30 86 35 30 86 37 30 86 39 30 86 41 30 86 43 30 86 46 30 86 48 30 86 50 30 86 52 30 86 54 30 86 57 30 86 59 30 86 61 30 86 63 30 86 65 30 86 68 -inf 86 70 -inf 86 72 -inf 86 74 -inf 86 77 -inf 86 79 -inf 86 81 -inf 86 83 -inf 86 88 -inf 86 90 -inf 86 92 -inf 88 1 -inf 88 3 -inf 88 5 -inf 88 7 -inf 88 10 30 88 12 30 88 14 30 88 16 30 88 18 30 88 21 -inf 88 23 -inf 88 25 -inf 88 27 -inf 88 30 30 88 32 30 88 35 30 88 37 30 88 39 30 88 41 30 88 43 30 88 46 30 88 48 30 88 50 30 88 52 30 88 54 30 88 57 30 88 59 30 88 61 30 88 63 30 88 65 30 88 68 -inf 88 70 -inf 88 72 -inf 88 74 -inf 88 77 -inf 88 79 -inf 88 81 -inf 88 83 -inf 88 86 -inf 88 90 -inf 88 92 -inf 90 1 -inf 90 3 -inf 90 5 -inf 90 7 -inf 90 10 30 90 12 30 90 14 30 90 16 30 90 18 30 90 21 -inf 90 23 -inf 90 25 -inf 90 27 -inf 90 30 30 90 32 30 90 35 30 90 37 30 90 39 30 90 41 30 90 43 30 90 46 30 90 48 30 90 50 30 90 52 30 90 54 30 90 57 30 90 59 30 90 61 30 90 63 30 90 65 30 90 68 -inf 90 70 -inf 90 72 -inf 90 74 -inf 90 77 -inf 90 79 -inf 90 81 -inf 90 83 -inf 90 86 -inf 90 88 -inf 90 92 -inf 92 1 -inf 92 3 -inf 92 5 -inf 92 7 -inf 92 10 30 92 12 30 92 14 30 92 16 30 92 18 30 92 21 -inf 92 23 -inf 92 25 -inf 92 27 -inf 92 30 30 92 32 30 92 35 30 92 37 30 92 39 30 92 41 30 92 43 30 92 46 30 92 48 30 92 50 30 92 52 30 92 54 30 92 57 30 92 59 30 92 61 30 92 63 30 92 65 30 92 68 -inf 92 70 -inf 92 72 -inf 92 74 -inf 92 77 -inf 92 79 -inf 92 81 -inf 92 83 -inf 92 86 -inf 92 88 -inf 92 90 -inf
Raw
MILP.py
# %% [markdown]
# ## Prototyping the MLIP way for GFJSP
#
# %%
from itertools import product
from collections import OrderedDict
from ortools.linear_solver import pywraplp
from ortools.sat.python import cp_model
import numpy as np
from utils import parse_data, get_m_value
# %%
# n_opt, n_mach, operation_data, machine_data = parse_data("gfjsp_10_10_1.txt")
n_opt, n_mach, operation_data, machine_data = parse_data("gfjsp_10_5_1.txt")
# %%
# %% [markdown]
# ## Solve the problem with MILP
#
# %%
from ortools.linear_solver import pywraplp
# maximum holding time of operation i in machine m
# =20 for the furnaces, 0 for Cutting, Pressing, and Forging)
# (0: Cutting; 1: Pressing; 2: Forging; 3: Furnace)
operation_data["0"]["h"] = 0
operation_data["1"]["h"] = 0
operation_data["2"]["h"] = 0
operation_data["3"]["h"] = 20
# declare the MIP solver using the Gurobi backend
solver = pywraplp.Solver(
"SolveIntegerProblem", pywraplp.Solver.GUROBI_MIXED_INTEGER_PROGRAMMING
)
# solver = pywraplp.Solver.CreateSolver("SCIP")
# infinity = 1.0e7
# infinity = np.inf
infinity = solver.infinity()
# minimum lag between the starting time of operation i and the ending time of operation j
para_lmin = np.full((n_opt, n_opt), dtype=object, fill_value=-infinity)
# maximum lag between the starting time of operation i and the ending time of operation j
para_lmax = np.full((n_opt, n_opt), dtype=object, fill_value=infinity)
# processing time of operation i in machine m
# para_p = np.full((n_opt, n_mach), dtype=object, fill_value=infinity)
para_p = np.full((n_mach, n_opt), dtype=object, fill_value=infinity)
# the shape of h in the original file is (n_machine) while the shape of para_h in the
# paper is (n_opt, n_mach)
# maximum holding time of operation i in machine m
para_h = np.empty((n_opt, n_mach), dtype=object)
# para_h = np.empty(n_mach, dtype=object)
# mapping of operation i to machine m
# 20 for the furnaces, 0 for Cutting, Pressing, and Forging
# 0: Cutting; 1: Pressing; 2: Forging; 3: Furnace
holding_time_dict = {
"0": 0,
"1": 0,
"2": 0,
"3": 20,
}
# weight of operation i in machine m
# para_w = np.empty((n_opt, n_mach), dtype=object)
para_w = np.full((n_mach, n_opt), dtype=object, fill_value=infinity)
# input/output delay time between two consecutive operations in mahcine m
para_delta = np.empty((n_mach), dtype=object)
# setup time of machine m when processing operation i before j
# para_a = np.full((n_opt, n_opt, n_mach), dtype=object, fill_value=infinity)
para_a = np.full((n_mach, n_opt, n_opt), dtype=object, fill_value=infinity)
# capacity of machine
para_mach_capacity = np.empty((n_mach), dtype=object)
for m in range(n_mach):
# capacity of machine is a set of constant numbers
para_mach_capacity[m] = machine_data[str(m)]["c"]
# input/output delay time between two consecutive operations in mahcine m
# delta(m): loading and unloading time of machine m (=1 for all machines)
para_delta[m] = 1
# set up time of machine m when processing operation i before j
# a(i,j,m): setup time of machine m when processing operation i before j (aijm = -inf if there
# is no setups)
for idx_setup, setup_data in enumerate(machine_data[str(m)]["setup_data"][0]):
para_a[m, int(setup_data[0]), int(setup_data[1])] = setup_data[2]
# maximum holding time of operation i in machine m
para_h[:, m] = holding_time_dict[str(machine_data[str(m)]["t"])]
# lag time
for i in range(n_opt):
for idx_lag, lag_data in enumerate(operation_data[str(i)]["lag"]):
# minimum lag between the starting time of operation i and the ending time of operation j
para_lmin[i, int(lag_data[0])] = lag_data[1]
# maximum lag between the starting time of operation i and the ending time of operation j
para_lmax[i, int(lag_data[0])] = lag_data[2]
for idx_pw, pw_data in enumerate(operation_data[str(i)]["pw"]):
# operation_data[str(1)]["pw"]
# # the shape of para_p in the original file is the transpose of the shape of para_p
# para_p[i, int(pw_data[0])] = pw_data[1]
# # the shape of para_w in the original file is the transpose of the shape of para_w
# para_w[i, int(pw_data[0])] = pw_data[2]
# the shape of para_p in the original file is the transpose of the shape of para_p
para_p[int(pw_data[0]), i] = pw_data[1]
# the shape of para_w in the original file is the transpose of the shape of para_w
para_w[int(pw_data[0]), i] = pw_data[2]
# reformat the shape of para_p and para_w
para_p = para_p.T
para_w = para_w.T
# reshape the shape of para_a
para_a = np.einsum("mij->ijm", para_a)
# the big M value
big_m = get_m_value(para_p=para_p, para_h=para_h, para_lmin=para_lmin, para_a=para_a)
# big_m = 1.0e4
# replace infinities with infinity from the solver
para_lmin[para_lmin == -np.inf] = -infinity
para_lmin[para_lmin == np.inf] = infinity
para_lmax[para_lmax == np.inf] = infinity
para_lmax[para_lmax == -np.inf] = -infinity
para_p[para_p == np.inf] = infinity
para_p[para_p == -np.inf] = -infinity
para_w[para_w == np.inf] = infinity
para_w[para_w == -np.inf] = -infinity
para_a[para_a == np.inf] = infinity
para_a[para_a == -np.inf] = -infinity
# =================================================
# # only take part of the data for debugging purpose
# n_opt = 7
# para_a = para_a[:n_opt, :n_opt, :]
# para_lmin = para_lmin[:n_opt, :n_opt]
# para_lmax = para_lmax[:n_opt, :n_opt]
# para_p = para_p[:n_opt, :]
# para_w = para_w[:n_opt, :]
# para_h = para_h[:n_opt, :]
# =================================================
# %%
n_opt_selected = 8
n_opt = n_opt_selected
para_lmin = para_lmin[:n_opt_selected, :n_opt_selected]
para_lmax = para_lmax[:n_opt_selected, :n_opt_selected]
para_p = para_p[:n_opt_selected, :]
para_h = para_h[:n_opt_selected, :]
para_w = para_w[:n_opt_selected, :]
para_a = para_a[:n_opt_selected, :n_opt_selected, :]
# %%
# %%
# create variables
ort_infinity = solver.infinity()
# if operation i is processed by machine m
var_y = np.empty((n_opt, n_mach), dtype=object)
for i, m in product(range(n_opt), range(n_mach)):
var_y[i, m] = solver.BoolVar(f"y_{i}_{m}")
# if operation i is processed before operation j
var_x = np.empty((n_opt, n_opt), dtype=object)
for i, j in product(range(n_opt), range(n_opt)):
var_x[i, j] = solver.BoolVar(f"x_{i}_{j}")
# if operation i is processed before operation j on machine m
var_z = np.empty((n_opt, n_opt, n_mach), dtype=object)
for i, j, m in product(range(n_opt), range(n_opt), range(n_mach)):
var_z[i, j, m] = solver.BoolVar(f"z_{i}_{j}_{m}")
# starting time of operation i
var_s = np.empty((n_opt), dtype=object)
for i in range(n_opt):
var_s[i] = solver.NumVar(0, ort_infinity, f"s_{i}")
# completion time of operation i
var_c = np.empty((n_opt), dtype=object)
for i in range(n_opt):
var_c[i] = solver.NumVar(0, ort_infinity, f"c_{i}")
# make span
var_c_max = solver.NumVar(0, ort_infinity, "C_max")
# %%
# create objective
solver.Minimize(var_c_max)
for i in range(n_opt):
# eq. (3)
# !!!!!!!!! expr = [para_p[i, m] * var_y[i, m] for i in range(n_mach)]
expr = [para_p[i, m] * var_y[i, m] for m in range(n_mach)]
solver.Add(var_c[i] >= var_s[i] + sum(expr))
# eq. (4)
# !!!!!!!!!! expr = [(para_p[i, m] + para_h[i, m]) * var_y[i, m] for i in range(n_mach)]
expr = [(para_p[i, m] + para_h[i, m]) * var_y[i, m] for m in range(n_mach)]
solver.Add(var_c[i] <= var_s[i] + sum(expr))
# eq. (5)
# !!!!!!!!!!!!!!
# for m in range(n_mach):
# # sum of y_im = 1
# solver.Add(sum([var_y[i, m] for i in range(n_opt)]) == 1)
for i in range(n_opt):
# sum of y_im = 1
solver.Add(sum([var_y[i, m] for m in range(n_mach)]) == 1)
for i, j in product(range(n_opt), range(n_opt)):
# eq. (6)
# minimum lag between the starting time of operation i and the ending time of operation j
solver.Add(var_s[j] >= var_c[i] + para_lmin[i, j])
# eq. (7)
# maximum lag between the starting time of operation i and the ending time of operation j
solver.Add(var_s[j] <= var_c[i] + para_lmax[i, j])
# ==================================================================
# comment out the following constraints for debugging purpose
for i, j in product(range(n_opt), range(n_opt)):
# eq. (6)
# minimum lag between the starting time of operation i and the ending time of operation j
solver.Add(var_s[j] >= var_c[i] + para_lmin[i, j])
# eq. (7)
# maximum lag between the starting time of operation i and the ending time of operation j
solver.Add(var_s[j] <= var_c[i] + para_lmax[i, j])
for i, j, m in product(range(n_opt), range(n_opt), range(n_mach)):
if i < j:
# eq. (8)
# setup time of machine m when processing operation i before j
solver.Add(
var_s[j]
>= var_c[i]
+ para_a[i, j, m]
- big_m * (3 - var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (9)
# setup time of machine m when processing operation i before j
solver.Add(
var_s[i]
>= var_c[i]
+ para_a[i, j, m]
- big_m * (2 + var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (10) and (11)
for i, m in product(range(n_opt), range(n_mach)):
if i < j:
# eq. (10)
solver.Add(
var_s[j]
>= var_s[i]
+ para_delta[m]
- big_m * (3 - var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (11)
solver.Add(
var_s[i]
>= var_s[j]
+ para_delta[m]
- big_m * (2 + var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (12) and (13)
for i, m in product(range(n_opt), range(n_mach)):
if i < j:
# eq. (12)
solver.Add(
var_c[j]
>= var_c[i]
+ para_delta[m]
- big_m * (3 - var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (13)
solver.Add(
var_c[i]
>= var_c[j]
+ para_delta[m]
- big_m * (2 + var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (14) and (15)
for i, j, m in product(range(n_opt), range(n_opt), range(n_mach)):
if i < j:
# eq. (14)
solver.Add(
var_s[j]
>= var_c[i]
- big_m * (3 + var_z[i, j, m] - var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (15)
solver.Add(
var_s[i]
>= var_c[j]
- big_m * (2 + var_z[i, j, m] + var_x[i, j] - var_y[i, m] - var_y[j, m])
)
# eq. (16)
for i in range(n_opt):
for j in range(n_opt):
expr = []
for m in range(n_mach):
if i != j:
# solver.Add(var_w[j, m] * var_z[i, j, m] >= var_w[i, m])
expr.append(para_w[j, m] * var_z[i, j, m])
solver.Add(
solver.Sum(expr) <= (para_mach_capacity[m] - para_w[i, m]) * var_y[i, m]
)
# ==================================================================
# %%
# %%
# solve the problem
# solver.set_time_limit(600 * 1000)
solver.EnableOutput()
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print(f"opt_obj = {solver.Objective().Value():.4f}")
# %%
print(status)
# %%
# %%
solver.Objective().Value()
# %%
var_c_max.solution_value()
# %%
Raw
utils.py
from collections import OrderedDict
import numpy as np
def get_m_value(para_p, para_h, para_lmin, para_a):
"""Get the big number m using equation (17) - (20).
Parameters
----------
para_p: numpy.ndarray
processing time of operation i in machine m (pim =+∞ if machine m cannot process operation
i). shape: (number of operations, number of machines).
para_h: numpy.ndarray
maximum holding time of operation i in machine m. shape: (number of operations, number of
machines).
para_lmin: numpy.ndarray
minumum lag between the starting time of operation i and the ending time of operation j.
shape: (number of operations, number of operations).
para_a: numpy.ndarray
setup time of machine m when processing operation i before j (aijm = -inf if there is no
setups). shape: (number of operations, number of operations, number of machines).
Returns
-------
big_m: float
Value for big M.
Notes
-----
The big M value is calculated using equation (17) - (20) in the paper. But we have to adapt the
equations only taking non-infinite values into account.
"""
selected_idx = np.argwhere(para_p != np.inf)
# eq. (17)
p_i = para_p[selected_idx] + para_h[selected_idx]
p_i = np.max(p_i[p_i != np.inf])
# eq. (18)
l_i = np.max(para_lmin, axis=1)
# setup time of machine m when processing operation i before j (aijm = -inf if there is no
# setups).
# eq. (19)
# TODO: check if this is correct
para_a = np.einsum("mij->ijm", para_a)
selected_a = para_a[selected_idx, :]
a_i = selected_a[selected_a != np.inf]
# eq. (20) adapted
big_m = np.sum(p_i) + np.max([l_i.max(), a_i.max()])
return big_m
def parse_data(input_fname):
section_breaker = False
operation_data = OrderedDict()
machine_data = OrderedDict()
machine_counter = 0
with open(input_fname, "r") as f:
# loop over the lines in the file
for idx, line in enumerate(f):
# # due date of operations
d = []
# starting time of time window of operation i
a = []
# ending time of time window of operation i
b = []
# number of machines that can process operation i
nm = []
# processing time of operations and weight of operation i
pw_data = []
# no(i): number of operation that must be process after operation i
num_successor = []
lag_data = []
# machine data related
# capacity of machine m
c = []
# type of machine m (0: Cutting; 1: Pressing; 2: Forging; 3: Furnace)
t = []
# nsu(m): number of setups (different than +inf) on machine m
nsu = []
# [op_i op_j SetUp(0,op_i, op_j)]xnsu(0)
# where there are nsu(0) number of setups on machine 0
setup_data = []
line = line.strip()
# check if line is empty
if not line:
section_breaker = True
continue
if section_breaker:
line_data = np.array(line.split())
line_data[line_data == "inf"] = np.inf
line_data[line_data == "-inf"] = -np.inf
line_data = line_data.astype(float).tolist()
# parse machine data
# C(m): capacity of machine m
c.append(int(line_data[0]))
# t(m): type of machine m (0: Cutting; 1: Pressing; 2: Forging; 3: Furnace)
t.append(int(line_data[1]))
# nsu(m): number of setups (different than +inf) on machine m
nsu.append(int(line_data[2]))
# nsu(0)
# [op_i op_j SetUp(0,op_i, op_j)]xnsu(0)
tmp = line_data[3:]
# reformat the list into a set of tuples where each tuple contains 3 values
setup_data.append(tuple(tmp[i : i + 3] for i in range(0, len(tmp), 3)))
machine_data[str(machine_counter)] = {
"c": int(line_data[0]),
"t": int(line_data[1]),
"nsu": int(line_data[2]),
"setup_data": setup_data,
}
machine_counter += 1
else:
# parse operation data
if idx == 0:
# n_opt: number of operations
# n_mach: number of machines
n_opt, n_mach = map(int, line.split())
else:
# parse operation data
line_data = np.array(line.split())
line_data[line_data == "inf"] = np.inf
line_data[line_data == "-inf"] = -np.inf
line_data = line_data.astype(float).tolist()
# d(i): due date of operation i where i is the operation index
d.append(line_data[0])
# a(i): starting time of time window of operation i
a.append(line_data[1])
# b(i): ending time of time window of operation i
b.append(line_data[2])
# nm(i): number of machines that can process operation i
nm_i = int(line_data[3])
nm.append(nm_i)
# p(i,m): processing time of operation i in machine m
# w(i): weight of operation i
for idx_pw in range(nm_i):
pw_data.append(
tuple(line_data[4 + idx_pw * 3 : 4 + idx_pw * 3 + 3])
)
# pw_end_idx = 4 + n_mach * 3
# pw_data.append(line_data[4:pw_end_idx])
# no(i): number of operation that must be process after operation i
num_successor_i = int(line_data[nm_i * 3 + 4])
num_successor.append(num_successor_i)
# [op_id lmin(0,op_id) lmax(0,op_id)]xno(0)
# where there are no(0) number of operations that must be process after operation 0
# there are 3 values in one tuple
for idx_oper in range(num_successor_i):
lag_data.append(
tuple(
line_data[
nm_i * 3
+ 5
+ idx_oper * 3 : nm_i * 3
+ 5
+ idx_oper * 3
+ 3
]
)
)
operation_data[str(idx - 1)] = {
"a": line_data[1],
"b": line_data[2],
"nm": int(line_data[3]),
# "pw": line_data[4 : 4 + nm_i * 3],
"pw": pw_data,
# "no": line_data[4 + nm_i * 3],
"no": num_successor,
# "lag": line_data[4 + nm_i * 3 + 1 : 4 + nm_i * 3 + 4],
"lag": lag_data,
}
return n_opt, n_mach, operation_data, machine_data
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment