Авиакомпания Пингвин-Авиа, как и многие другие антарктические авиакомпании, испытывает финансовые трудности в период мирового экономического кризиса. Жители Антарктиды теперь экономят на полётах и чаще пользуются поездами или вообще предпочитают сидеть дома. Руководство авиакомпании надеется, что летом поток клиентов возрастёт за счёт желающих отдохнуть на приморских курортах Антарктиды. Чтобы дотянуть до лета, было решено оптимизировать схему авиарейсов, временно сократив часть рейсов и, возможно, введя несколько новых.

Директор Пингвин-Авиа считает, что после оптимизации схема полётов должна обладать следующими свойствами:

1. Рейсами Пингвин-Авиа можно добраться из любого аэропорта Антарктиды до любого другого. Возможно, для этого придётся сделать несколько пересадок.
2. Схема должна содержать минимальное число рейсов среди всех схем, отвечающих первому свойству.

Но в Антарктиде не всё так просто. За отмену существующего рейса с авиакомпании взимается разовая неустойка в размере d антарктических долларов. Кроме того, чтобы получить слоты под новый рейс, надо дать взятку крёстному отцу антарктической мафии по прозвищу Белый медведь в размере a антарктических долларов.

Помогите директору Пингвин-Авиа трансформировать существующее расписание полётов, потратив при этом наименьшую сумму денег, и вы получите за это проездной билет на все рейсы авиакомпании.

В первой строке записано целое число n — количество аэропортов в Антарктиде, 2 ≤ n ≤ 100. Во второй строке через пробел записаны целые числа d и a, 1 ≤ d, a ≤ 10⁶. В следующих n строках записана существующая схема полётов Пингвин-Авиа в виде матрицы размером n × n. В ячейке (i, j) матрицы стоит единица, если авиакомпания совершает рейс между аэропортами i и j. В противном случае в ячейке стоит нуль. Гарантируется, что матрица симметрична и на её диагонали стоят нули.

В первой строке выведите наименьшую сумму денег, которую придётся потратить для оптимизации существующей схемы полётов. В следующих n строках выведите план изменения схемы в виде матрицы размера n × n. Ячейка (i, j) матрицы содержит символ «d», если нужно отменить существующий рейс между аэропортами i и j. Если нужно ввести новый рейс между этими аэропортами, ячейка содержит символ «a». Все остальные ячейки матрицы содержат символ «0». Матрица должна быть симметричной. Если существует несколько оптимальных схем, выведите любую из них.