$\Huge\texttt{407ms without DLX!}$

// Author: XZC(L_Wave)
// Language: Cpp/G++14
// Problem: Sudoku
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA1309
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// Create Time: 2023-02-03 08:41:17
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast", "inline")
#include<bits/stdc++.h>

namespace std
{
    template<typename T1,typename T2,typename T3>struct triplet{
        T1 first;T2 second;T3 third;
        friend bool operator ==(triplet x,triplet y){return x.first==y.first&&x.second==y.second&&x.third==y.third;}
        friend bool operator !=(triplet x,triplet y){return x.first!=y.first||x.second!=y.second||x.third!=y.third;}
        friend bool operator <(triplet x,triplet y){return x.first==y.first?x.second==y.second?x.third<y.third:x.second<y.second:x.first<y.first;}
        friend bool operator >(triplet x,triplet y){return x.first==y.first?x.second==y.second?x.third>y.third:x.second>y.second:x.first>y.first;}
        friend bool operator <=(triplet x,triplet y){return x.first==y.first?x.second==y.second?x.third<=y.third:x.second<y.second:x.first<y.first;}
        friend bool operator >=(triplet x,triplet y){return x.first==y.first?x.second==y.second?x.third>=y.third:x.second>y.second:x.first>y.first;}
        friend triplet operator +(triplet x,triplet y){return (triplet){x.first+y.first,x.second+y.second,x.third+y.third};}
        friend triplet operator -(triplet x,triplet y){return (triplet){x.first-y.first,x.second-y.second,x.third-y.third};}

        triplet& operator +=(triplet x){return (*this)=(*this)+x;}
        triplet& operator -=(triplet x){return (*this)=(*this)-x;}
    };
    template<typename T1,typename T2,typename T3>triplet<T1,T2,T3> make_triplet(T1 x,T2 y,T3 z){
        triplet<T1,T2,T3> res;
        res.first=x;res.second=y;res.third=z;return res;
    }
}

#define Rep(i, n) for(int i=0; i< (int)(n); i++)
#define Rpp(i, n) for(int i=1; i<=(int)(n); i++)
#define Dpp(i, n) for(int i=(int)n; i; i--)
#define Frr(i, s, e) for(int i=(int)(s); i<=(int)(e); i++)
#define Tc int T; cin >> T; while(T--)
#define Eps 1e-7
#define Pinf 0x3f3f3f3f3f3f3f3fLL
#define Ninf (long long)0xcfcfcfcfcfcfcfcfLL
#define Mem0(Cont) memset(Cont, 0, sizeof(Cont))
#define MemP(Cont) memset(Cont, 0x3f, sizeof(Cont))
#define MemN(Cont) memset(Cont, 0xcf, sizeof(Cont))
#define endl '\n'
//#define int long long
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define yes cout << "yes\n"
#define no cout << "no\n"
#define pjj pair <int, int>
#define ff first
#define ss second
//#define Files
using namespace std;

template <typename T> inline void Print(T x, char ed = '\n') { cout << x << ed; }
template <typename T> inline void Exit(T x, int cd = 0) { cout << x << endl; exit(cd); }
template <typename T> inline bool CheckMax(T& x, T y) { if(x < y) { x = y; return 1; } else return 0; }
template <typename T> inline bool CheckMin(T& x, T y) { if(y < x) { x = y; return 1; } else return 0; }
inline void Print_if(bool sth, string s1 = "Yes", string s2 = "No") { if(sth) cout << s1 << endl; else cout << s2 << endl; }

constexpr int N = 1 << 4 | 5, n = 16,
    b = (1 << 16) - 1, B = b << 1, sm = 4;

struct State {
    int ok;
    char pl;
    //0 -> 255: can I place this letter?
    //pl: what letter did I put? or 0 (nothing)
};

struct Grid {
    State state[N][N];
};

#define Gr(i, j) sudoku.state[i][j]

Grid sudoku;
bool finish, at;

stack <Grid> stk;

