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

int uniK;

void fart(vector<int>& ans, int ll, int rr) {
  ///  cout << "Interval: " << ll << " " << rr << endl;
    int idx = ll - 1, cnt = 0;
    while(idx + 1 <= rr) {
        if(uniK == 0) {
          ///  cout << idx + 1 << " " << rr << endl;
            break;
        }
        if(find_portals(idx + 1, rr) == 0) {
            break;
        }
        int l = idx + 1, r = rr, mid, jk = idx + 1;
        idx = INT_MAX;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(find_portals(jk, mid) >= 1) {
                idx = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        if(idx == INT_MAX) {
            break;
        }
        ans.push_back(idx);
        uniK--;
      ///  cout << idx << endl;
    }
}

vector<int> portals(int n, int k) {
    int sq, i = 1;
    uniK = k;
    vector<int> ans;
    while(i <= n) {
        if(ans.size() == k) break;
        double CheatMultiplier = 1.435;
        int fuh = k - ans.size();
        int ert = CheatMultiplier * fuh;
        int sq = (n - i + 1) / ert;
        fart(ans, i, min(i + sq - 1, n));
        i = min(i + sq - 1, n) + 1;
    }
    return ans;
}

typedef long long int LL;

pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths,
                                   vector<int> portals, vector<int> fortresses) {
    vector<pair<int, LL>> to[N + 1];
    for(auto it : paths) {
        to[it.second.first].push_back({it.second.second, (LL)it.first});
        to[it.second.second].push_back({it.second.first, (LL)it.first});
    }
    LL minh = LLONG_MAX;
    int k1 = 1, k2 = 2;
    if(portals.size() < fortresses.size()) {
        if((LL)portals.size() * (LL)fortresses.size() * (LL)log2(fortresses.size()) > (LL)1e7) return {1, 1};
        for(int jk : portals) {
            if(clock() / (double)CLOCKS_PER_SEC > 0.4) return {1, 1};
            vector<LL> dist(N + 1);
            for(int i = 0; i < dist.size(); i++) {
                dist[i] = LLONG_MAX;
            }
            priority_queue<pair<LL, LL>> pq;
            pq.push({0, jk});
            dist[jk] = 0;
            while(!pq.empty()) {
                auto [d, curr] = pq.top();
                pq.pop();
                d = -d;
                for(auto [next, w] : to[curr]) {
                    if(dist[next] > dist[curr] + w) {
                        dist[next] = dist[curr] + w;
                        pq.push({-dist[next], next});
                    }
                }
            }
            int ans = fortresses[0];
            for(int i : fortresses) {
             ///   cout << i << " " << dist[i] << endl;
                if(dist[ans] > dist[i]) {
                    ans = i;
                }
            }
            if(minh > dist[ans]) {
                minh = dist[ans];
                k1 = jk, k2 = ans;
            }
        }
        return {k1, k2};
    }
    else {
        for(int jk : fortresses) {\
            if(clock() / (double)CLOCKS_PER_SEC > 0.4) return {1, 1};
            if((LL)fortresses.size() * (LL)portals.size() * (LL)log2(portals.size()) > (LL)1e7) return {1, 1};
            vector<LL> dist(N + 1);
            for(int i = 0; i < dist.size(); i++) {
                dist[i] = LLONG_MAX;
            }
            priority_queue<pair<LL, LL>> pq;
            pq.push({0, jk});
            dist[jk] = 0;
            while(!pq.empty()) {
                auto [d, curr] = pq.top();
                pq.pop();
                d = -d;
                for(auto [next, w] : to[curr]) {
                    if(dist[next] > dist[curr] + w) {
                        dist[next] = dist[curr] + w;
                        pq.push({-dist[next], next});
                    }
                }
            }
            int ans = portals[0];
            for(int i : portals) {
             ///   cout << i << " " << dist[i] << endl;
                if(dist[ans] > dist[i]) {
                    ans = i;
                }
            }
            if(minh > dist[ans]) {
                minh = dist[ans];
                k2 = jk, k1 = ans;
            }
        }
    }

    return {k1, k2};
}

pair<int, int> find_end_portal(int L) {
    int lx = 1, ly = 1, rx = L, ry = L;
    while(lx <= rx && ly <= ry) {
        if(clock() / (double)CLOCKS_PER_SEC > 0.6) return {1, 1};
       // cout << lx << " " << ly << " " << rx << " " << ry << endl;
        if(lx == rx && ly == ry) return {lx, rx};
        if(lx == rx) {
            int l1 = ly, r1 = ry, mid;
            while(l1 <= r1) {
                mid = (l1 + r1) >> 1;
                string s = throw_eye({lx, mid});
                if(s == "NONE") {
                    return {lx, mid};
                }
                if(s == "W") {
                    r1 = mid - 1;
                }
                else {
                    l1 = mid + 1;
                }
            }
        }
        if(ly == ry) {
            int l1 = lx, r1 = rx, mid;
            while(l1 <= r1) {
                mid = (l1 + r1) >> 1;
                string s = throw_eye({mid, ly});
                if(s == "NONE") {
                    return {mid, ly};
                }
                if(s == "S") {
                    r1 = mid - 1;
                }
                else {
                    l1 = mid + 1;
                }
            }
        }
        int midx = (lx + rx) >> 1, midy = (ly + ry) >> 1;
        string q = throw_eye({midx, midy});
        if(q == "W" || q == "NW" || q == "N") {
            ly = midy, rx = midx;
        }
        else if(q == "S" || q == "SW") {
            rx = midx, ry = midy - 1;
        }
        else if(q == "SE") {
            lx = midx + 1, ry = midy - 1;
        }
        else {
            lx = midx + 1, ly = midy;
        }
    }
}

/*

100 2
55 90
2
55 12 15
12 77 5
1
77
99
6 7

*/









