Задача Z6. Быстрое перемножение матриц ≡

Условие

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

• алгоритм Штрассена;
• или модификацию Штрассена-Винограда.

Алгоритм должен корректно работать при любых размерностях n, в том числе если n не является степенью двойки. Рекомендуется продумать гибридную стратегию, при которой быстрый алгоритм используется там, где это выгодно, а на малых или неудачных размерах - обычный тройной цикл. Сторонние библиотеки запрещены. Статья про умножение матриц - https://github.com/Rmgs123/Matrix-Multiplication/blob/main/article.md

Формат входных данных

Вход задаёт две квадратные матрицы A и B одинакового размера. Первая строка содержит целое число n.
Затем идут n строк по n целых чисел - элементы матрицы A.
После них - n строк по n целых чисел - элементы матрицы B.

Формат выходных данных

Выведите n строк по n целых чисел — элементы матрицы C = A × B. Числа в строках можно разделять произвольным числом пробелов. Дополнительные пробелы в конце строк допускаются.

Ограничения

1 <= n <= 512

-9 <= a_ij, b_ij <= 9

Примеры тестов

2
1 2
3 4
5 6
7 8

19 22
43 50