#include "minecraft.h"
#include<bits/stdc++.h>
using namespace std;

template<class T> using matrix = vector<vector<T>>;
const long long inf = 1e18 + 7;
vector<int> p;

void find_portal(int l, int r, int cnt){
    if(cnt == 0)return;
    if(l == r){
        p.push_back(l); return;
    }
    int m = (l + r) / 2;
    int x = find_portals(l, m);
    int y = cnt - x;
    find_portal(l, m, x);
    find_portal(m + 1, r, y);
}

vector<int> portals(int n, int k){
    find_portal(1, n, k);
    sort(p.begin(), p.end());
    return p;
}

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) {
    matrix<pair<int, int>> G(n);
    for (auto& [w, uv] : paths) {
        int u = uv.first, v = uv.second;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    priority_queue<
        array<long long, 3>,
        vector<array<long long, 3>>,
        greater<array<long long, 3>>
    >pq;

    vector<bool>check(n + 1, false);
    vector<long long>dist(n + 1, inf);
    for(auto i : fortresses)check[i] = true;
    for(auto i : portals){
        pq.push({0, i, i}); dist[u] = 0;
    }
    while(!pq.empty()){
        auto [d, u, par] = pq.top();
        pq.pop();
        if(d > dist[u])continue;
        if(check[u]){
            return {(int)par, (int)u};
        }
        for(auto [v, w] : G){
            if(dist[u] + w >= dist[v])continue;
            dist[v] = dist[u] + w;
            pq.push({dist[v], v, par});
        }
    }
    return {1, 1};
}

pair<int, int> find(int x, int y, int a, int b){
    if(x == a && y == b)return {x, y};
    int nx = (x + a) / 2, ny = (y + b) / 2;
    string dirr = throw_eye({nx, ny});
    if(dirr == "NE")  return find(nx + 1, ny + 1, a + 0 , b);
    if(dirr == "N")   return find(nx + 0, ny + 1, nx + 0, b);
    if(dirr == "NW")  return find(x + 0 , ny + 1, nx - 1, b);
    if(dirr == "E")   return find(nx + 1, ny + 0, a + 0 , ny);
    if(dirr == "NONE")return {nx, ny};
    if(dirr == "W")   return find(x + 0 , ny + 0, nx - 1, ny);
    if(dirr == "SE")  return find(nx + 1, y + 0 , a + 0 , ny - 1);
    if(dirr == "S")   return find(nx + 0, y + 0 , nx + 0, ny - 1);
    if(dirr == "SW")  return find(x + 0 , y + 0 , nx - 1, ny - 1);
}

pair<int, int> find_end_portal(int L) {
    return find(1, 1, L, L);
}
