n-Special Queens

Time Limit: 10 Seconds    Memory Limit: 32768 KB

‫در یک نوع شطرنج خاص یک مهرهٔ وزیر می‌تواند مهره‌هایی را که با آن در یک سطر یا یک ستون یا به‌صورت قطری یا به شکل L (مشابه روش تهدید اسب در شطرنج عادی) قرار گرفته‌اند (و مانعی بینشان نیست) تهدید کند.
‫در این سؤال می‌خواهیم تمامی حالات ممکن برای چیدن n وزیر در یک صفحهٔ شطرنج n×n خالی را به طوری که هیچ کدام دیگری را تهدید نکند بیابیم.

Input

‫ورودی برنامه شامل یک سطر است که در آن عدد صحیح نامنفی n قرار گرفته است.

Output

‫خروجی برنامه تمام حالات ممکن را برای یک صفحه با ابعاد n×n را نشان می‌دهد.
‫حالات مختلف باید براساس lexicographical order مرتب شوند، به این صورت که اگر برای هر صفحهٔ پر شده از n وزیر شمارهٔ ستون پر شده در هر سطر را به ترتیب پشت سر هم بنویسیم، به هر صفحه عددی اختصاص می‌یابد که ملاک مرتب سازی خواهد بود.
‫در هر سطر از چیدمان برای هر خانهٔ خالی یک نقطه (.) و برای هر خانه‌ای که رخ در آن قرار دارد # چاپ می‌شود. بین خانه‌ها نیز یک فاصله ( ) چاپ می‌شود. بعد از هر چیدمان باید یک سطر خالی چاپ شود.

Sample Input

10

Sample Output

. . # . . . . . . .
. . . . . # . . . .
. . . . . . . . # .
# . . . . . . . . .
. . . # . . . . . .
. . . . . . # . . .
. . . . . . . . . #
. # . . . . . . . .
. . . . # . . . . .
. . . . . . . # . .

. . . # . . . . . .
. . . . . . . # . .
# . . . . . . . . .
. . . . # . . . . .
. . . . . . . . # .
. # . . . . . . . .
. . . . . # . . . .
. . . . . . . . . #
. . # . . . . . . .
. . . . . . # . . .

. . . . . . # . . .
. . # . . . . . . .
. . . . . . . . . #
. . . . . # . . . .
. # . . . . . . . .
. . . . . . . . # .
. . . . # . . . . .
# . . . . . . . . .
. . . . . . . # . .
. . . # . . . . . .

. . . . . . . # . .
. . . . # . . . . .
. # . . . . . . . .
. . . . . . . . . #
. . . . . . # . . .
. . . # . . . . . .
# . . . . . . . . .
. . . . . . . . # .
. . . . . # . . . .
. . # . . . . . . .
Submit