#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 120;
int g[N][N];
int d[N][N];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int n, m;
void bfs() {

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    queue<pair<int, int>> q;
    q.push({ 0,0 });
    while (!q.empty()) {
        auto top = q.front();
        for (int i = 0; i < 4; i++) {

            int x = top.first + dx[i], y = top.second + dy[i];
            if (x < n && x >= 0 && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0) {

                d[x][y] = d[top.first][top.second] + 1;
                q.push({ x,y });
            }
        }
        q.pop();
    }


    cout << d[n - 1][m - 1];
}
int main() {

    ios::sync_with_stdio(false);

    cin.tie(NULL);
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    bfs();
    return 0;
}

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
bool row[N];
/*void dfs(int deep)
{
    if (deep == n) {

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << g[i][j];
            }
            cout << '\n';
        }
        cout << '\n';
        return;
    }
    for (int i = 0; i < n; i++)
    {

        if (!col[i] && !dg[deep + i] && !udg[n - deep + i]) {

            g[deep][i] = 'Q';
            col[i] = dg[deep + i] = udg[n - deep + i] = true;
            dfs(deep + 1);
            col[i] = dg[deep + i] = udg[n - deep + i] = false;
            g[deep][i] = '.';
        }

    }

}
*/

void dfs(int x, int y, int s)
{
    if (s > n) return;
    if (y == n) y = 0, x++;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cout << g[i][j];
                }
                cout << '\n';
            }
            cout << '\n';

        }
        return;
    }
    g[x][y] = '.';
    //不放皇后
    dfs(x, y + 1, s);
    //放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[n - y + x])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n - y + x] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[n - y + x] = false;
        g[x][y] = '.';

    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);


    cin >> n;
    //初始化
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = '.';
    //dfs(0);
    dfs(0, 0, 0);

    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 10;
int a[N];
bool b[N];
void dfs(int kk)
{
    if (kk == n) {

        for (int i = 0; i < n; i++) cout << a[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (!b[i]) {

            a[kk] = i;
            b[i] = true;
            dfs(kk+1);
            a[kk] = 0;
            b[i] = false;
        }

    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    dfs(0);
    return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    vector<pair<int,int>> a(10+1);
    for (int i = 1; i <= 10; i++) cin >> a[i].second;

    sort(a.begin() + 1, a.end(), [](const auto& b1, const auto& b2)->bool {

        return b1.second < b2.second;
        });
    //cout << &a[0].second << ' ' << &a[1].second << ' ';
    //for (auto c : a) cout << c.second << ' ';
    for (int i = 1; i <= 10; i++) cout << a[i].second << ' ';
    cout << '\n';


    return 0;
}

#include<iostream>
typedef unsigned long long ULL;
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
char str[N];
ULL p[N], h[N];
ULL cp(int a, int b) {

    return h[b] - h[a - 1] * p[b - (a - 1)];

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    cin >> str + 1;
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + str[i];

        p[i] = p[i - 1] * P;

    }

    while (m--) {

        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (cp(a, b) == cp(c, d)) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

#include<iostream>

using namespace std;
const int N = 100003;
int ne[N], e[N], h[N], idx;
void insert(int kk) {

    int kk_1 = (kk % N + N) % N;

    e[idx] = kk;
    ne[idx] = h[kk_1];
    h[kk_1] = idx;
    idx++;


}
bool find(int kk) {

    int kk_1 = (kk % N + N) % N;
    for (int i = h[kk_1]; i != -1; i = ne[i])
        if (e[i] == kk) return true;

    return false;

}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < N; i++) h[i] = -1;
    int m;
    cin >> m;
    string s;
    int x;
    while (m--)
    {
        cin >> s;
        cin >> x;
        if (s == "I") {

            insert(x);
        }
        else {

            if (find(x)) cout << "Yes\n";
            else cout << "No\n";
        }


    }


    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N];
int cnt;
int m;//m用来记录第几个插入的数
void h_swap(int a, int b) {

    swap(h[a], h[b]);//交换值
    //交换两个映射
    //这个时候h的坐标是a,b所对应的p的坐标是hp[a],hp[b]
    swap(hp[a], hp[b]);

    swap(ph[hp[a]], ph[hp[b]]);

}
void down(int u) {

    int t = u;

    if (u * 2 <= cnt && h[t] > h[u * 2]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[t] > h[u * 2 + 1]) t = u * 2 + 1;

    if (t != u) {

        h_swap(t, u);
        down(t);
    }

}
void up(int u) {



    while (u / 2 != 0 && h[u] < h[u / 2]) {

        h_swap(u, u / 2);

        u /= 2;

    }

}
int main() {


    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {

        string s;
        cin >> s;
        if (s == "I") {

            int a;
            cin >> a;
            h[++cnt] = a;
            ph[++m] = cnt;
            hp[cnt] = m;
            up(cnt);
        }
        else if (s == "PM") cout << h[1] << "\n";
        else if (s == "DM") {

            h_swap(1, cnt);
            cnt--;
            down(1);
        }
        else if (s == "D") {

            int a;
            cin >> a;
            a = ph[a];
            h_swap(a, cnt);
            cnt--;
            up(a);
            down(a);
        }
        else {
            int a;
            cin >> a;
            int b;
            cin >> b;
            a = ph[a];

            h[a] = b;
            down(a);
            up(a);

        }
    }

    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
using i64 = long long;
const int N = 100010;
int n, m;
int h[N], size_h;//h->heap
void down(int u) {
    int t = u;//t存的是三个点中最小点的编号,一开始假设要down的点是最小值
    //判断左子节点
    if (u * 2 <= size_h && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size_h && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {//这也是为什么要开t的原因,因为要判断与原来的点是否相同,如果kk!=t的话说明一开始认为的点不是最小值点的编号

        swap(h[u], h[t]);
        down(t);//要全部都比较过才算把位置正确分配
    }
}
int main() {
    ios::sync_with_stdio(false);;
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> h[i];
    size_h = n;
    for (int i = n / 2; i; i--) down(i);
    while (m--) {

        cout << h[1] <<' ';
        h[1] = h[size_h];
        size_h--;
        down(1);
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n, m;
int find(int kk) {

    if (q[kk] != kk) q[kk] = find(q[kk]);
    return q[kk];
}
int main() {
    ios::sync_with_stdio(false);;
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        q[i] = i;
    }
    while (m--) {
        int b, c;
        char a;
        cin >> a;
        if (a == 'M') {

            cin >> b >> c;
            q[find(b)] = find(c);
        }
        else {
            cin >> b >> c;
            if (find(b) == find(c)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

#include<iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
//cnt存储的是以当前这个点单词有多少个,idx表示当前用到了哪个下标
char str[N];
void insert(char str[]) {//插入一个字符串

    int p = 0;//从根节点开始

    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';//将字母映射成数字
        if (!son[p][u]) son[p][u] = ++idx; //如果这个节点不存在就创建出来

        p = son[p][u]; //走到下一个点
    }
    cnt[p]++;//表示以这个点结尾的单词数量多了一个
}
int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;//查询不出来就返回0
        p = son[p][u]; //否则就走过去
    }
    return cnt[p];//返回以p节点的单词数量
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    while (n--)
    {
        char op[2];
        cin >> op >> str;
        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }


    return 0;
}