#include "minecraft.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
vector<int> divide(int l,int r,int cnt)
{   
    if(cnt==0) return{};
    if(l==r)
    {
        return {l};
    }
    int m=(l+r)/2;
    int br=find_portals(l,m);
    vector<int> v1,v2;
    v1=divide(l,m,br);
    v2=divide(m+1,r,cnt-br);
    vector<int> ans=v1;
    for(int x:v2)
    {
        ans.push_back(x);
    }
    return ans;
}
std::vector<int> portals(int N, int K) 
{
    return divide(1,N,K);
}
struct cell
{
    int to;
    long long cost;
    cell(){};
    cell(int _to,long long _cost)
    {
        to=_to;cost=_cost;
    };
    bool operator<(const cell& c)const
    {
        return cost>c.cost;
    }
};
const int maxn=1e5+1000;
vector<cell> v[maxn];
int from[maxn];
long long d[maxn];
void dijkstra(vector<int>portal)
{
    for(int i=1;i<maxn;i++)
    {
        d[i]=1e18;
    }
    priority_queue<cell> q;
    for(int x:portal)
    {
        d[x]=0;
        q.push({x,0});
        from[x]=x;
    }
    while(q.size())
    {
        cell w=q.top();
        q.pop();
        if(d[w.to]<w.cost) continue;
        for(cell nb:v[w.to])
        {
            if(d[nb.to]>nb.cost+d[w.to])
            {
                d[nb.to]=nb.cost+d[w.to];
                from[nb.to]=from[w.to];
                q.push({nb.to,d[nb.to]});
            }
        }
    }
}
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(pair<int,pair<int,int>> p:paths)
    {
        v[p.sec.fir].push_back({p.sec.sec,p.fir});
        v[p.sec.sec].push_back({p.sec.fir,p.fir});
    }
    dijkstra(portals);
    long long dan=1e9;
    int por,fort;
    for(int x:fortresses)
    {
        if(d[x]<dan)
        {
            fort=x;
            por=from[x];
            dan=d[x];
        }
    }
    return {por,fort};
}
pair<int,int> find_end_portal(int L)
{
    int xmin=1,xmax=L;
    int ymin=1,ymax=L;
    while(true)
    {
        int mx=(xmin+xmax)/2;
        int my=(ymin+ymax)/2;
        string s=throw_eye({mx,my});
        if(s=="NONE")
        {
            return {mx,my};
        }
        else if(s=="NE")
        {
            xmin=mx+1;
            ymin=my+1;
        }
        else if(s=="NW")
        {
            xmax=mx-1;
            ymin=my+1;
        }
        else if(s=="SE")
        {
            xmin=mx+1;
            ymax=my-1;
        }
        else if(s=="SW")
        {
            xmax=mx-1;
            ymax=my-1;
        }
        else if(s=="N")
        {
            xmin=mx;
            xmax=mx;
            ymin=my+1;
        }
        else if(s=="S")
        {
            xmin=mx;
            xmax=mx;
            ymax=my-1;
        }
        else if(s=="E")
        {
            xmin=mx+1;
            ymin=my;
            ymax=my;
        }
        else if(s=="W")
        {
            xmax=mx-1;
            ymin=my;
            ymax=my;
        }
    }
}