#include "minecraft.h"
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <array>
#include <algorithm>
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> portals(int l, int r, int K)
{
    // cerr << l << " " << r << " " << K << "\n";
    if (l == r && K == 1)
        return {l};
    if (l == r - 1)
    {
        if (K == 2)
            return {l, l + 1};
        if (find_portals(l, l))
            return {l};
        return {r};
    }
    vector<int> ans;
    int last = l;
    for (int i = log2(r - l - 1); i >= 0 && K > 0 && last + (1 << i) <= r; --i)
    {
        int ch = find_portals(last, last + (1 << i));
        // cerr << last + (1 << i) << " " << ch << "\n";
        if (ch > 0)
        {
            auto ports = portals(last, last + (1 << i), ch);
            ans.insert(ans.begin(), all(ports));
        }
        last = last + (1 << i) + 1;
        K -= ch;
    }
    int ch = K;
    if (K > 0)
    {
        auto ports = portals(last, r, ch);
        ans.insert(ans.begin(), all(ports));
    }
    return ans;
}
std::vector<int> portals(int N, int K)
{
    return portals(1, N, K);
}
using pil = pair<int, long long>;
using pii = pair<int, int>;
using trii = array<long long, 3>;
map<int, long long> distS;
map<int, int> portalUsedS;
map<int, vector<pii>> G;
pii minimal_danger(int N, std::vector<std::pair<int, pii>> paths, std::vector<int> portals, std::vector<int> fortresses)
{
    priority_queue<trii, vector<trii>, greater<>> pq;
    sort(all(portals));
    for (auto e : portals)
        pq.push({0, e, e}), distS[e] = 0, portalUsedS[e] = e;
    for (auto [w, pr] : paths)
    {
        auto [u, v] = pr;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    while (!pq.empty())
    {
        auto [d, u, root] = pq.top();
        pq.pop();
        if (distS.count(u) && distS[u] < d)
            continue;

        for (auto [v, w] : G[u])
        {
            if (distS.count(v) && distS[v] <= d + w)
                continue;
            distS[v] = d + w;
            portalUsedS[v] = root;
            pq.push({distS[v], v, root});
        }
    }
    long long mn = 1e18, mnFortress = -1;
    for (auto e : fortresses)
    {
        if (distS[e] < mn)
            mn = distS[e], mnFortress = e;
    }
    return {portalUsedS[mnFortress], mnFortress};
}
pii find_end_portal(int L)
{
    int ansX, ansY;
    {
        int l = 1, r = L, ans = 0, mid;
        while (l <= r)
        {
            // cerr << l << " " << r << " " << mid << " ";
            mid = (l + r) / 2;
            auto e = throw_eye({1, mid});
            // cerr << e << "\n";
            if (e.find("N") == -1 ||e=="NONE")
            {
                r = mid - 1;
                ans = mid;
            }
            else
                l = mid + 1;
        }
        ansY = ans;
    }
    {
        int l = 1, r = L, ans = 0, mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            // cerr << l <<< " " << r << " " << mid << " ";
            auto e = throw_eye({mid, ansY});
            // cerr << e << ";" << ans << '\n';
            if (e[0]!='E')
            {
                r = mid - 1;
                ans = mid;
            }
            else
                l = mid + 1;
            // cerr << e << ";" << ans << '\n';
        }
        ansX = ans;
    }
    return {ansX, ansY};
}