#include "minecraft.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>v;
void rec(int l,int r,int br)
{
    if(!br)return;
    if(r-l+1==br)
    {
        for(int i=l;i<=r;i++)
        {
            v.push_back(i);
        }
        return;
    }
    int mid=(l+r)/2;
    int b=(find_portals(l,mid));
    rec(l,mid,b);
    rec(mid+1,r,br-b);
}
vector<int> portals(int N, int K)
{
    rec(1,N,K);
    return v;
}

struct cell
{
    long long int to,c;
    bool operator<(const cell&a)const
    {
        return c>a.c;
    }
};
vector<cell>gg[200005];
long long int fort[200005],used[200005],mi[200005];
priority_queue<cell>q;
pair<int,int>p;
void dijkstra()
{
    cell w,nb;
    while(q.size())
    {
        w=q.top();
        q.pop();
        if(fort[w.to])
        {
            p={used[w.to],w.to};
            return;
        }
        if(w.c>mi[w.to])continue;
        for(int i=0;i<gg[w.to].size();i++)
        {
            nb=gg[w.to][i];
            if(!mi[nb.to]||w.c+nb.c<mi[nb.to])
            {
                mi[nb.to]=w.c+nb.c;
                used[nb.to]=used[w.to];
                q.push({nb.to,mi[nb.to]});
            }
        }
    }
}
pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths, vector<int> portals, vector<int> fortresses)
{
    int a,b,c;
    for(int i=0;i<paths.size();i++)
    {
        a=paths[i].second.first;
        b=paths[i].second.second;
        c=paths[i].first;
        gg[a].push_back({b,c});
        gg[b].push_back({a,c});
    }
    for(int i=0;i<fortresses.size();i++)
    {
        fort[fortresses[i]]=1;
    }
    for(int i=0;i<portals.size();i++)
    {
        q.push({portals[i],0});
        used[portals[i]]=portals[i];
    }
    dijkstra();
    return p;
}

pair<int, int> find_end_portal(int L)
{
    int l1=1,r1=L,l2=1,r2=L,mid1,mid2;
    string s;
    int ot1=0,ot2=0;
    while(l1<=r1)
    {
        mid1=(l1+r1)/2;
        mid2=(l2+r2)/2;
        s=throw_eye({mid1,mid2});
        if(s=="NONE")
        {
            ot1=mid1;
            ot2=mid2;
            return {ot1,ot2};
        }
        if(s=="N"||s=="S")
        {
            ot1=mid1;
            if(s=="N")l2=mid2+1;
            else r2=mid2-1;
        }
        if(s=="E"||s=="W")
        {
            ot2=mid2;
            if(s=="E")l1=mid1+1;
            else r1=mid1-1;
        }
        if(s=="NE")
        {
            l2=mid2+1;
            l1=mid1+1;
        }
        if(s=="NW")
        {
            l2=mid2+1;
            r1=mid1-1;
        }
        if(s=="SW")
        {
            r2=mid2-1;
            r1=mid1-1;
        }
        if(s=="SE")
        {
            r2=mid2-1;
            l1=mid1+1;
        }
    }
    return {ot1,ot2};
}
