Рисовая компания
Рисовая компания
Новый украинский фермер старый дед Василий имеет в своём распоряжении прямоугольный участок n на m. Разобъем его на единичные квадратики. В каждом из них растёт сорт риса (не удивляйтесь, рис является достаточно ценным и выгодным продуктом). Для простоты сорта риса пронумерованы числами от 1 до n * m.
Совсем недавно деду Василию удалось заключить сделку с компанией IPC (International Рис Corporation) на t дней. Согласно условий этой сделки каждый день фермер должен поставлять рис определённого сорта.
Пусть у деда Василия заказали рис сорта k. Тогда он действует по следующему принципу: на участке n на m он выбирает прямоугольный участок максимальной площади, на котором ростёт только рис сорта k. То есть дед Василий собирает рис определённого сорта только с прямоугольных участков.
Для компании ІРС важно знать, какое максимальное количество риса определённого сорта сможет поставлять дед Василий для каждого запроса. Известно, что с одного единичного квадрата дед Василий получает одну условную единицу товара, то есть из участка площадью s дед Василий получает s единиц риса. Также известно, что с определённой площади дед Василий может сколько угодно раз подряд собирать рис.
Входные данные
В первой строке задано два целых числа n и m (1 ≤ n, m ≤ 1000) - размеры участка деда Василия. В последующих n строках задано по m целых чисел в каждой, aij
– сорт риса, который растёт в j-ом квадратике і-ой строки, 1 ≤ aij
≤ n * m.
После этого задано число t (1 ≤ t ≤ 20) – количество дней, на протяжении которых дед Василий должен поставлять рис в компанию. В последующих t строках задано по одному целому числу k (1 ≤ k ≤ n * m) – сорт риса, который заказывает фирма.
Выходные данные
Выведите t чисел – для каждого запроса компании ІРС максимальное количество риса, которое сможет собрать дед Василий.
4 2 1 3 5 2 4 2 2 3 4 1 2 3 4
1 2 1 1