Галерея современного искусства заказала художнику Малявичу очередной шедевр, с условным названием «Сложный квадрат». По условиям заказа, полотно должно:

1. быть квадратом, целиком состоящим из других $$$n$$$ квадратов;
2. иметь размер $$$k \times k$$$, причем размер может быть выбран художником произвольно, но так, чтобы $$$1 \leq k \leq n$$$;
3. стороны всех квадратов должны быть строго вертикальны или строго горизонтальны;
4. размеры сторон квадратов – целые числа;
5. два квадрата соприкасающихся сторонами (но не вершинами) должны быть разного цвета.

Помогите Малявичу создать шедевр – напишите программу, которая по заданному $$$n$$$ выберет подходящее $$$k$$$ и построит карту расположения цветных квадратов, не нарушающую приведенные условия, либо сообщит, что решения не существует.