int sG(int x, int y) {
    return ((x+3)/4-1)*4+((y+3)/4);
}
pjj gR(int t) {
    return {((t+3)/4-1)*4+1, ((t-1)%4+1)*4-3};
}

void maintain() {
    Rpp(i, n) Rpp(j, n)
        Gr(i, j).ok = (!Gr(i, j).pl) * B;
    Rpp(i, n) {
        int est = B;
        Rpp(j, n) if(Gr(i, j).pl)
            est &= ~ (1 << (Gr(i, j).pl ^ 64));
        Rpp(j, n) if(!Gr(i, j).pl)
            Gr(i, j).ok &= est;
    }
    Rpp(j, n) {
        int est = B;
        Rpp(i, n) if(Gr(i, j).pl)
            est &= ~ (1 << (Gr(i, j).pl ^ 64));
        Rpp(i, n) if(!Gr(i, j).pl)
            Gr(i, j).ok &= est;
    }
    Rpp(i, n) {
        pjj p = gR(i);
        int est = B;
        Rep(dx, sm) Rep(dy, sm) {
            int nx = p.ff+dx, ny = p.ss+dy;
            if(Gr(nx, ny).pl)
                est &= ~ (1 << (Gr(nx, ny).pl ^ 64));
        }
        Rep(dx, sm) Rep(dy, sm) {
            int nx = p.ff+dx, ny = p.ss+dy;
            if(!Gr(nx, ny).pl)
                Gr(nx, ny).ok &= est;
        }
    }
}

bool read() {
    Rpp(i, n) Rpp(j, n) {
        char c;
        if(!(cin >> c)) return 0;
        if(c == '-') c = 0;
        Gr(i, j).pl = c;
    }
    maintain();
    return 1;
}

void print() {
    if(!at) at = 1;
    else cout << '\n';
    Rpp(i, n) Rpp(j, n) {
        if(!Gr(i, j).pl) cout << '-';
        else cout << Gr(i, j).pl;
        if(j == n) cout << '\n';
    }
    // Rpp(i, n) Rpp(j, n)
        // Gr(i, j).ok = (!Gr(i, j).pl) * B;
    // Rpp(i, n) {
        // int est = 0;
        // Rpp(j, n) if(Gr(i, j).pl)
            // est |= 1<<(Gr(i, j).pl^64);
        // assert(est == B);
    // }
    // Rpp(j, n) {
        // int est = B;
        // Rpp(i, n) if(Gr(i, j).pl)
            // est |= 1<<(Gr(i, j).pl^64);
        // assert(est == B);
    // }
    // Rpp(i, n) {
        // pjj p = gR(i);
        // int est = B;
        // Rep(dx, sm) Rep(dy, sm) {
            // int nx = p.ff+dx, ny = p.ss+dy;
            // if(Gr(nx, ny).pl)
                // est |= 1<<(Gr(nx, ny).pl^64);
        // }
        // assert(est == B);
    // }
}

void go(int x, int y, char c) {
    Gr(x, y).pl = c;
    Gr(x, y).ok = 0;
    Rpp(i, n) if(!Gr(i, y).pl)
        Gr(i, y).ok &= ~ (1 << (c ^ 96));
    Rpp(i, n) if(!Gr(x, i).pl)
        Gr(x, i).ok &= ~ (1 << (c ^ 96));
    pjj P = gR(sG(x, y));
    Rep(dx, sm) Rep(dy, sm) {
        int nx = P.ff+dx, ny = P.ss+dy;
        if(!Gr(nx, ny).pl)
            Gr(nx, ny).ok &= ~ (1 << (c ^ 96));
    }
}

