Большой Музей скоро открывает новую выставку, и в связи с этим принято решение сделать апгрейд системы безопасности. Вас назначили ответственным за установку камер видеонаблюдения.
Пространство, отведённое для выставки, представляет собой прямоугольник размера H × W, разделённый на отдельные зоны размера 1 × 1. В каждой зоне планируется разместить ровно один экспонат; ценность экспоната, расположенного в зоне с координатами (i; j), равна Pij. Вы заметили, что все экспонаты имеют различные ценности.
Руководство музея планирует разместить видеокамеры над каждым из экспонатов; для этой цели уже закупили (H·W) видеокамер, k-я из которых имеет надёжность Qk. Вы заметили, что надёжности всех камер также являются различными.
Разумеется, над более ценными экспонатами следует разместить более надёжные камеры. Более формально, над самым дорогим экспонатом должна быть самая надёжная камера, над вторым по ценности экспонатом — вторая по надёжности камера, и так далее.
Составьте план размещения камер, аналогичный плану размещения экспонатов.
Выходные данные
Выведите H строк, каждая из которых содержит W чисел — величины надёжности камер, размещаемых над каждым из экспонатов.