#include "minecraft.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int n, k;
vector<int> pos;
vector<pair<long long int, long long int>> g[maxn];
bool visited[maxn];
bool dali[maxn];
pair<long long int, long long int> dist[maxn];
void dnc(int l, int r, int cnt)
{
    if (cnt == 0)
        return;
    if (r - l + 1 == cnt)
    {
        for (int i = l; i <= r; i++)
        {
            pos.push_back(i);
        }
        return;
    }
    int mid = (l + r) >> 1;
    int curr = find_portals(l, mid);
    dnc(l, mid, curr);
    dnc(mid + 1, r, cnt - curr);
    return;
}
vector<int> portals(int N, int K)
{
    n = N;
    k = K;
    dnc(1, N, K);
    return pos;
}

std::pair<int, int> minimal_danger(int N, std::vector<std::pair<int, std::pair<int, int>>> paths, std::vector<int> portals, std::vector<int> fortresses)
{
    for (auto x : paths)
    {
        g[x.second.second].push_back({x.second.first, x.first});
        g[x.second.first].push_back({x.second.second, x.first});
    }
    for (int i = 0; i < maxn; i++)
    {
        dist[i].first = LLONG_MAX;
        dist[i].second = -1;
    }
    priority_queue<pair<long long int, pair<long long int, long long int>>> q;
    for (auto x : portals)
    {
        q.push({0, {x, x}});
        dist[x].first = 0;
        dist[x].second = x;
    }
    for (auto x : fortresses)
    {
        dali[x] = true;
    }
    while (!q.empty())
    {
        long long int curr = q.top().second.first;
        long long int currdist = -q.top().first;
        long long int st = q.top().second.second;
        q.pop();
        if (dali[curr])
            return {st, curr};
        if (visited[curr])
            continue;
        visited[curr] = true;
        for (auto x : g[curr])
        {
            long long int next = x.first;
            long long int weight = x.second;
            if (currdist + weight < dist[next].first)
            {
                dist[next].first = currdist + weight;
                dist[next].second = st;
                q.push({-dist[next].first, {next, st}});
            }
        }
    }
}

std::pair<int, int> find_end_portal(int L)
{

    int l = 1;
    int l2 = 1;
    int r = L;
    int r2 = L;
    while (true)
    {
        int mid = (l + r) >> 1;
        int mid2 = (l2 + r2) >> 1;
        string ans = throw_eye({mid2, mid});
        if (ans == "NE")
        {
            l = mid + 1;
            l2 = mid2 + 1;
        }

        if (ans == "N")
        {
            l = mid + 1;
        }
        if (ans == "NW")
        {
            l = mid + 1;
            r2 = mid2 - 1;
        }
        if (ans == "E")
        {
            l2 = mid2 + 1;
        }
        if (ans == "NONE")
        {
            return {mid2, mid};
        }
        if (ans == "W")
        {
            r2 = mid2 - 1;
        }
        if (ans == "SE")
        {
            r = mid - 1;
            l2 = mid2 + 1;
        }
        if (ans == "S")
        {
            r = mid - 1;
        }
        if (ans == "SW")
        {
            r = mid - 1;
            r2 = mid2 - 1;
        }
    }
}