void dfs() {
    // print();
    // bool ookk = 1;
    // Rpp(i, n) Rpp(j, n)
        // ookk &= Gr(i, j).pl;
    // if(ookk) return (void)(finish = ookk);
    Rpp(i, n) Rpp(j, n) {
        if(Gr(i, j).pl) continue;
        int popc = __builtin_popcountll(Gr(i, j).ok);
        if(!popc) return ;
        if(popc == 1) go(i, j, __builtin_ctzll(Gr(i, j).ok)^64);
    }
    // cout << "OK\n";
    Rpp(x, n)
        Frr(c, 'A', 'P') {
            bool hv = 0;
            Rpp(y, n) if(Gr(x, y).pl == c) hv = 1;
            if(hv) continue;
            int est = 0;
            Rpp(y, n) if(Gr(x, y).ok >> (c^64) & 1)
                est |= 1 << y;
            int popc = __builtin_popcountll(est);
            if(!popc) return ;
            if(popc == 1) go(x, __builtin_ctzll(est), c);
        }
    // cout << "OK\n";
    Rpp(y, n)
        Frr(c, 'A', 'P') {
            bool hv = 0;
            Rpp(x, n) if(Gr(x, y).pl == c) hv = 1;
            if(hv) continue;
            int est = 0;
            Rpp(x, n) if(Gr(x, y).ok >> (c^64) & 1)
                est |= 1 << x;
            int popc = __builtin_popcountll(est);
            // cout << y << ' ' << (char)c << endl;
            if(!popc) return ;
            if(popc == 1) go(__builtin_ctzll(est), y, c);
            // cout << y << ' ' << (char)c << endl;
        }
    // cout << "OK\n";
    Rpp(i, n) {
        pjj P = gR(i);
        Frr(c, 'A', 'P') {
            bool hv = 0;
            Rep(dx, 4) Rep(dy, 4)
                if(Gr(dx+P.ff, dy+P.ss).pl == c) hv = 1;
            if(hv) continue;
            int est = 0;
            Rep(dx, 4) Rep(dy, 4)
                if(Gr(dx+P.ff, dy+P.ss).ok >> (c^64) & 1)
                    est |= 1 << (dx*4+dy);
            int popc = __builtin_popcountll(est);
            if(!popc) return ;
            if(popc == 1) {
                int cd = __builtin_ctzll(est),
                    dx = cd >> 2, dy = cd & 3;
                go(dx+P.ff, dy+P.ss, c);
            }
        }
    }
    // cout << "OK\n";
    int minu = 17;
    pjj mp = {-1, -1};
    Rpp(i, n) Rpp(j, n) if(!Gr(i, j).pl)
        if(CheckMin(minu, __builtin_popcountll
            (Gr(i, j).ok))) mp = {i, j};
    if(minu == 17) {
        finish = 1;
        return ;
    }
    int est = Gr(mp.ff, mp.ss).ok;
    // cout << mp.ff << ' ' << mp.ss << endl;
    stk.push(sudoku);
    Frr(c, 'A', 'P')
        if(est >> (c^64) & 1) {
            go(mp.ff, mp.ss, c);
            dfs();
            if(finish) return ;
            sudoku = stk.top();
        }
    stk.pop();
}

bool solve() {
    if(!read()) return 0;
    finish = 0;
    dfs(); print();
    return 1;
}

signed main()
{
#ifdef Files
    freopen(".in", "r", stdin);
    freopen(".out", "w",stdout);
#endif
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    while(solve());

    return 0;
}

/*
 *  things to check
 *  1.  int overflow or long long memory need
 *  2.  recursion/array/binary search/dp/loop bounds
 *  3.  precision
 *  4.  special cases(n=1,bounds)
 *  5.  delete debug statements
 *  6.  initialize(especially multi-tests)
 *  7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
 *  8.  keep it simple and stupid
 *  9.  do not delete, use // instead
 *  10. operator priority
 *  11. is there anything extra to output?
 *  12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
 *  13. submit ONCE, AC once. submit twice, WA forever
 *  14. calm down and you'll get good rank
 *  15. even a bit wrong scores zero
 *  16. ...
 **/

/*
 *  something to think about
 *  1. greedy? dp? searching? dp with matrix/ segment tree? binary search? ...?
 *  2. If it is difficult, why not the opposite?
 **/