Одна из проблем при игре на фортепьяно - выбор хорошей аппликатуры, то есть определение для каждого звука мелодии (клавиши инструмента) пальца руки, которым эту ноту лучше всего сыграть в данном месте мелодии.

Пронумеруем пальцы пианиста слева направо натуральными числами от 1 до P, клавиши инструмента также пронумеруем слева направо натуральными числами от 1 до K. Тогда запись звуков мелодии можно представить в виде последовательности N номеров клавиш, которые следует нажимать для ее исполнения, где N - длина мелодии.

Пусть для каждой пары пальцев с номерами i и j заданы целые числа a_ij и b_ij, такие, что если палец i нажимает клавишу X, то следующей клавишей пальцем j может быть нажата лишь клавиша из диапазона [X+a_ij, X+b_ij]. Этот набор чисел a_ij, b_ij, 1 ≤ i ≤ P , 1 ≤ j ≤ P, зависит от особенностей пианиста и его исполнительской техники. Заметим, что не каждая мелодия может быть сыграна конкретным пианистом при указанных выше ограничениях.

Назовем перекладыванием пальцев ситуацию, когда для двух последовательно исполняемых нот мелодии клавиша с большим номером нажимается пальцем с меньшим номером. Требуется написать программу, которая для заданной мелодии определяет аппликатуру с наименьшим количеством перекладываний пальцев.

В первой строке входного файла содержится число P - количество пальцев у пианиста (1 ≤ P ≤ 20). Во второй строке записано число K - количество клавиш у инструмента (1 ≤ K ≤ 10000). В третьей строке указаны целые числа a₁₁ b₁₁ a₁₂ b₁₂ ... a_1P b_1P a₂₁ b₂₁ a₂₂ b₂₂ ... a_2P b_2P ... a_P1 b_P1 a_P2 b_P2 ... a_PP b_PP, разделенные пробелами (-K ≤ a_ij ≤ b_ij ≤ K). В четвертой строке находится число N - длина мелодии (1 ≤ N ≤ 1000). Пятая строка содержит N чисел X₁ X₂ ... X_N - последовательность разделенных пробелами номеров клавиш для исполнения мелодии.

В первой строке выходного файла должно содержаться либо число L - количество перекладываний пальцев в оптимальной аппликатуре, либо число -1 при невозможности сыграть мелодию. Вторая строка при наличии решения должна содержать N чисел Y₁ ... Y_N - последовательность разделенных пробелами номеров пальцев при исполнении мелодии.

input.txt	output.txt
3 10 0 0 -2 -2 -5 1 2 3 8 10 0 1 2 10 -2 -2 -1 -1 9 4 5 7 7 7 6 8 7 5	3 2 3 1 1 3 3 1 3 2