#include "minecraft.h"
#include <bits/stdc++.h>
using namespace std;
int n,k;
vector <int> v1;
int dnc(int l,int r,int val)
{
    if(val==0)return val;
    if(l==r)
    {
        v1.push_back(l);
        return val;
    }
    int mid=(l+r)/2;
    int v=val;
    val-=dnc(l,mid,find_portals(l,mid));
    val-=dnc(mid+1,r,val);
    return v;
}
std::vector<int> portals(int N, int K)
{
    n=N;
    k=K;
    dnc(1,N,k);
    return v1;
}
struct edge
{
    long long d,v;
    bool operator<(const edge& e) const
    {
        return d>e.d;
    }
};
priority_queue <edge> q;
pair <long long,long long> d[131072];
vector <pair <long long,long long>> v[131072];
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++)v[i].clear();
    for(auto i:paths)
    {
        int w=i.first;
        v[i.second.first].push_back({i.second.second,w});
        v[i.second.second].push_back({i.second.first,w});
    }
    for(int i=1;i<=N;i++)d[i]={1e18,0};
    for(auto i:fortresses)
    {
        d[i].first=0;
        d[i].second=i;
        q.push({0,i});
    }
    while(!q.empty())
    {
        edge w=q.top();
        q.pop();
        if(d[w.v].first>=w.d)
        {
            d[w.v].first=w.d;
            for(auto nb:v[w.v])
            {
                if(d[nb.first].first>=d[w.v].first+nb.second)
                {
                    d[nb.first].first=d[w.v].first+nb.second;
                    d[nb.first].second=d[w.v].second;
                    q.push({d[nb.first].first,nb.first});
                }
            }
        }
    }
    long long mn=1e18,ans=0,a1;
    for(auto i:portals)
    {
        if(mn>d[i].first)
        {
            mn=d[i].first;
            ans=d[i].second;
            a1=i;
        }
    }
    return {a1,ans};
}

std::pair<int, int> find_end_portal(int L)
{
    int l1=1,r1=L,l2=1,r2=L,c1,c2;
    while(l1<=r1&&l2<=r2)
    {
        int mid1=(l1+r1)/2,mid2=(l2+r2)/2;
        string t=throw_eye({mid2,mid1});
        if(t=="NONE")
        {
            c1=mid1;
            c2=mid2;
            break;
        }
        if(t.find('N')!=-1)l1=mid1+1;
        else if(t.find('S')!=-1)r1=mid1-1;
        else c1=mid1;
        if(t.find('E')!=-1)l2=mid2+1;
        else if(t.find('W')!=-1)r2=mid2-1;
        else c2=mid2;
    }
    return {c2,c1};
}
