#include "minecraft.h"
#include <bits/stdc++.h>



using namespace std;

const int MAXN = 1e5;

int n, k;
vector<int>ans;

pair<int,vector<int>> dnc(int l, int r)
{
    int counter = find_portals(l, r);
    if(counter == 0)return {0, {}};
    if(counter == r - l + 1)
    {
        vector<int>curr;
        for(int i = l; i <= r; i++)
        {
            curr.push_back(i);
        }
        return {r - l + 1, curr};
    }

    int mid = (l + r) / 2;

    vector<int>curr, cur2;
    pair<int,vector<int>>qry1, qry2;
    qry1 = dnc(l, mid);
    vector<int>cur1 = qry1.second;
    if(qry1.first != counter)cur2 = dnc(mid + 1, r).second;

    for(auto i: cur1)
    {
        curr.push_back(i);
    }
    for(auto i: cur2)
    {
        curr.push_back(i);
    }
    return {counter, curr};
}

std::vector<int> portals(int N, int K)
{
    n = N; k = K;
    return dnc(1, n).second;
}

long long dist[MAXN + 5], par[MAXN + 5];
vector<pair<int,int>>graph[MAXN + 5];
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(int i = 1; i <= n; i++)
    {
        graph[i].clear();
    }
    
    n = N;
    for(auto i: paths)
    {
        graph[i.second.first].push_back({i.second.second, i.first});
        graph[i.second.second].push_back({i.second.first, i.first});
    }


    priority_queue<pair<long long,int>>q;

    for(int i = 0; i < n; i++)
    {
        dist[i] = 1e18;
        par[i] = -1;
    }

    for(auto i: portals)
    {
        dist[i] = 0;
        par[i] = i;
        q.push({0, i});
    }

    while(!q.empty())
    {
        int a = q.top().second; q.pop();

        for(auto i: graph[a])
        {
            if(dist[i.first] > dist[a] + i.second)
            {
                par[i.first] = par[a];
                dist[i.first] = dist[a] + i.second;
                q.push({-dist[i.first], i.first});
            }
        }
    }

    long long mini = 1e18;
    int ans1, ans2 = 0;

    for(auto i: fortresses)
    {
        if(dist[i] < mini)
        {
            mini = dist[i];
            ans1 = i;
            ans2 = par[i];
        }
    }

    return {ans2, ans1};
}


std::pair<int, int> find_end_portal(int L)
{
    //std::string throw_eye(std::pair<int, int> coordinates);
    return {1, 1};
}
