#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
#define clr(a) memset(a, 0, sizeof(a))

namespace nQueens
{

    int sn, mt[1010][1010], ps[1010], pm[1010], dpm[1010], stm[1010];
    char ans[2000010];
    bool gmp(int a, int b)
    {
        return dpm[a - 1] < dpm[b - 1];
    }
    void gpm(int n, int r = -1, int c = -1)
    {
        int i;
        for (i = 0; i < n; ++i)
            pm[i] = i + 1, dpm[i] = rand();
        sort(pm, pm + n, gmp);
        if (r >= 0)
        {
            for (i = 0; pm[i] != r + 1; ++i)
                ;
            swap(pm[i], pm[c]);
        }
    }
    inline bool v2ck(int a, int b, int c, int d) { return a == c || b == d || (abs(c - a) == abs(d - b)); };

    void makeans(int n)
    {
        int i, j, k, d, t;
        for (clr(ans), i = d = 0; i < n; ++i, ans[d++] = '\n')
            for (j = 0; j < n; ++j)
            {
                ans[d++] = mt[i][j] ? 'Q' : '.';
            }
    }

    int __cl(int r, int c, int dt, bool zt, bool lz, int n)
    {
        int i, j, k, d, t, rs = 0;
        bool fg = 0;
        if (lz)
            mt[r][c] = zt ? 0 : dt, ps[dt] = zt ? -1 : r;
        for (i = 1; i <= n; ++i)
            if (ps[i] >= 0 && i != dt && v2ck(r, c, ps[i], i - 1))
            {
                if (!stm[i] && !zt)
                    ++rs;
                if (stm[i] == 1 && zt)
                    --rs;
                if (lz && zt)
                    stm[i]--, stm[dt]--;
                if (lz && !zt)
                    stm[i]++, stm[dt]++;
                fg = 1;
            }
        if (fg)
        {
            rs += zt ? -1 : 1;
        }
        return rs;
    }

    string _cl(int n, int dq = -1, int dp = -1)
    {
        int i, j, k, d, t, q, o, h, zn, qn, dqn = 10, dn = 50 * n;
        clr(mt);
        for (sn = n, qn = 1; sn && qn < dqn; ++qn)
        {
            for (i = 1; i <= n; stm[i++] = 0)
                mt[max(0, ps[i])][i - 1] = 0;
            for (i = 1; i <= n; ps[i++] = -1)
                ;
            for (gpm(n, dq, dp), sn = 0, i = 1; i <= n; ++i)
            {
                t = pm[i - 1] - 1;
                sn += cl(t, i - 1, i, 0, 1, n), ps[i] = t;
            }
            for (zn = 1; sn && zn <= dn; ++zn)
            {
                for (gpm(n), i = 0; i < n; ++i)
                {
                    if (pm[i] - 1 == dp)
                        continue;
                    if (stm[pm[i]])
                        break;
                }
                if (n == i)
                    break;
                i = pm[i];
                sn += cl(q = ps[i], i - 1, i, 1, 1, n);
                for (gpm(n), t = n + 1, j = 0; j < n; ++j)
                {
                    if (q == pm[j] - 1)
                        continue;
                    d = cl(pm[j] - 1, i - 1, i, 0, 0, n);
                    if (d < t)
                        t = d, k = pm[j] - 1;
                }
                sn += cl(k, i - 1, i, 0, 1, n);
            }
        }
        if (qn < dqn)
            makeans(n);
        else
        {
            ans[0] = 0;
        }
        return (string)ans;
    };

    std::string solveNQueens(int n, std::pair<int, int> mandatoryQueenCoordinates)
    {
        return _cl(n, mandatoryQueenCoordinates.second, mandatoryQueenCoordinates.first);
    }
}

int main() {
    std::cout << "Hello world!" << std::endl;
    return 0;
}