void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N + 1);
    rep(i, N) cin >> P[i + 1];

    double INF = 100000;
    // dp[i][num]: i番目までの問題を選んで、num 個選んだときの \sum_{i=1}^k (0.9)^{k-i} Q[i] の最大値
    vector dp(N + 1, vector<double>(N + 1, -INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(num, i + 1) {
            chmax(dp[i][num], dp[i - 1][num]);

            if (dp[i - 1][num] != -INF)
                chmax(dp[i][num + 1], dp[i - 1][num] * 0.9 + P[i]);
        }
    }

    vector<double> pow(N + 1), prd(N + 1);
    pow[0] = prd[0] = 1;
    rep2(i, 1, N + 1) {
        pow[i] = pow[i - 1] * 0.9;
        prd[i] += pow[i] + prd[i - 1];
    }

    double ans = -INF;
    rep2(num, 1, N + 1) {
        chmax(ans, dp[N][num] / prd[num - 1] - 1200.0 / sqrt(num));
    }
    printf("%.9lf\n", ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) {
        cin >> A[i];
        A[i] %= 200;
    }

    map<int, vvint> mp;
    int n = min(N, 8ll);
    rep2(i, 1, 1 << n) {
        vint v;
        ll sum = 0;
        rep(j, n) if ((i >> j) & 1) {
            v.push_back(j + 1);
            sum += A[j];
        }
        sum %= 200;
        mp[sum].push_back(v);
    }

    for (auto [k, vv] : mp) {
        if (vv.size() >= 2) {
            Yes();
            rep(i, 2) {
                cout << vv[i].size() << ' ';
                print(vv[i]);
            }
            return;
        }
    }

    No();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cumsum(N + 1), mi(N + 1);
    rep(i, N) {
        cumsum[i + 1] = cumsum[i] + A[i];
    }

    ll ans = -INF;
    rep2(i, 1, N + 1) {
        chmax(ans, cumsum[i] - mi[i - 1]);
        mi[i] = min(mi[i - 1], cumsum[i]);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string P;
    int L;
    cin >> P >> L;
    yesno((int)P.size() >= L);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll D(N);
    rep2(i, 1, N) cin >> D[i];

    rep(i, N) {
        ll sum = 0;
        vll ans;
        rep2(j, i + 1, N) {
            sum += D[j];
            ans.push_back(sum);
        }
        print(ans);
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto f = [&](ll x) -> ll {
        ll ret = 0;
        for (ll a : A) ret += (a + x - 1) / x - 1;
        return ret;
    };

    ll ac = INF, wa = 0;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj) <= K) {
            ac = wj;
        } else {
            wa = wj;
        }
    }
    cout << ac << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto f = [&](ll x) -> bool {
        ll cnt = 0;
        rep(i, N) {
            cnt += min(A[i], x);
        }
        return cnt < K;
    };

    ll ac = 0, wa = INF;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }

    rep(i, N) {
        ll x = A[i];
        K -= min(x, ac);
        A[i] -= min(x, ac);
    }

    int i = 0;
    while (K) {
        if (A[i] > 0) {
            K--;
            A[i]--;
        }
        i++;
    }
    print(A);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    vint col(N);
    rep(i, N) cin >> col[i];
    vector<set<int>> balls(N);
    rep(i, N) balls[i].insert(col[i]);

    rep(i, Q) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (balls[a].size() < balls[b].size()) {
            for (ll x : balls[a]) balls[b].insert(x);
            balls[a].clear();
        } else {
            for (ll x : balls[b]) balls[a].insert(x);
            balls[b].clear();
            swap(balls[a], balls[b]);
        }
        cout << balls[b].size() << endl;
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    using P = pair<ll, ll>;
    vector<vector<P>> graph(N);
    rep(i, M) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u].emplace_back(v, w);
    }

    vector used(N, vint(1 << 10, 0));
    used[0][0] = true;

    auto dfs = [&](auto dfs, int now, ll xor_sum) -> void {
        for (auto [nx, w] : graph[now]) {
            ll nx_xor_sum = xor_sum ^ w;
            if (used[nx][nx_xor_sum]) continue;
            used[nx][nx_xor_sum] = true;
            dfs(dfs, nx, nx_xor_sum);
        }
    };

    dfs(dfs, 0, 0);

    ll ans = INF;
    rep(i, 1 << 10) {
        if (used[N - 1][i]) chmin(ans, i);
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<tuple<ll, ll, ll>> nodes;
    rep(i, N) {
        ll x, y, P;
        cin >> x >> y >> P;
        nodes.emplace_back(x, y, P);
    }

    auto f = [&](ll x) -> bool {
        rep(s, N) {
            vector<bool> used(N);
            used[s] = true;
            queue<int> que;
            que.push(s);
            while (que.size()) {
                int now = que.front();
                que.pop();

                rep(nx, N) {
                    if (nx == now) continue;
                    if (used[nx]) continue;
                    auto [xi, yi, pi] = nodes[now];
                    auto [xj, yj, pj] = nodes[nx];
                    if (pi * x >= abs(xi - xj) + abs(yi - yj)) {
                        used[nx] = true;
                        que.push(nx);
                    }
                }
            }

            ll sum = accumulate(all(used), 0);
            if (sum == N) return true;
        }
        return false;
    };

    ll ac = 0;
    rep(i, N) rep(j, N) {
        auto [xi, yi, pi] = nodes[i];
        auto [xj, yj, pj] = nodes[j];
        chmax(ac, abs(xi - xj) + abs(yi - yj));
    }

    ll wa = -1;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj))
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint Kbit;
    vvint Abit(N);
    int mx = 60;

    {
        ll t = K;
        rep(i, mx) {
            Kbit.push_back(t % 2);
            t /= 2;
        }
        reverse(all(Kbit));

        rep(i, N) {
            ll a = A[i];
            rep(j, mx) {
                Abit[i].push_back(a % 2);
                a /= 2;
            }
            reverse(all(Abit[i]));
        }
    }

    vector dp(mx + 1, vll(2));
    rep2(i, 1, mx + 1) {
        int t = Kbit[i - 1];
        ll cnt = 0;
        rep(j, N) {
            cnt += Abit[j][i - 1];
        }

        rep(d, 2) {
            if (d < t) {
                chmax(dp[i][1], dp[i - 1][0] * 2 + cnt);
            }
            if (d == t) {
                if (d == 0)
                    chmax(dp[i][0], dp[i - 1][0] * 2 + cnt);
                else
                    chmax(dp[i][0], dp[i - 1][0] * 2 + N - cnt);
            }
            if (dp[i - 1][1]) {
                chmax(dp[i][1], dp[i - 1][1] * 2 + max(N - cnt, cnt));
            }
        }
    }

    cout << max(dp[mx][0], dp[mx][1]) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;

    auto cal = [](string S) -> ll {
        int N = S.size();
        vector dp(N + 1, vector(2, vector(2, vll(2))));
        dp[0][0][0][0] = 1;

        rep2(i, 1, N + 1) {
            int t = S[i - 1] - '0';
            rep(d, 10) {
                bool has_four = d == 4;
                bool has_nine = d == 9;
                if (d < t) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                if (t == d) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][0][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                rep(fr, 2) rep(ni, 2) {
                    dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][1][fr][ni];
                }
            }
        }

        ll ret = 0;
        rep(fr, 2) rep(ni, 2) {
            if (fr == 0 && ni == 0) continue;
            ret += dp[N][1][fr][ni] + dp[N][0][fr][ni];
        }

        return ret;
    };
    // cout << cal(B) << endl;
    // cout << cal(A) << endl;

    cout << cal(B) - cal(to_string(stoll(A) - 1)) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    ll K;
    cin >> N >> K;

    int M = N.size();
    vector dp(M + 1, vector(2, vll(K + 2)));
    dp[0][0][0] = 1;
    rep2(i, 1, M + 1) {
        int t = N[i - 1] - '0';
        rep(d, 10) {
            int is_not_zero = d != 0;
            rep(c, 4) {
                int nxc = min(c + is_not_zero, K + 1);
                if (d < t) {
                    dp[i][1][nxc] += dp[i - 1][0][c];
                }
                if (d == t) {
                    dp[i][0][nxc] += dp[i - 1][0][c];
                }
                dp[i][1][nxc] += dp[i - 1][1][c];
            }
        }
    }

    ll ans = dp[M][1][K] + dp[M][0][K];
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    cin >> N;

    int sz = N.size();

    int mx = 15;
    vector dp(sz + 1, vector(2, vector<mint>(mx)));
    dp[0][0][0] = 1;

    rep2(i, 1, sz + 1) {
        int t = N[i - 1] - '0';
        rep(d, 10) {
            bool is_one = d == 1;
            rep(c, mx) {
                if (d < t) {
                    dp[i][1][c + is_one] += dp[i - 1][0][c];
                }
                if (d == t) {
                    dp[i][0][c + is_one] += dp[i - 1][0][c];
                }
                dp[i][1][c + is_one] += dp[i - 1][1][c];
            }
        }
    }

    mint ans = 0;
    rep2(c, 1, mx) {  // (N 未満の数で 1 の個数が c 個である数の個数) * c
        ans += dp[sz][1][c] * c;
    }
    for (char c : N) {  // N そのものの 1 の個数を数える
        if (c == '1') ans++;
    }
    cout << ans.val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vll A(N);
    rep(i, N) cin >> A[i];

    ll l = A[0], r = A[1];
    vll B;
    rep2(i, 2, N) B.push_back(A[i]);
    sort(all(B));

    ll ans = INF;
    for (int i = 0; i + M - 1 < N - 2; i++) {
        ll left = B[i], right = B[i + M - 1];
        ll tmp = 0;
        if (left < l) tmp += l - left;
        if (r < right) tmp += right - r;
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto _cal = []() -> void {
        int N;
        string S;
        cin >> N >> S;

        // dp[i][j]: i 番目まで決めて末尾がグループ j に属したときの最小コスト
        vvll dp(N + 1, vll(3, INF));
        rep(i, 3) dp[0][i] = 0;

        rep2(i, 1, N + 1) {
            rep(j, 3) {
                if (j == 0) {
                    chmin(dp[i][0], dp[i - 1][0] + (ll)(S[i - 1] == '1'));
                }
                if (j == 1) {
                    chmin(dp[i][1], min(dp[i - 1][0], dp[i - 1][1]) + (ll)(S[i - 1] == '0'));
                }
                if (j == 2) {
                    chmin(dp[i][2], min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + (ll)(S[i - 1] == '1'));
                }
            }
        }

        ll ans = INF;
        rep(i, 3) chmin(ans, dp[N][i]);
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) _cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, a, b;
    cin >> N >> a >> b;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto check = [&](ll x) -> bool {
        ll l = 0, r = 0;
        rep(i, N) {
            if (A[i] < x) {
                // x がめちゃでかくて a がめちゃ小さくと N が O(10) くらいのオーダーでも l が long long int の範疇に収まらない
                l += (x - A[i] + a - 1) / a;
            } else {
                r += (A[i] - x) / b;
            }
        }

        return l <= r;
    };

    // wa に 2e18+9 を使ったら WA した
    // N=12, a = b = 1, A は 10^9 を 12 にしたら check 関数の中で overflow していた
    ll ac = 0, wa = *max_element(all(A)) + 1;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (check(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }

    cout << ac << endl;
}

template <typename T>
vector<pair<T, int>> runLengthEncode(const vector<T>& input) {
    vector<pair<T, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    auto ps = runLengthEncode(A);
    if (ps.size() == 1) {
        cout << N + 1 << endl;
        return;
    }

    int m = ps.size();

    int mone = 0, pone = 0;
    bool is_init_one = ps[0].first == 1;
    int s0 = 0, s1 = 1;
    if (is_init_one) swap(s0, s1);
    int sum0 = 0;
    for (int i = s0; i < m; i += 2) {
        sum0 += ps[i].second;
        chmax(pone, sum0);
        if (i + 1 < m) {
            sum0 -= ps[i + 1].second;
            if (sum0 < 0) sum0 = 0;
        }
    }
    int sum1 = 0;
    for (int i = s1; i < m; i += 2) {
        sum1 += ps[i].second;
        chmax(mone, sum1);
        if (i + 1 < m) {
            sum1 -= ps[i + 1].second;
            if (sum1 < 0) sum1 = 0;
        }
    }

    int cnt_one = accumulate(all(A), 0);
    int r = cnt_one + pone;
    int l = cnt_one - mone;
    cout << r - l + 1 << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    if (N == 1) {
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }

    vint ans;
    for (int i = 2; i <= N; i += 2) {
        ans.push_back(i);
    }

    cout << ans.size() << endl;
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    cin >> a >> b;

    ll mi = INF;
    ll ans = 0;
    for (ll x = 0; x <= 1000; x++) {
        if (abs(a - x * b) < mi) {
            ans = x;
            mi = abs(a - x * b);
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, D;
    cin >> H >> W >> D;

    vector A(H, vll(W));
    rep(i, H) rep(j, W) {
        cin >> A[i][j];
        A[i][j]--;
    }

    vector<pair<int, int>> num_pos(H * W);
    rep(i, H) rep(j, W) num_pos[A[i][j]] = {i, j};

    int Q;
    cin >> Q;
    vector<pair<int, int>> queries;
    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        queries.emplace_back(l, r);
    }

    vint rmax(D, 0);
    vector<bool> rexists(D, 0);
    for (auto [l, r] : queries) {
        chmax(rmax[r % D], r);
        rexists[r % D] = true;
    }

    map<pair<int, int>, ll> memo;
    auto f = [&](auto f, int l, int r) -> ll {
        if (l == r)
            return 0;
        auto [ni, nj] = num_pos[l + D];
        auto [i, j] = num_pos[l];
        return memo[{l, r}] = abs(ni - i) + abs(nj - j) + f(f, l + D, r);
    };

    rep(i, D) {
        if (!rexists[i])
            continue;
        f(f, i, rmax[i]);
    }

    for (auto [l, r] : queries) {
        int rmx = rmax[r % D];
        cout << memo[{l, rmx}] - memo[{r, rmx}] << '\n';
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int K;
    cin >> K;
    vector<pair<int, int>> ps;
    rep(i, K) {
        int p, d;
        cin >> p >> d;
        p--;
        ps.push_back({p, d});
    }

    auto short_path = [](vvint& graph, int start) -> vint {
        int N = graph.size();
        vint dist(N, INF);
        dist[start] = 0;

        // cost, position
        using P = pair<ll, int>;
        deque<P> deq;
        deq.push_back({0, start});
        while (deq.size()) {
            auto [cost, now] = deq.front();
            deq.pop_front();

            if (dist[now] < cost)
                continue;

            for (int nx : graph[now]) {
                if (dist[nx] <= cost + 1)
                    continue;
                dist[nx] = cost + 1;
                deq.push_back({cost + 1, nx});
            }
        }

        return dist;
    };

    vvint dists(N);
    rep(i, N) {
        dists[i] = short_path(graph, i);
    }

    // 一旦全ての頂点を黒く塗る
    vint black(N, 1);

    // 頂点 p から d より近いところにある黒を白く塗り直す
    for (auto [p, d] : ps) {
        rep(i, N) {
            if (dists[p][i] < d)
                black[i] = 0;
        }
    }

    // 各頂点について条件を満たす黒い頂点があるか調べる
    for (auto [p, d] : ps) {
        int ok = 0;
        rep(i, N) {
            if (dists[p][i] == d && black[i])
                ok = 1;
        }
        if (!ok) {
            yesno(false);
            return;
        }
    }

    yesno(true);
    for (int x : black)
        cout << x;
    cout << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll B, C;
    cin >> B >> C;

    vector<pair<ll, ll>> ps;
    ps.emplace_back(B - C / 2, B + (C - 2) / 2);
    ps.emplace_back(-B - (C - 1) / 2, -B + (C - 1) / 2);
    sort(all(ps));

    if (ps[0].second >= ps[1].first) {
        ps[0].second = ps[1].second;
        ps.pop_back();
    }

    ll ans = 0;
    for (auto [x, y] : ps) {
        ans += y - x + 1;
    }
    cout << ans << endl;
}

def main():
    n, k = map(int, input().split())
    a = map(int, input().split())

    mx = 10**k
    ans = 1
    for i in a:
        ans *= i
        if ans >= mx:
            ans = 1

    print(ans)

main()

ll intpow(ll x, ll n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    ll mx = intpow(10, K) - 1;
    ll ans = 1;
    for (ll a : A) {
        if (ans > mx / a) {
            ans = 1;
        } else {
            ans *= a;
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, L;
    cin >> N >> L;
    vll X(N);
    rep(i, N) cin >> X[i];
    ll T1, T2, T3;
    cin >> T1 >> T2 >> T3;

    vll hurdles(L + 1);
    for (ll x : X)
        hurdles[x] = 1;

    vll dp(L + 1, INF);
    dp[0] = 0;
    rep2(i, 1, L + 1) {
        ll offset = hurdles[i] * T3;
        chmin(dp[i], dp[i - 1] + T1 + offset);
        if (i - 2 >= 0) {
            chmin(dp[i], dp[i - 2] + T1 + T2 + offset);
        }
        if (i - 4 >= 0) {
            chmin(dp[i], dp[i - 4] + T1 + T2 * 3 + offset);
        }

        // ジャンプして超える
        if (i == L) {
            if (i - 3 >= 0) {
                chmin(dp[i], dp[i - 3] + T1 / 2 + T2 / 2 * 5);
            }
            if (i - 2 >= 0) {
                chmin(dp[i], dp[i - 2] + T1 / 2 + T2 / 2 * 3);
            }
            if (i - 1 >= 0) {
                chmin(dp[i], dp[i - 1] + T1 / 2 + T2 / 2);
            }
        }
    }
    cout << dp[L] << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    auto is_seq = [&](int l, int r) -> bool {
        bool ok = false;
        r++;
        rep2(i, l, r) {
            rep2(j, i + 1, r) {
                rep2(k, j + 1, r) {
                    if (A[j] - A[i] == A[k] - A[j])
                        ok = true;
                }
            }
        }
        return ok;
    };

    ll ans = N * (N + 1) / 2;
    rep(l, N) {
        rep2(r, l, N) {
            if (is_seq(l, r)) {
                break;
            } else {
                ans--;
            }
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int si = 0, sj = 0;
    vector<pair<int, int>> exits;
    rep(i, H) rep(j, W) {
        if (grid[i][j] == 'E')
            exits.push_back({i, j});
    }

    // i,j, cost
    vvll dist(H, vll(W, INF));
    deque<tuple<ll, ll, ll>> deq;
    for (auto [i, j] : exits) {
        deq.push_back({i, j, 0});
        dist[i][j] = 0;
    }

    vll di = {0, 1, 0, -1};
    vll dj = {1, 0, -1, 0};
    while (deq.size()) {
        auto [nowi, nowj, cost] = deq.front();
        deq.pop_front();

        if (dist[nowi][nowj] < cost)
            continue;

        rep(dir, 4) {
            ll ni = nowi + di[dir], nj = nowj + dj[dir];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                continue;
            if (grid[ni][nj] == '#')
                continue;
            if (dist[ni][nj] <= cost + 1)
                continue;
            dist[ni][nj] = cost + 1;
            deq.push_back({ni, nj, dist[ni][nj]});
        }
    }

    vector<char> dir_mark = {'>', 'v', '<', '^'};

    vector<string> ans = grid;

    rep(i, H) {
        rep(j, W) {
            if (grid[i][j] == '#' || grid[i][j] == 'E')
                continue;
            rep(dir, 4) {
                ll ni = i + di[dir], nj = j + dj[dir];
                if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                    continue;
                if (dist[i][j] == dist[ni][nj] + 1) {
                    ans[i][j] = dir_mark[dir];
                }
            }
        }
    }

    for (auto s : ans)
        cout << s << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto check = [](string X, string Y) -> bool {
        int n = X.size();
        int xa = 0, ya = 0;
        for (char c : X) {
            if (c == 'A')
                xa++;
        }
        for (char c : Y) {
            if (c == 'A')
                ya++;
        }

        if (xa > ya)
            return false;

        int rema = ya - xa;
        rep(i, n) {
            if (X[i] == 'C') {
                if (rema) {
                    X[i] = 'A';
                    rema--;
                } else {
                    X[i] = 'B';
                }
            }
        }

        set<int> xbpos;
        rep(i, n) {
            if (X[i] == 'B')
                xbpos.insert(i);
        }

        rep(i, n) {
            if (X[i] == Y[i])
                continue;
            if (X[i] == 'B' && Y[i] == 'A')
                return false;
            if (X[i] == 'A' && Y[i] == 'B') {
                auto it = xbpos.lower_bound(i);
                if (it == xbpos.end())
                    return false;
                swap(X[i], X[*it]);
                xbpos.erase(it);
            }
        }

        return true;
    };

    auto cal = [&]() -> void {
        int N;
        string X, Y;
        cin >> N >> X >> Y;

        if (X == Y) {
            yesno(true);
            return;
        }

        // sentinel
        X.push_back('C');
        Y.push_back('C');

        N++;
        int start = 0;
        rep(i, N) {
            if (Y[i] == 'C' && X[i] != 'C') {
                yesno(false);
                return;
            }

            if (X[i] == 'C' && Y[i] == 'C') {
                int len = i - start;
                if (!check(X.substr(start, len), Y.substr(start, len))) {
                    yesno(false);
                    return;
                };
                start = i + 1;

                continue;
            }
        }
        yesno(true);
    };

    int t;
    cin >> t;
    rep(i, t) {
        cal();
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    vint s, t;
    rep(i, N) {
        if (S[i] == '0')
            s.push_back(i);
        if (T[i] == '0')
            t.push_back(i);
    }

    if (s.size() != t.size()) {
        cout << -1 << endl;
        return;
    }

    int ans = 0;
    rep(i, s.size()) {
        if (s[i] != t[i])
            ans++;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<string> S(N), T(N);
    rep(i, N) cin >> S[i];
    rep(i, N) cin >> T[i];

    auto rotr90 = [&](vector<string>& S) -> vector<string> {
        vector<string> newS = S;
        rep(i, N) {
            rep(j, N) {
                // newS[j][N - 1 - i] = S[i][j];
                newS[i][j] = S[N - j - 1][i];
            }
        }
        return newS;
    };

    ll ans = INF;
    rep(k, 4) {
        if (k)
            S = rotr90(S);
        ll cnt = k;
        rep(i, N) rep(j, N) {
            if (S[i][j] != T[i][j])
                cnt++;
        }
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

+--B-W-W-B--+       +--W-B-B-W--+
W           W       B           B
|           |       |           |
B           B       W           W
+----...----+       +----...----+

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> es;

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        es.emplace_back(a, b);
    }

    vint col(N);
    rep(i, N) cin >> col[i];

    vector<pair<int, int>> same_col;

    dsu uf(N);
    for (auto [u, v] : es) {
        if (col[u] != col[v])
            uf.merge(u, v);
        else
            same_col.push_back({u, v});
    }

    int ok = 0;
    for (auto [u, v] : same_col) {
        if (uf.same(u, v))
            ok = 1;
    }
    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector dist(N, vll(N, INF));
    rep(i, M) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        dist[u][v] = c;
    }
    rep(i, N) dist[i][i] = 0;

    ll ans = 0;
    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
                if (dist[i][j] != INF) {
                    ans += dist[i][j];
                }
            }
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll K;
    string S, T;
    cin >> K >> S >> T;

    vll cnt(10, K);
    rep(i, 4) {
        cnt[S[i] - '0']--;
        cnt[T[i] - '0']--;
    }

    auto score = [&](string s) -> ll {
        vll used(10);
        for (char c : s)
            used[c - '0']++;
        ll ans = 0;
        rep2(i, 1, 10) {
            ans += i * intpow(10, used[i]);
        }
        return ans;
    };

    ll ans = 0;
    S[4] = T[4] = '0';
    rep2(i, 1, 10) {
        rep2(j, 1, 10) {
            S.back() = '0' + i;
            T.back() = '0' + j;

            if (score(S) <= score(T))
                continue;

            ans += cnt[i] * (cnt[j] - (i == j));
        }
    }

    ll rem = K * 9 - 8;
    printf("%.9lf\n", (double)ans / (double)(rem * (rem - 1)));
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M, K;
    cin >> N >> M >> K;

    vector<tuple<int, int, int>> es;
    rep(i, M) {
        int u, v, a;
        cin >> u >> v >> a;
        u--, v--;
        es.emplace_back(u, v, a);
    }

    vector<bool> sw(N);
    rep(i, K) {
        int s;
        cin >> s;
        s--;
        sw[s] = true;
    }

    vvint graph(N * 2);
    for (auto [u, v, a] : es) {
        if (a == 1) {
            graph[u].push_back(v);
            graph[v].push_back(u);
        } else {
            graph[u + N].push_back(v + N);
            graph[v + N].push_back(u + N);
        }
        if (sw[u]) {
            graph[u].push_back(u + N);
            graph[u + N].push_back(u);
        }
        if (sw[v]) {
            graph[v].push_back(v + N);
            graph[v + N].push_back(v);
        }
    }

    vll dists(N * 2, INF);
    dists[0] = 0;

    // cost, position
    deque<pair<ll, ll>> dq;
    dq.push_back({0, 0});
    while (dq.size()) {
        auto [cost, now] = dq.front();
        dq.pop_front();

        if (dists[now] < cost)
            continue;

        for (int nx : graph[now]) {
            ll d = cost;
            int add = 0;
            if (abs(nx - now) != N) {
                d++;
                add++;
            }
            if (dists[nx] <= d)
                continue;
            dists[nx] = d;
            if (add)
                dq.push_back({d, nx});
            else
                dq.push_front({d, nx});
        }
    }

    ll ans = INF;
    chmin(ans, dists[N - 1]);
    chmin(ans, dists[N * 2 - 1]);
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, D;
    cin >> N >> D;
    vll A(N);
    rep(i, N) cin >> A[i];

    if (D == 0) {
        ll ans = 0;
        map<ll, ll> cnt;
        for (ll x : A)
            cnt[x]++;
        for (auto [k, v] : cnt) {
            ans += v - 1;
        }
        cout << ans << endl;
        return;
    }

    map<ll, ll> cnts;
    for (ll x : A)
        cnts[x]++;

    ll ans = 0;
    set<int> used;
    for (auto [k, v] : cnts) {
        if (used.count(k))
            continue;
        vll B = {v};
        used.insert(k);
        ll t = k;
        while (cnts.count(t + D)) {
            t += D;
            B.push_back(cnts[t]);
            used.insert(t);
        }

        // dp[i][j] : i 1 捨てる, 0 捨てない
        // j 個目の数に対して
        vvll dp(2, vll(B.size() + 1, INF));
        dp[0][0] = dp[1][0] = 0;
        rep2(i, 1, B.size() + 1) {
            dp[0][i] = dp[1][i - 1];                                // i 番目を採用する場合は i-1 番目は削除する必要がある
            dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + B[i - 1];  // i 番目を削除する場合は i-1 番目は削除してもしなくてもどっちでもいい
        }
        ans += min(dp[0][B.size()], dp[1][B.size()]);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    vint depth(N);
    vll B(N);
    B[0] = A[0];
    rep2(i, 1, N) {
        int p;
        cin >> p;
        p--;
        depth[i] = depth[p] + 1;
        B[depth[i]] += A[i];
    }

    string ans = "0";
    for (int i = N - 1; i >= 0; i--) {
        if (B[i] == 0)
            continue;
        if (B[i] < 0)
            ans = "-";
        if (B[i] > 0)
            ans = "+";
        break;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvll A(M);
    rep(i, M) {
        int K;
        cin >> K;
        rep(j, K) {
            ll a;
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    vll B(N);
    rep(i, N) {
        cin >> B[i];
        B[i]--;
    }

    // shokuzai[i]: 食材 i を使っている料理の番号
    vvll shokuzai(N);
    rep(i, M) {
        for (ll a : A[i]) {
            shokuzai[a].push_back(i);
        }
    }

    // nums[i]: 料理 i に含まれる苦手な食材の数
    vll nums(M, 0);
    rep(i, M) nums[i] = A[i].size();

    ll ans = 0;
    for (ll b : B) {
        for (ll i : shokuzai[b]) {
            nums[i]--;
            if (nums[i] == 0)
                ans++;
        }
        cout << ans << endl;
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;
    vll a(n), b(n), c(n);
    rep(i, n) cin >> a[i] >> b[i] >> c[i];

    vector<vector<pair<ll, ll>>> lec(5001);
    rep(i, n) {
        lec[b[i]].push_back({a[i], c[i]});
    }

    vvll dp(5001, vll(m + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, 5001) {
        rep(j, m + 1) {
            // i 限目の科目を取らない場合
            chmin(dp[i][j], dp[i - 1][j]);

            // i 限目の科目を取る場合
            rep(k, lec[i].size()) {
                chmin(dp[i][j], dp[i - 1][max(0ll, j - lec[i][k].second)] + lec[i][k].first);
            }
        }
    }

    ll ans = dp[5000][m];
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

vector<pair<char, int>> runLengthEncode(const string& input) {
    vector<pair<char, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    string S;
    cin >> N >> K >> S;

    rep(i, N) {
        if (i + 1 < N && S[i] == '?' && S[i + 1] == 'o') {
            S[i] = '.';
        }
        if (i + 1 < N && S[i] == 'o' && S[i + 1] == '?') {
            S[i + 1] = '.';
        }
    }

    int no = 0;
    for (char c : S)
        if (c == 'o')
            no++;
    if (no == K) {
        rep(i, N) if (S[i] == '?') S[i] = '.';
        cout << S << endl;
        return;
    }

    auto ps = runLengthEncode(S);
    int m = 0;
    for (auto [c, num] : ps) {
        if (c == 'o')
            m += num;
        if (c == '?')
            m += (num + 1) / 2;
    }

    if (m > K) {
        cout << S << endl;
        return;
    }

    for (auto [c, num] : ps) {
        if (c != '?') {
            rep(i, num) cout << c;
            continue;
        }

        if (num % 2 == 0) {
            rep(i, num) cout << '?';
        } else {
            rep(i, num) {
                cout << (i % 2 == 0 ? 'o' : '.');
            }
        }
    }
    cout << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    set<ll> check, stock;
    stock.insert(0);

    while ((int)check.size() != K + 1) {
        auto it = stock.begin();
        ll x = *it;
        stock.erase(it);

        check.insert(x);
        for (ll a : A)
            stock.insert(x + a);
    }
    cout << *check.rbegin() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vll powers(N, -1);
    rep(i, K) {
        int p, h;
        cin >> p >> h;
        p--;
        powers[p] = h;
    }

    // power, node id
    using P = pair<ll, int>;
    priority_queue<P> pq;
    rep(i, N) {
        if (powers[i] > 0)
            pq.push({powers[i], i});
    }

    while (pq.size()) {
        auto [power, id] = pq.top();
        pq.pop();

        if (powers[id] > power)
            continue;

        for (int nx : graph[id]) {
            if (powers[nx] >= power - 1)
                continue;
            powers[nx] = power - 1;
            pq.push({powers[nx], nx});
        }
    }

    vint ans;
    rep(i, N) {
        if (powers[i] >= 0)
            ans.push_back(i + 1);
    }
    cout << ans.size() << endl;
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];

    vint v;

    auto dfs = [&](auto dfs, int used) -> void {
        if (__builtin_popcount(used) == k) {
            v.push_back(used);
            return;
        }

        int id = -1;
        rep(i, n) {
            if ((used >> i) & 1)
                id = i;
        }
        rep2(i, id + 1, n) {
            dfs(dfs, used | (1 << i));
        }
    };

    dfs(dfs, 0);

    ll ans = 0;
    for (int used : v) {
        rep(i, n) {
            if ((used >> i) & 1)
                ans += a[i];
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    map<int, vint> mp;
    rep(i, N) {
        mp[A[i]].push_back(i);
    }

    int cnt = 1;
    vint ans(N);
    for (auto it = mp.begin(); it != mp.end(); it++) {
        auto [_, ids] = *it;
        for (int id : ids) {
            ans[id] = cnt++;
        }
    }
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint as(M), bs(M);
    rep(i, M) {
        int k;
        cin >> k;
        rep(j, k) {
            int a, b;
            cin >> a >> b;
            a--;
            as[i].push_back(a);
            bs[i].push_back(b);
        }
    }

    rep(t, 1 << N) {
        vint xs;
        rep(i, N) {
            xs.push_back((t >> i) & 1);
        }

        int cnt = 0;
        rep(i, M) {
            int ok = 0;
            int ki = as[i].size();
            rep(j, ki) {
                if (xs[as[i][j]] == bs[i][j])
                    ok = 1;
            }
            if (ok)
                cnt++;
        }

        if (cnt == M) {
            yesno(true);
            return;
        }
    }
    yesno(false);
}

// DP 解放
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();
    if (n == 1) {
        yesno(true);
        return;
    }

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    vvint dp(n + 1, vint(10, INF));
    rep2(i, 1, 10) {
        if (v[0] != i)
            dp[0][i] = 1;
        else
            dp[0][i] = 0;
    }

    rep2(i, 1, n) {
        rep(j, 10) {
            int change = v[i] != j;
            if (j - 1 >= 0) {
                chmin(dp[i][j], dp[i - 1][j - 1] + change);
            }
            if (j + 1 <= 9) {
                chmin(dp[i][j], dp[i - 1][j + 1] + change);
            }
            chmin(dp[i][j], dp[i - 1][j] + change);
        }
    }

    int ok = 0;
    rep(i, 10) {
        if (dp[n - 1][i] <= 1)
            ok = 1;
    }
    yesno(ok);
}

// 全探索解法
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    auto check = [](vint& v) -> bool {
        bool ok = true;
        int n = v.size();
        if (n == 1)
            return true;

        if (v[0] == 0)
            return false;

        rep(i, n - 1) {
            if (abs(v[i] - v[i + 1]) > 1)
                ok = false;
        }

        return ok;
    };

    rep(i, n) {
        vint t = v;
        rep(j, 10) {
            t[i] = j;
            if (check(t)) {
                yesno(true);
                return;
            }
        }
    }

    yesno(false);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vint ans(N * 2 - 1, N);
    for (int i = 1; i < N * 2 - 1; i += 2) {
        ans[i] = N - 1;
    }

    for (int i = N - 2; i >= 1; i--) {
        vint tmp;
        int cnt = i;
        int m = ans.size();
        tmp.push_back(i);
        cnt--;
        rep(j, m) {
            tmp.push_back(ans[j]);
            if (cnt > 1 && j + 1 < m && tmp.back() != i && ans[j + 1] != i && abs(tmp.back() - i) <= 2 && abs(ans[j + 1] - i) <= 2) {
                tmp.push_back(i);
                cnt--;
            }
        }
        if (cnt)
            tmp.push_back(i);
        swap(tmp, ans);
    }
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    S = "_" + S;

    vll C(N + 1), D(N + 1);
    rep(i, N) cin >> C[i + 1];
    rep(i, N) cin >> D[i + 1];

    // dp[i][j]: i 文字目まで見たときの、対応が取れていない左カッコの数が j のときの最小コスト
    vvll dp(N + 1, vll(N + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(j, N) {
            if (S[i] == '(') {
                chmin(dp[i][j + 1], dp[i - 1][j]);

                // 反転
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j] + C[i]);
            } else {
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j]);

                // 反転
                chmin(dp[i][j + 1], dp[i - 1][j] + C[i]);
            }

            // i 番目の要素を削除
            chmin(dp[i][j], dp[i - 1][j] + D[i]);
        }
    }
    cout << dp[N][0] << endl;
}